Дисциплина "Теоретические основы компьютерных наук" для аспирантов ФКН ВШЭ.

2015-2016 год

Последний экзамен по курсу состоится в пятницу 23 июня 2017 г. в 10:30-13:30 в ауд. 511 (сдают М. Марон и Д. Тверской).

Пересдача коллоквиума и экзамена назначена на пятницу 7 октября с 9 до 11:50 (две пары) в ауд. 618. Можно пользоваться собственными рукописными конспектами (не ксерокопиями чужих), литературой пользоваться нельзя.

Программа экзамена. Программу коллоквиума см. ниже (список вопросов к коллоквиуму). Оценки.

Домашние задания

Содержание лекций и семинаров

Что надо изучить самостоятельно:

Ко второму занятию (16 декабря) необходимо самостоятельно ознакомиться со следующими темами:

К третьему занятию (10 февраля) необходимо самостоятельно ознакомиться со следующими темами:

К четвертому занятию (2 марта), на котором состоится коллоквиум, необходимо самостоятельно ознакомиться со следующими темами:

К шестому занятию (25 мая) необходимо самостоятельно ознакомиться с принципом Ocсam's razor машинного обучения, прочитав статью [Blumer, A., Ehrenfeucht, A., Haussler, D., and Warmuth, M.K.(1987). Occam's razor. Information Processing Letters, 24, 377-380.]

К экзамену (20 июня) необходимо самостоятельно разобрать доказательство оценки вероятности отклонения эмпирического качества гипотез от их фактического качества для гипотез из класса данной размерности Вапника-Червоненкиса (теорема Вапника-Червоненкиса).

Список вопросов к коллоквиуму.

Темы эссе (окончательный)

  1. (Взято Михаилом Бочкарёвым) Simple NP problems whose counting version is #P complete (permanent and a couple of others). Примеры простых NP задачи, для которых задачи подсчета #P полны (перманент и пара других). Про перманент можно прочитать в учебнике Пападимитриу [11], надо изложить доказательство.
  2. (Взято Анной Потапенко) One-way permutaions and constructing Pseudo random generators. Односторонние перестановки и их применение для построения генераторов псевдослучайных чисел. Можно прочитать в [9].
  3. (Взято Дмитрием Фроловым) The combinatorial proof of PCP-theorem. Комбинаторное доказательство PCP-теоремы. По учебнику [9].
  4. NP hardness of approximate solution of MAX3SAT via PCP-theorem. NP трудность приблизительного решения для MAX3SAT путем сведения к PCP-теореме. По учебнику [9].
  5. (Тверской) DEXP hardness of deciding valididy of formulas of the elementary theory of the additive group of reals. Super-Exponential Complexity of Presburger Arithmetic. (Fischer -- Rabin theorems). DEXP трудность задачи задачи распознавания истинности формул в абелевой группе действительных чисел. Трудность задачи распознавания истинности формул Арифметики Прессбургера (теоремы Фишера--Рабина). По статье [Fischer, Michael J.; Rabin, Michael O. (1974). "Super-Exponential Complexity of Presburger Arithmetic". Proceedings of the SIAM-AMS Symposium in Applied Mathematics 7: 27–41.]
  6. NEXP=MIP (MIP is the class of languages that have two provers interactive protocols). Совпадение NEXP и MIP (класса языков, допускающих интерактивное доказательство с двумя Доказывающими). По статье [M. Ben-Or, S. Goldwasser, J. Kilian, and A. Wigderson. Multi-prover interactive proofs: how to remove intractability, Proceedings of ACM STOC'88, pp. 113-131, 1988.]
  7. (Взято Ильей Турунтаевым) Nisan - Wigderson generators with an application to extractors (Trevisan extractor). Генераторы Нисана-Вигдерсона и их применение для построения экстраторов (Тревисан). [9]
  8. (Взято Нуртасом Махажановым) Expanding graphs and LOGSPACE algorithm for s-t-connectivity for undirected graphs (Reingold theorem). Экспандеры и их применение в алгоритме поиска пути в неорентированном графе на логарифмической памяти. [9]
  9. (взято Андреем Шестаковым) Average case complexity and average case complete NP problems. Сложность в среднем и NP трудные в среднем задачи. [Andrej Bogdanov and Luca Trevisan: Average-case complexity. In Madhu Sudan, editor, Foundations and Trends in Theoretical Computer Science, volume 2, issue 1, Now Publishers, 2006.]
  10. (Взято Екатериной Лобачевой) Yao XOR lemma and its three proofs. XOR лемма Яо об увеличении трудности предиката с помощью функции XOR и три ее доказательства. http://www.wisdom.weizmann.ac.il/~oded/COL/yao.pdf
  11. Circuits of small depth: the classes NC, NC^1, AC^0, AC^0[m]. Razborov-Smolensky theorem. Barrington theorem. (по книге [12])
  12. (Взято Николаем Фединым) An Exponential lower bound for PARITY for constant depth AND-OR-circuits. (По работе [J. Håstad, Almost Optimal Lower Bounds for Small Depth Circuits, in Randomness and Computation, Advances in Computing Reasearch, Vol 5, ed. S. Micali, 1989, JAI Press Inc, pp 143-170].)

Литература

  1. A. Китаев, А. Шень, М. Вялый. Классические и квантовые вычисления. М.: МЦНМО, ЧеРо, 1999.
  2. Владимир Крупский. Введение в сложность вычислений. Факториал Пресс, 2006.
  3. Sipser M. Introduction to the Theory of Computation. — Cengage Learning, 2013.
  4. Т. Кормен, Ч. Лейзерсон, Р. Ривест. Алгоритмы: построение и анализ. М.: МЦНМО, 2001.
  5. M. Гэри, Д. Джонсон. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
  6. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М. Мир 1979
  7. Downey, Rod G.; Fellows, Michael R. (1999). Parameterized Complexity. Springer.
  8. M. Grötschel, L. Lovász, A. Schrijver: Geometric Algorithms and Combinatorial Optimization, Springer, 1988.

    Продвинутая литература для написания эссе

  9. Sanjeev Arora, Boaz Barak Computational Complexity: A Modern Approach. Cambridge University Press, 2009.
  10. O. Goldreich. Foundations of Cryptography. Basic Tools. Cambridge UP. 2001.
  11. Christos H. Papadimitriou, Computational Complexity (Addison Wesley, 1994)
  12. H. Vollmer. Introduction tp Circuit Сomplexity. Springer 1999.