Проект по теоретической информатике 2018 - История изменений

Nichichileva в 16:21, 22 октября 2018

2018-10-22T16:21:09Z

← Предыдущая версия		Версия от 16:21, 22 октября 2018
Строка 1:		Строка 1:
			{{Карточка_проекта
			\|name=Проект по теоретической информатике
			\|mentor=Подольский Владимир Владимирович
			\|mentor_login={{URLENCODE:Nichichileva\|WIKI}}
			\|semester=Осень 2018
			\|course=2
			\|summer=
			\|number_of_students=30
			\|categorize=yes
			}}

	== Что за проект? ==		== Что за проект? ==

Vpodolskii: /* Возможные темы проекта */

2018-10-22T14:19:57Z

Возможные темы проекта

← Предыдущая версия		Версия от 14:19, 22 октября 2018
Строка 107:		Строка 107:
	Ментор: [https://www.hse.ru/org/persons/134220270 Владимир Владимирович Подольский]		Ментор: [https://www.hse.ru/org/persons/134220270 Владимир Владимирович Подольский]

	Типичная задача коммуникационной сложности выглядит так. Есть два человека, которые хотят вычислить функцию f(x,y) на какой-то паре входов (x,y). При этом первый знает только x, а второй только y, то есть чтобы вычислить функцию им нужно обмениваться информацией. Какое минимальное количество информации им нужно передать друг другу, чтобы вычислить функцию? Например, x и y могут быть файлами, и участники вычисления хотят узнать, совпадают ли эти файлы. Коммуникационная сложность оказывается очень полезной при доказательстве нижних оценок сложности вычислений в множестве вычислительных моделей. Подробнее об этом можно почитать в обзоре by Eyal Kushilevitz http://www.cs.~~bris~~.ac.uk/~~probtcs08~~/~~materials/kushilevitz~~.~~pdf~~		Типичная задача коммуникационной сложности выглядит так. Есть два человека, которые хотят вычислить функцию f(x,y) на какой-то паре входов (x,y). При этом первый знает только x, а второй только y, то есть чтобы вычислить функцию им нужно обмениваться информацией. Какое минимальное количество информации им нужно передать друг другу, чтобы вычислить функцию? Например, x и y могут быть файлами, и участники вычисления хотят узнать, совпадают ли эти файлы. Коммуникационная сложность оказывается очень полезной при доказательстве нижних оценок сложности вычислений в множестве вычислительных моделей. Подробнее об этом можно почитать в обзоре by Eyal Kushilevitz http://www.cs.technion.ac.il/~eyalk/cc-survey.ps.Z

Vpodolskii в 00:05, 9 октября 2018

2018-10-09T00:05:33Z

← Предыдущая версия		Версия от 00:05, 9 октября 2018
Строка 1:		Строка 1:
	~~Исследовательский проект~~

	== Что за проект? ==		== Что за проект? ==

Vpodolskii в 23:55, 8 октября 2018

2018-10-08T23:55:50Z

← Предыдущая версия		Версия от 23:55, 8 октября 2018
Строка 20:		Строка 20:

	== Возможные темы проекта ==		== Возможные темы проекта ==

			Ниже приведен список возможных тем проекта. Если у Вас есть свои пожелания, возможен вариант договориться с конкретным ментором о другой теме.


	'''Тема проекта: Формулы для функций Шпрага-Гранди.'''		'''Тема проекта: Формулы для функций Шпрага-Гранди.'''

Vpodolskii: /* Возможные темы проекта */

2018-10-08T23:54:59Z

Возможные темы проекта

← Предыдущая версия		Версия от 23:54, 8 октября 2018
Строка 85:		Строка 85:

	Вычисление булевых функций многочленами рассматривается в области сложности вычислений в связи с тем, что эта модель помогает доказывать нижние оценки для ряда других вычислительных моделей, например, для булевых схем и разрешающих деревьев. Есть несколько разных моделей вычисления функций многочленами, например, точные и приближенные вычисления над действительными числами, вычисления по модулю, пороговые функции. Предлагается изучить некоторые из этих моделей и взаимосвязи между ними. Чтобы больше узнать об этой области можно посмотреть обзор by Richard Beigel http://knight.cis.temple.edu/~beigel/papers/polynomial-survey-structures.html		Вычисление булевых функций многочленами рассматривается в области сложности вычислений в связи с тем, что эта модель помогает доказывать нижние оценки для ряда других вычислительных моделей, например, для булевых схем и разрешающих деревьев. Есть несколько разных моделей вычисления функций многочленами, например, точные и приближенные вычисления над действительными числами, вычисления по модулю, пороговые функции. Предлагается изучить некоторые из этих моделей и взаимосвязи между ними. Чтобы больше узнать об этой области можно посмотреть обзор by Richard Beigel http://knight.cis.temple.edu/~beigel/papers/polynomial-survey-structures.html


	'''Тема проекта: Пороговые функции и пороговые схемы.'''		'''Тема проекта: Пороговые функции и пороговые схемы.'''
Строка 98:		Строка 99:

	Булевы схемы – одна из основных вычислительных моделей в теории сложности вычислений. Основной интерес к ней связан с доказательством нижних оценок сложности вычислений. Это большая тема и в ней можно либо изучить основы, либо подробно разобраться в каком-то конкретном направлении. Из доступных в Интернете источников в этой области можно посмотреть книгу by Ingo Wegener http://eccc.hpi-web.de/resources/pdf/cobf.pdf. Также на эту тему есть свежая книга “Boolean Function Complexity”, Stasys Jukna.		Булевы схемы – одна из основных вычислительных моделей в теории сложности вычислений. Основной интерес к ней связан с доказательством нижних оценок сложности вычислений. Это большая тема и в ней можно либо изучить основы, либо подробно разобраться в каком-то конкретном направлении. Из доступных в Интернете источников в этой области можно посмотреть книгу by Ingo Wegener http://eccc.hpi-web.de/resources/pdf/cobf.pdf. Также на эту тему есть свежая книга “Boolean Function Complexity”, Stasys Jukna.


			'''Тема проекта: Коммуникационная сложность и ее приложения.'''

			Ментор: [https://www.hse.ru/org/persons/134220270 Владимир Владимирович Подольский]

			Типичная задача коммуникационной сложности выглядит так. Есть два человека, которые хотят вычислить функцию f(x,y) на какой-то паре входов (x,y). При этом первый знает только x, а второй только y, то есть чтобы вычислить функцию им нужно обмениваться информацией. Какое минимальное количество информации им нужно передать друг другу, чтобы вычислить функцию? Например, x и y могут быть файлами, и участники вычисления хотят узнать, совпадают ли эти файлы. Коммуникационная сложность оказывается очень полезной при доказательстве нижних оценок сложности вычислений в множестве вычислительных моделей. Подробнее об этом можно почитать в обзоре by Eyal Kushilevitz http://www.cs.bris.ac.uk/probtcs08/materials/kushilevitz.pdf

Vpodolskii: /* Возможные темы проекта */

2018-10-08T23:53:53Z

Возможные темы проекта

@@ Строка 78: / Строка 78: @@
 Полиномиальный алгоритм исправления ошибок в коммуникационных протокола:
 Zvika Brakerski and Yael Tauman Kalai. Efficient interactive coding against adversarial noise. In FOCS, pages 160–166, 2012
 '''Тема проекта: Вычисление булевых функций многочленами.'''
@@ Строка 84: / Строка 85: @@
 Вычисление булевых функций многочленами рассматривается в области сложности вычислений в связи с тем, что эта модель помогает доказывать нижние оценки для ряда других вычислительных моделей, например, для булевых схем и разрешающих деревьев. Есть несколько разных моделей вычисления функций многочленами, например, точные и приближенные вычисления над действительными числами, вычисления по модулю, пороговые функции. Предлагается изучить некоторые из этих моделей и взаимосвязи между ними. Чтобы больше узнать об этой области можно посмотреть обзор by Richard Beigel http://knight.cis.temple.edu/~beigel/papers/polynomial-survey-structures.html

Vpodolskii в 23:50, 8 октября 2018

2018-10-08T23:50:39Z

← Предыдущая версия		Версия от 23:50, 8 октября 2018
Строка 78:		Строка 78:
	Полиномиальный алгоритм исправления ошибок в коммуникационных протокола:		Полиномиальный алгоритм исправления ошибок в коммуникационных протокола:
	Zvika Brakerski and Yael Tauman Kalai. Efficient interactive coding against adversarial noise. In FOCS, pages 160–166, 2012		Zvika Brakerski and Yael Tauman Kalai. Efficient interactive coding against adversarial noise. In FOCS, pages 160–166, 2012

			'''Тема проекта: Вычисление булевых функций многочленами.'''

			Ментор: [https://www.hse.ru/org/persons/134220270 Владимир Владимирович Подольский]

			Вычисление булевых функций многочленами рассматривается в области сложности вычислений в связи с тем, что эта модель помогает доказывать нижние оценки для ряда других вычислительных моделей, например, для булевых схем и разрешающих деревьев. Есть несколько разных моделей вычисления функций многочленами, например, точные и приближенные вычисления над действительными числами, вычисления по модулю, пороговые функции. Предлагается изучить некоторые из этих моделей и взаимосвязи между ними. Чтобы больше узнать об этой области можно посмотреть обзор by Richard Beigel http://knight.cis.temple.edu/~beigel/papers/polynomial-survey-structures.html

Vpodolskii в 23:25, 8 октября 2018

2018-10-08T23:25:39Z

← Предыдущая версия		Версия от 23:25, 8 октября 2018
Строка 8:		Строка 8:

	Отбор на проект по теоретической информатике производится по результатам собеседования. На собеседовании проверяется владение студентом знаниями и навыками, достаточными для успешной работы по выбранной теме, а также мотивация студента. В частности, в рамках описания мотивации от студента ожидаются примеры того, что он уже делал ранее, подтверждающие его интерес к теоретическим исследованиям (это может быть посещение факультатива, прохождение соответствующей летней практики, самостоятельное изучение какой-то области и т.д.).		Отбор на проект по теоретической информатике производится по результатам собеседования. На собеседовании проверяется владение студентом знаниями и навыками, достаточными для успешной работы по выбранной теме, а также мотивация студента. В частности, в рамках описания мотивации от студента ожидаются примеры того, что он уже делал ранее, подтверждающие его интерес к теоретическим исследованиям (это может быть посещение факультатива, прохождение соответствующей летней практики, самостоятельное изучение какой-то области и т.д.).

			== Критерии оценивания ==

			Критериями для выставления оценки по данному проекту является глубина освоения материала, уровень полученных новых результатов, качество изложения работы.

	== Контакты ==		== Контакты ==

Vpodolskii в 23:23, 8 октября 2018

2018-10-08T23:23:37Z

← Предыдущая версия		Версия от 23:23, 8 октября 2018
Строка 17:		Строка 17:
	== Возможные темы проекта ==		== Возможные темы проекта ==

	'''Тема проекта:		'''Тема проекта: Формулы для функций Шпрага-Гранди.'''
	Формулы для функций Шпрага-Гранди.'''

	Ментор: [https://www.hse.ru/org/persons/176125335 Владимир Александрович Гурвич]		Ментор: [https://www.hse.ru/org/persons/176125335 Владимир Александрович Гурвич]
Строка 41:		Строка 40:


	'''Тема проекта:		'''Тема проекта: Чувствительность булевых функций'''
	Чувствительность булевых функций'''

	Ментор: [https://www.hse.ru/org/persons/14007605 Михаил Николаевич Вялый]		Ментор: [https://www.hse.ru/org/persons/14007605 Михаил Николаевич Вялый]
Строка 58:		Строка 56:


	'''Тема проекта:		'''Тема проекта: Исправление ошибок в коммуникационных протоколах.'''
	Исправление ошибок в коммуникационных протоколах.'''

	Ментор: [https://www.hse.ru/org/persons/176000058 Александр Николаевич Козачинский]		Ментор: [https://www.hse.ru/org/persons/176000058 Александр Николаевич Козачинский]

Vpodolskii в 23:23, 8 октября 2018

2018-10-08T23:23:17Z

← Предыдущая версия		Версия от 23:23, 8 октября 2018
Строка 17:		Строка 17:
	== Возможные темы проекта ==		== Возможные темы проекта ==

	Тема проекта:		'''Тема проекта:
	~~'''~~Формулы для функций Шпрага-Гранди.'''		Формулы для функций Шпрага-Гранди.'''

	Ментор: [https://www.hse.ru/org/persons/176125335 Владимир Александрович Гурвич]		Ментор: [https://www.hse.ru/org/persons/176125335 Владимир Александрович Гурвич]
Строка 41:		Строка 41:


	Тема проекта:		'''Тема проекта:
	Чувствительность булевых функций		Чувствительность булевых функций'''

	Ментор: [https://www.hse.ru/org/persons/14007605 Михаил Николаевич Вялый]		Ментор: [https://www.hse.ru/org/persons/14007605 Михаил Николаевич Вялый]
Строка 58:		Строка 58:


	Тема проекта:		'''Тема проекта:
	Исправление ошибок в коммуникационных протоколах.		Исправление ошибок в коммуникационных протоколах.'''

	Ментор: [https://www.hse.ru/org/persons/176000058 Александр Николаевич Козачинский]		Ментор: [https://www.hse.ru/org/persons/176000058 Александр Николаевич Козачинский]