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

Rubtsov: /* Дневник курса */

2017-11-09T11:53:00Z

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

← Предыдущая версия		Версия от 11:53, 9 ноября 2017
Строка 65:		Строка 65:
	\|\|  20.09 \|\|  Лекция 1 \|\|   Глава 1 Сипсера		\|\|  20.09 \|\|  Лекция 1 \|\|   Глава 1 Сипсера
	\|-		\|-
	\|\|  23.09 \|\|  Семинар 1 \|\|   [~~https~~://dl.~~dropboxusercontent.com/u~~/~~31418200~~/fl/2016/hse_ct/cw01_ct.pdf Листок семинаров (1-2)]		\|\|  23.09 \|\|  Семинар 1 \|\|   [http://rubtsov.su/public/fl/2016/hse_ct/cw01_ct.pdf Листок семинаров (1-2)]
	\|-		\|-
	\|\|  27.09 \|\|  Семинар 2 \|\|  [~~https~~://dl.~~dropboxusercontent.com/u~~/~~31418200~~/fl/2016/hse_ct/hw01_ct.pdf Домашнее задание 1 (1/2)]		\|\|  27.09 \|\|  Семинар 2 \|\|  [http://rubtsov.su/public/fl/2016/hse_ct/hw01_ct.pdf Домашнее задание 1 (1/2)]
	\|- style="text-align:center;"		\|- style="text-align:center;"
	\|colspan=3 style="padding: 0.5ex 0; "\| '''Контекстно-свободные языки'''		\|colspan=3 style="padding: 0.5ex 0; "\| '''Контекстно-свободные языки'''
Строка 75:		Строка 75:
	\|\|  04.10 \|\|  Лекция 3 \|\|   Глава 2 Сипсера		\|\|  04.10 \|\|  Лекция 3 \|\|   Глава 2 Сипсера
	\|-		\|-
	\|\|  07.10 \|\|  Семинар 3 \|\|   [~~https~~://dl.~~dropboxusercontent.com/u~~/~~31418200~~/fl/2016/hse_ct/cw02_ct.pdf Листок семинаров (3-4)]		\|\|  07.10 \|\|  Семинар 3 \|\|   [http://rubtsov.su/public/fl/2016/hse_ct/cw02_ct.pdf Листок семинаров (3-4)]
	\|-		\|-
	\|\|  11.10 \|\|  Лекция 4 \|\|   Глава 2 Сипсера		\|\|  11.10 \|\|  Лекция 4 \|\|   Глава 2 Сипсера
	\|-		\|-
	\|\|  14.10 \|\|  Семинар 4 \|\|  [~~https~~://dl.~~dropboxusercontent.com/u~~/~~31418200~~/fl/2016/hse_ct/hw01_2_ct.pdf Домашнее задание 1 (2/2)]		\|\|  14.10 \|\|  Семинар 4 \|\|  [http://rubtsov.su/public/fl/2016/hse_ct/hw01_2_ct.pdf Домашнее задание 1 (2/2)]
	\|}		\|}

Vyalyi в 16:46, 17 марта 2017

2017-03-17T16:46:36Z

← Предыдущая версия		Версия от 16:46, 17 марта 2017
Строка 14:		Строка 14:

	'''О домашнем задании 2 (вычислительная сложность):''' требуется решить любые 10 задач (пункты 1a, 2b и т.д. cчитаются за отдельную задачу)		'''О домашнем задании 2 (вычислительная сложность):''' требуется решить любые 10 задач (пункты 1a, 2b и т.д. cчитаются за отдельную задачу)
	из [https://dl.~~dropboxusercontent~~.com/u/~~33029521~~/edited.pdf этого списка]. Те, кто не успевают подготовить домашнее задание к сроку (утро 5 декабря) должны		из [https://www.dropbox.com/s/dibc6o5wgry3dqm/edited.pdf?dl=0 этого списка]. Те, кто не успевают подготовить домашнее задание к сроку (утро 5 декабря) должны
	связаться с кем-нибудь из преподавателей курса и договориться о продлении срока сдачи.		связаться с кем-нибудь из преподавателей курса и договориться о продлении срока сдачи.

Vyalyi в 17:55, 2 декабря 2016

2016-12-02T17:55:56Z

← Предыдущая версия		Версия от 17:55, 2 декабря 2016
Строка 15:		Строка 15:
	'''О домашнем задании 2 (вычислительная сложность):''' требуется решить любые 10 задач (пункты 1a, 2b и т.д. cчитаются за отдельную задачу)		'''О домашнем задании 2 (вычислительная сложность):''' требуется решить любые 10 задач (пункты 1a, 2b и т.д. cчитаются за отдельную задачу)
	из [https://dl.dropboxusercontent.com/u/33029521/edited.pdf этого списка]. Те, кто не успевают подготовить домашнее задание к сроку (утро 5 декабря) должны		из [https://dl.dropboxusercontent.com/u/33029521/edited.pdf этого списка]. Те, кто не успевают подготовить домашнее задание к сроку (утро 5 декабря) должны
	связаться с кем-нибудь из преподавателей курса и договориться о ~~сроке~~ сдачи.		связаться с кем-нибудь из преподавателей курса и договориться о продлении срока сдачи.

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

Vyalyi в 17:54, 2 декабря 2016

2016-12-02T17:54:20Z

← Предыдущая версия		Версия от 17:54, 2 декабря 2016
Строка 8:		Строка 8:

	Результаты домашнего задания по формальным языкам в [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».		Результаты домашнего задания по формальным языкам в [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://dl.dropboxusercontent.com/u/33029521/edited.pdf этого списка]. Те, кто не успевают подготовить домашнее задание к сроку (утро 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.

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

Rubtsov в 16:08, 27 ноября 2016

2016-11-27T16:08:51Z

← Предыдущая версия		Версия от 16:08, 27 ноября 2016
Строка 6:		Строка 6:

	Доступен [https://dl.dropboxusercontent.com/u/31418200/hse/2016/edited.pdf листок] от 7-го ноября.		Доступен [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».

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

Rubtsov в 15:38, 9 ноября 2016

2016-11-09T15:38:46Z

← Предыдущая версия		Версия от 15:38, 9 ноября 2016
Строка 4:		Строка 4:

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

			Доступен [https://dl.dropboxusercontent.com/u/31418200/hse/2016/edited.pdf листок] от 7-го ноября.

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

Rubtsov: /* Дневник курса */

2016-10-16T16:17:56Z

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

← Предыдущая версия		Версия от 16:17, 16 октября 2016
Строка 27:		Строка 27:
	\|\|  07.10 \|\|  Семинар 3 \|\|   [https://dl.dropboxusercontent.com/u/31418200/fl/2016/hse_ct/cw02_ct.pdf Листок семинаров (3-4)]		\|\|  07.10 \|\|  Семинар 3 \|\|   [https://dl.dropboxusercontent.com/u/31418200/fl/2016/hse_ct/cw02_ct.pdf Листок семинаров (3-4)]
	\|-		\|-
	\|\|  11.10 \|\|  Лекция 3 \|\|   Глава 2 Сипсера		\|\|  11.10 \|\|  Лекция 4 \|\|   Глава 2 Сипсера
	\|-		\|-
	\|\|  14.10 \|\|  Семинар 4 \|\|  [https://dl.dropboxusercontent.com/u/31418200/fl/2016/hse_ct/hw01_2_ct.pdf Домашнее задание 1 (2/2)]		\|\|  14.10 \|\|  Семинар 4 \|\|  [https://dl.dropboxusercontent.com/u/31418200/fl/2016/hse_ct/hw01_2_ct.pdf Домашнее задание 1 (2/2)]
	\|}		\|}

Rubtsov в 12:57, 16 октября 2016

2016-10-16T12:57:36Z

← Предыдущая версия		Версия от 12:57, 16 октября 2016
Строка 3:		Строка 3:
	Занятия по курсу «Теория вычислений» проходят по вторникам в ауд. 513 и пятницам в ауд. 503, начало занятий 16:40.		Занятия по курсу «Теория вычислений» проходят по вторникам в ауд. 513 и пятницам в ауд. 503, начало занятий 16:40.

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

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

Rubtsov: /* Общая информация */

2016-10-16T12:57:23Z

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

← Предыдущая версия		Версия от 12:57, 16 октября 2016
Строка 2:		Строка 2:

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

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

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

Rubtsov в 12:51, 16 октября 2016

2016-10-16T12:51:56Z

← Предыдущая версия		Версия от 12:51, 16 октября 2016
Строка 21:		Строка 21:
	\|\|  30.09 \|\|  Лекция 2 \|\|   Глава 2 Сипсера		\|\|  30.09 \|\|  Лекция 2 \|\|   Глава 2 Сипсера
	\|-		\|-
			\|\|  04.10 \|\|  Лекция 3 \|\|   Глава 2 Сипсера
			\|-
			\|\|  07.10 \|\|  Семинар 3 \|\|   [https://dl.dropboxusercontent.com/u/31418200/fl/2016/hse_ct/cw02_ct.pdf Листок семинаров (3-4)]
			\|-
			\|\|  11.10 \|\|  Лекция 3 \|\|   Глава 2 Сипсера
			\|-
			\|\|  14.10 \|\|  Семинар 4 \|\|  [https://dl.dropboxusercontent.com/u/31418200/fl/2016/hse_ct/hw01_2_ct.pdf Домашнее задание 1 (2/2)]
	\|}		\|}