• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Бакалаврская программа «Прикладная математика и информатика»

Специализация Теоретическая информатика

Руководители специализации:
Шень Александр Ханиевич, к.ф.-м.н., старший научный сотрудник LIRMM CNRS (Лаборатории 
Национального центра научных исследований Франции в Монпелье) и Института проблем передачи информации РАН
Подольский Владимир Владимирович, к.ф.-м.н., руководитель департамента больших данных и информационного поиска ФКН НИУ ВШЭ, старший научный сотрудник лаборатории теоретической информатики НИУ ВШЭ, старший научный сотрудник Математического института им. В.А. Стеклова
 

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



Курсы специализации 3 года обучения

Курсы специализации 4 года обучения
Рекомендованные курсы по выбору
Семинары Международной лаборатории теоретической информатики 

 


 курсы специализации 3 года обучения (в 2018/19): 

1. Теория вычислений 
Лектор: Подольский Владимир Владимирович

Международная лаборатория теоретической информатики: Старший научный сотрудник, Департамент больших данных и информационного поиска: Доцент

 
Лектор: Баувенс Бруно Фредерик Л.

Доцент Департамента больших данных и информационного поиска

 
Курс читается: 1-2 модули 
Не всегда практическая задача, связанная с применением компьютеров, имеет чёткую математическую постановку. И даже если такая постановка есть, может оказаться, что в принципе не существует алгоритма, который решает соответствующую математическую задачу (она, как говорят, может быть алгоритмически неразрешимой). Наконец, задача может быть хотя и алгоритмически разрешимой, но вычислительно сложной - порой настолько, что с практической точки зрения она ничем не лучше алгоритмически неразрешимой.
Теория вычислений как раз и занимается такими вопросами. Общая теория вычислимости позволяет понять, является ли задача алгоритмически разрешимой (и классифицирует алгоритмически неразрешимые задачи). Теория сложности вычислений изучает, прежде всего, класс "реально разрешимых задач", который в первом приближении отождествляется с полиномиально разрешимыми задачами. К сожалению, центральная проблема (P=NP) остаётся нерешённой, но тем не менее удаётся получить множество интересных условных результатов (в предположении трудности этой или близких задач, некоторые другие задачи являются трудными).
Можно исследовать и более сложные ситуации, чем задачи разрешения: вместо того, чтобы узнавать, обладает ли исходное данное желаемым свойством, можно рассматривать интерактивный протокол, когда два участника обмениваются сообщениями (и имеют те или иные цели). Например, можно анализировать сложность игр, или сложность интерактивных доказательств (когда один участник должен убедить другого, что исходное данное обладает некоторым свойством), или криптографические задачи (когда два участника должны обменяться информацией, но так, чтобы внешний наблюдатель с ограниченными вычислительными ресурсами ничего не узнал), и так далее.
Чтобы преодолеть барьер, связанный с P=NP, можно рассматривать некоторые ограниченные классы алгоритмов или специальные модели вычислений. Скажем, легко (и важно!) проанализировать, какие задачи могут быть решены алгоритмами без внешней памяти (конечные автоматы) - они соответствуют так называемым регулярным выражениями. Или, напротив, можно исследовать только какой-то один аспект вычислений - например, количество битов, которыми обмениваются участники (считая, что сами вычисления нам ничего не стоят, а сложна лишь передача битов).
В целом, теория сложности вычислений расставляет (пусть не всегда и не везде) ориентиры для программиста - позволяя ему лучше рассчитать свои силы и понять, чего в принципе можно достичь и чего достичь нельзя

2. Сложность вычислений и логика в теоретической информатике 

Лектор: Верещагин Николай Константинович

Департамент больших данных и информационного поиска: Профессор

 
Курс читается: 3-4 модули
Теория вычислений и логика в их современном виде появились одновременно (и даже в работах одних и тех же людей - Гёделя, Чёрча, Тьюринга и других), и это не случайно: процесс формального вывода (применение разрешённых правил) и процесс вычисления (детерминированное применение разрешённых правил) по природе близки. Знаменитая теорема Гёделя (не все истинные утверждения формально доказуемы) означает на языке теории вычислений, что множество истинных утверждений неперечислимо - и в такой форме легко следует из классических результатов теории вычислений. Впоследствии появились и другие связи: логические теории можно использовать для доказательства свойств программ, классы сложности можно описывать в логических терминах, поэтому знакомство с основными понятиями и результатами логики входит в базовое образование программистов. Кое-что уже было в курсе дискретной математики - и в этом курсе мы пойдём дальше (и, в частности, докажем теорему Гёделя о неполноте).


 курсы специализации 4 года обучения : 

