• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Контакты

Адрес: 125319, г. Москва, 
Кочновский проезд, д. 3 (станция метро "Аэропорт").

Телефон: +7 (495) 772-95-90 *12332

Email: computerscience@hse.ru

 

Руководство

Декан Аржанцев Иван Владимирович

Первый заместитель декана Вознесенская Тамара Васильевна

Заместитель декана по научной работе и международному сотрудничеству Объедков Сергей Александрович

Заместитель декана по учебно-методической работе Самоненко Илья Юрьевич

Заместитель декана по развитию и административно-финансовой работе Плисецкая Ирина Александровна

Образовательные программы
Бакалаврская программа

Прикладная математика и информатика

4 года
Очная форма обучения
110/80/15
110 бюджетных мест
80 платных мест
15 платных мест для иностранцев
RUS
Обучение ведётся на русском языке
Бакалаврская программа

Программа двух дипломов НИУ ВШЭ и Лондонского университета "Прикладной анализ данных"

4 года
Очная форма обучения
70/12
70 платных мест
12 платных мест для иностранцев
ENG
Обучение ведётся на английском языке
Бакалаврская программа

Программная инженерия

4 года
Очная форма обучения
80/70/15
80 бюджетных мест
70 платных мест
15 платных мест для иностранцев
RUS
Обучение ведётся на русском языке
Магистерская программа

Анализ данных в биологии и медицине

2 года
Очная форма обучения
15/5/2
15 бюджетных мест
5 платных мест
2 платных места для иностранцев
RUS/ENG
Обучение ведётся на русском и английском языках
Магистерская программа

Науки о данных

2 года
Очная форма обучения
55/15/6
55 бюджетных мест
15 платных мест
6 платных мест для иностранцев
RUS/ENG
Обучение ведётся на русском и английском языках
Магистерская программа

Системная и программная инженерия

2 года
Очная форма обучения
25/5/8
25 бюджетных мест
5 платных мест
8 платных мест для иностранцев
ENG
Обучение ведётся на английском языке
Магистерская программа

Системное программирование

2 года
Очная форма обучения
15/5/2
15 бюджетных мест
5 платных мест
2 платных места для иностранцев
RUS
Обучение ведётся на русском языке
Магистерская программа

Статистическая теория обучения

2 года
Очная форма обучения
20/5/4
20 бюджетных мест
5 платных мест
4 платных места для иностранцев
ENG
Обучение ведётся на английском языке
Магистерская программа

Финансовые технологии и анализ данных

2 года
Очная форма обучения
35/3
35 платных мест
3 платных места для иностранцев
RUS/ENG
Обучение ведётся на русском и английском языках
Статья
Infinite transitivity, finite generation, and Demazure roots

Arzhantsev I., Kuyumzhiyan K., Zaidenberg M.

Advances in Mathematics. 2019. Vol. 351. P. 1-32.

Статья
Bias in False Discovery Rate Estimation in Mass-Spectrometry-Based Peptide Identification

Sulimov P., Voronkova A., Danilova Y. et al.

Journal of Proteome Research. 2019. Vol. 18. No. 5. P. 2354-2358.

Статья
Compression of recurrent neural networks for efficient language modeling

Grachev A., Ignatov D. I., Savchenko A.

Applied Soft Computing Journal. 2019. Vol. 79. P. 354-362.

Глава в книге
Numerical Pattern Mining Through Compression

Makhalova T., Kuznetsov S., Napoli A.

In bk.: 2019 Data Compression Conference Proceedings. IEEE, 2019.

Теория вычислений

Информация о преподавателях

Первая часть курса, относящаяся к формальным языкам, будет прочитана А.А. Рубцовым, научным сотрудником лаборатории теоретической информатики. Остальные части курса будут прочитаны кем-то из сотрудников лаборатории теоретической информатики (https://cs.hse.ru/big-data/tcs-lab/) и их коллег  из списка ниже:

  • Н. К. Верещагин, заведующий лабораторией
  • М.Н. Вялый, ведущий научный сотрудник
  • В.А. Гурвич, ведущий научный сотрудник
  • В.В. Подольский, старший научный сотрудник
  • А.Х. Шень, партнёр лаборатории
  • С. Л. Кузнецов, сотрудник департамента анализа данных и искусственного интеллекта

С вопросами по курсу можно обращаться к Владимиру Владимировичу Подольскому vpodolskii@hse.ru и к Александру Александровичу Рубцову arubtsov@hse.ru.

Факультатив «Теория вычислений» является введением в классические темы теоретической информатики. Изложение во многом следует книге Майкла Сипсера «Introduction to the Theory of Computation», одной из лучших в этой области. Сипсер является одним из ведущих специалистов в области теоретической информатики и деканом по науке MIT.

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

Центральной темой курса является NP-полнота. Слова «P» и «NP» можно было услышать в разговорах о задачах тысячелетия: за разделение этих двух классов обещают $1 000 000 (как и за доказательство их совпадения). Однако, не смотря на невозможность решения этого вопроса в обозримом будущем, изучение NP полноты полезно в том числе и для практики: многие алгоритмы шифрования используют свойства задач из класса NP;  также при работе на практике полезно выяснить, что поставленная задача NP-полна, поэтому эффективного решения искать не стоит, а значит стоит уточнить эту задачу или искать приближённые решения.

Также будут изучены и другие базовые классы сложности вычислений, такие как L, NL, PSPACE и полиномиальная иерархия. Курс не имеет жёсткой программы — содержание может варьироваться в зависимости от подготовки слушателей и их интересов, однако не будет выходить за пределы книги Сипсера.

Курс рассчитан на студентов 2-4 курсов, но может быть также интересен студентам магистратуры и аспирантам, интересующимся теоретической информатикой и в частности теорией вычислений. Предполагается, что слушатели уже знакомы с машинами Тьюринга или вычислимыми функциями.

Критерии оценки знаний и формула оценивания 

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

Оценки за каждое из аттестационных мероприятий выставляются по десятибалльной системе. Итоговая оценка вычисляется по формуле:

Оитог = Онак*0,2  + Оэкз*0,8

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

План занятий

Каждую неделю будет проходить лекция и семинар по её материалу. Изложение соответствует книге M. Sipser «Introduction to the Theory of Computation». Мы приведём примерный план курса — реальный план может отличаться в зависимости от начальной подготовки слушателей, их интересов и пожеланий, однако мы не выйдем за пределы книги Сипсера. 

Лекции 1-2: регулярные языки

Лекции 3-4: контекстно свободны

Лекции 4-7: классы P и NP; NP-полные задачи

Лекции 8-12: классы L, NL, PSPACE, полиномиальная иерархия

Расписание:
29.01 - ауд. 509
время - с 13.40 до 16.30
с 05.02 по 19.03 - ауд. 400 - 3 модуль
с 02.04 по 21.05 – ауд. 402 – 4 модуль
31 мая с 16.40 до 19.30 - ауд. 219
7 июня с 16.40 до 19.30 - ауд. 505