Факультатив теория вычислений 2016/2017 — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
(Дневник курса)
 
(не показано 13 промежуточных версии 2 участников)
Строка 1: Строка 1:
 +
== Общая информация ==
 +
 +
Занятия по курсу «Теория вычислений» проходят по вторникам в ауд. 513 и пятницам в ауд. 503, начало занятий 16:40.
 +
 +
Срок сдачи первого домашнего задания — первая неделя ноября.
 +
 +
Доступен [https://dl.dropboxusercontent.com/u/31418200/hse/2016/edited.pdf листок] от 7-го ноября.
 +
 +
Результаты домашнего задания по формальным языкам в [https://dl.dropboxusercontent.com/u/31418200/hse/2016/%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F%20%D0%B2%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D0%B9.xls таблице]. См. лист «Задание 1».
 +
 +
== Объявления ==
 +
 +
'''13 декабря (вторник, обычное время)''' для желающих будет еще раз заново рассказан AM[2] протокол для задачи неизоморфизма графов.
 +
 +
'''О домашнем задании 2 (вычислительная сложность):''' требуется решить любые 10 задач (пункты 1a, 2b и т.д. cчитаются за отдельную задачу)
 +
из [https://www.dropbox.com/s/dibc6o5wgry3dqm/edited.pdf?dl=0 этого списка]. Те, кто не успевают подготовить домашнее задание к сроку (утро 5 декабря) должны
 +
связаться с кем-нибудь из преподавателей курса и договориться о продлении срока сдачи.
 +
 +
'''Экзамен''' по курсу состоится 16 декабря, 16:40. Экзамен устный.
 +
 +
'''Программа экзамена'''
 +
 +
'''I. Регулярные языки'''
 +
# Регулярные выражения
 +
# Конечные автоматы
 +
# Эквивалентность определений регулярных языков через конечные автоматы и регулярные выражения
 +
# Лемма о накачке
 +
# Теорема Майхилла-Нероуда. Минимальный ДКА.
 +
# Замкнутость класса регулярных языков относительно теоретико-множественных операций
 +
 +
'''II. Контекстно-свободные языки'''
 +
# КС-грамматики
 +
# Лемма о накачке (для КС языков)
 +
# Нормальная форма Хомского
 +
# Автоматы с магазинной памятью
 +
# Эквивалентность языков, задаваемых КС-грамматиками и МП-автоматами
 +
# Свойства замкнутости класса КС-языков относительно теоретико-множественных операций и относительно пересечения с регулярными языками
 +
 +
'''III. Вычислительная сложность.'''
 +
# Классы P, NP, coNP.
 +
# Полиномиальная сводимость.
 +
# NP- и coNP-полные задачи.
 +
# Класс BPP. Устойчивость определения относительно уменьшения вероятности ошибки.
 +
# Вероятностное сведение задачи о полном паросочетании в двудольном графе к вычислению определителя.
 +
# Схемная сложность булевых функций и класс P/poly.
 +
# Вложение BPP в P/poly.
 +
# Полиномиальная иерархия. Вложение BPP во второй уровень иерархии.
 +
# Универсальный перебор по Левину
 +
# Решение полиномиальной игры лежит в PSPACE. Обратное: для всякого свойства из PSPACE есть полиномиальная игра с параметром, в которой есть выигрыш тогда и только тогда, когда параметр обладает указанным свойством. 3.11 Задача TQBF  и её полнота в PSPACE.
 +
# PSPACE-полные задачи: игра на графе без повторений позиций, игра в слова.
 +
# Теорема Сэвича
 +
# Определение класса AM: вместо второго игрока случайные биты. Вероятность выигрыша при оптимальной стратегии.
 +
# Замкнутость класса AM относительно сводимости.
 +
# AM лежит в PSPACE.
 +
# TQBF лежит в AM.
 +
 
== Дневник курса ==
 
== Дневник курса ==
  
{| class="wikitable" style="width: 25%;"
+
{| class="wikitable" style="width: 25%; min-width:400px; max-width:500px;"
 
|-
 
|-
 
! дата  !! занятие !! материалы
 
! дата  !! занятие !! материалы
 
|- style="text-align:center;"
 
|- style="text-align:center;"
|colspan=3 | '''Регулярные языки и конечные автоматы'''
+
|colspan=3 style="padding: 0.5ex 0; "| '''Регулярные языки и конечные автоматы'''
 +
|-
 +
||  20.09 ||  Лекция 1 ||   Глава 1 Сипсера
 
|-
 
|-
|| 20.09 || Лекция 1 || Глава 1 Сипсера
+
||  23.09 ||  Семинар 1 ||   [http://rubtsov.su/public/fl/2016/hse_ct/cw01_ct.pdf Листок семинаров (1-2)]
 
|-
 
|-
|| 23.09 || Семинар 1 || Листок семинаров (1-2)
+
||  27.09 ||  Семинар 2 ||  [http://rubtsov.su/public/fl/2016/hse_ct/hw01_ct.pdf Домашнее задание 1 (1/2)]
|-
+
|| 27.09 || Семинар 2 || Домашнее задание 1 (1/2)
+
 
|- style="text-align:center;"
 
|- style="text-align:center;"
|colspan=3| '''Контекстно-свободные языки'''
+
|colspan=3 style="padding: 0.5ex 0; "| '''Контекстно-свободные языки'''
 +
|-
 +
||  30.09 ||  Лекция 2 ||   Глава 2 Сипсера
 +
|-
 +
||  04.10 ||  Лекция 3 ||   Глава 2 Сипсера
 +
|-
 +
||  07.10 ||   Семинар 3 ||   [http://rubtsov.su/public/fl/2016/hse_ct/cw02_ct.pdf Листок семинаров (3-4)]
 
|-
 
|-
|| 30.09 || Лекция 2 || Глава 2 Сипсера
+
||  11.10 ||  Лекция 4 ||   Глава 2 Сипсера
 
|-
 
|-
 +
||  14.10 ||  Семинар 4 ||  [http://rubtsov.su/public/fl/2016/hse_ct/hw01_2_ct.pdf Домашнее задание 1 (2/2)]
 
|}
 
|}

Текущая версия на 14:53, 9 ноября 2017

Общая информация

Занятия по курсу «Теория вычислений» проходят по вторникам в ауд. 513 и пятницам в ауд. 503, начало занятий 16:40.

Срок сдачи первого домашнего задания — первая неделя ноября.

Доступен листок от 7-го ноября.

Результаты домашнего задания по формальным языкам в таблице. См. лист «Задание 1».

Объявления

13 декабря (вторник, обычное время) для желающих будет еще раз заново рассказан AM[2] протокол для задачи неизоморфизма графов.

О домашнем задании 2 (вычислительная сложность): требуется решить любые 10 задач (пункты 1a, 2b и т.д. cчитаются за отдельную задачу) из этого списка. Те, кто не успевают подготовить домашнее задание к сроку (утро 5 декабря) должны связаться с кем-нибудь из преподавателей курса и договориться о продлении срока сдачи.

Экзамен по курсу состоится 16 декабря, 16:40. Экзамен устный.

Программа экзамена

I. Регулярные языки

  1. Регулярные выражения
  2. Конечные автоматы
  3. Эквивалентность определений регулярных языков через конечные автоматы и регулярные выражения
  4. Лемма о накачке
  5. Теорема Майхилла-Нероуда. Минимальный ДКА.
  6. Замкнутость класса регулярных языков относительно теоретико-множественных операций

II. Контекстно-свободные языки

  1. КС-грамматики
  2. Лемма о накачке (для КС языков)
  3. Нормальная форма Хомского
  4. Автоматы с магазинной памятью
  5. Эквивалентность языков, задаваемых КС-грамматиками и МП-автоматами
  6. Свойства замкнутости класса КС-языков относительно теоретико-множественных операций и относительно пересечения с регулярными языками

III. Вычислительная сложность.

  1. Классы P, NP, coNP.
  2. Полиномиальная сводимость.
  3. NP- и coNP-полные задачи.
  4. Класс BPP. Устойчивость определения относительно уменьшения вероятности ошибки.
  5. Вероятностное сведение задачи о полном паросочетании в двудольном графе к вычислению определителя.
  6. Схемная сложность булевых функций и класс P/poly.
  7. Вложение BPP в P/poly.
  8. Полиномиальная иерархия. Вложение BPP во второй уровень иерархии.
  9. Универсальный перебор по Левину
  10. Решение полиномиальной игры лежит в PSPACE. Обратное: для всякого свойства из PSPACE есть полиномиальная игра с параметром, в которой есть выигрыш тогда и только тогда, когда параметр обладает указанным свойством. 3.11 Задача TQBF и её полнота в PSPACE.
  11. PSPACE-полные задачи: игра на графе без повторений позиций, игра в слова.
  12. Теорема Сэвича
  13. Определение класса AM: вместо второго игрока случайные биты. Вероятность выигрыша при оптимальной стратегии.
  14. Замкнутость класса AM относительно сводимости.
  15. AM лежит в PSPACE.
  16. TQBF лежит в AM.

Дневник курса

дата занятие материалы
Регулярные языки и конечные автоматы
  20.09   Лекция 1   Глава 1 Сипсера
  23.09   Семинар 1   Листок семинаров (1-2)
  27.09   Семинар 2  Домашнее задание 1 (1/2)
Контекстно-свободные языки
  30.09   Лекция 2   Глава 2 Сипсера
  04.10   Лекция 3   Глава 2 Сипсера
  07.10   Семинар 3   Листок семинаров (3-4)
  11.10   Лекция 4   Глава 2 Сипсера
  14.10   Семинар 4  Домашнее задание 1 (2/2)