1. Автоматизированная проверка доказательств и верификация алгоритмов |  Automatic Proof Checking and Algorithm Verification  

Лектор: Кузнецов Степан Львович

Департамент анализа данных и искусственного интеллекта: Доцент





Курс читается: 1-2 модули  |  на английском языке
Modern mathematical proofs are sometimes too long and sophisticated for a human expert to analyse them in detail and guarantee their correctness. A similar issue can be observed in programming practice: big projects usually contain bugs, and testing is not always capable of finding them. A more reliable method is verification, i.e. a formal proof of a theorem stating that the program in question is correct w.r.t. a specification, which is also written in a formal language. Finally, there are mixed cases, in which bruteforce search on a computer is used to prove a mathematical statement (the classical example here is the four colour theorem). In such situations formal verification of the algorithm is needed to finish the proof.In this course we discuss formalisation of mathematical reasoning on a computer using one of such systems called Coq (http://coq.inria.fr/). The course also includes all necessary background from mathematical logic and theoretical computer science: intuitionstic logic, lambda calculus, type theory, the Curry - Howard correspondence, and also elements of functional programming (both in specialised functional languages, like OCaml and Haskell, and on top of standard imperative languages, like Python). Besides theoretical material, the course also includes practical activities.


 
2. Теория информации 

Верещагин Николай Константинович

Департамент больших данных и информационного поиска: Профессор

 
Курс читается: 1-2 модули
В науке не существует единого подхода к определению понятия информации. В разных областях это понятие трактуется по-разному. Имеются информация по Хартли, энтропия Шеннона, Колмогоровская сложность, коммуникационная сложность. Каждое из этих понятий отражает некоторую грань интуитивного понятия информации. В курсе будет рассказано об этих понятиях и как они применяются в решении разных задач.

3.  Методы теоретической информатики  |   A Theorist's Toolkit

Подольский Владимир Владимирович

Департамент больших данных и информационного поиска: Доцент

 
Курс читается: 3 модуль  |  на английском языке
Once some area arrives at the problems that are not clear how to solve, it becomes especially important not only to obtain new results, but also to develop new methods and techniques.
In recent decades Theoretical Computer Science had expanded substantially and the number of mathematical tools used in it in it rapidly increased. The goal of this course is to go through these tools and techniques, so that students can apply them when needed.
The plan is to discuss various results in different areas of Theoretical Computer Science specifically to consider various proof techniques.
Topics of the course include
1.    Probabilistic methods and Chernoff bound;
2.    Fourier analysis over finite fields, Boolean function analysis;
3.    Representation of Boolean functions by polynomials, polynomial method;
4.    Matrix theory and spectral techniques;
5.    Spectral graph theory;
6.    Linear programming as a proof technique



4. Выпуклое программирование и аппроксимационные алгоритмы

Вялый Михаил Николаевич

Департамент больших данных и информационного поиска: Профессор

 
Курс читается: 3 модуль
Приближенное решение оптимизационных задач всегда было важной частью теории оптимизации. На практике часто бывает так, что лучше быстро найти решение, отличающееся от оптимального на 1%, чем долго искать точное решение. Для многих трудных задач комбинаторной оптимизации существуют эффективные приближенные алгоритмы. Мощным средством построения таких алгоритмов является решение задач выпуклой оптимизации, ограничения которых ослабляют ограничения исходной задачи (релаксации).В курсе будет рассказано о самых важных алгоритмах такого типа, основанных на релаксациях к задачам линейного программирования (LP) и задачам полуопределенного программирования (SDP). Частным случаем SDP релаксаций является метод сумм квадратов (SOS алгоритмы), который приобрел в последние годы большую популярность. В курсе планируется также рассказать о возможностях этого метода.
 рекомендованные курсы по выбору : 

Теория вычислений (для студентов 3 и 4 курса) 
Математическая логика и сложность вычислений  (для студентов 3 курса)



↑  вернуться