Чем занимается теоретическая информатика: первое знакомство с наукой21.07.2022 15:48

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

Теория вычислительного обучения посвящена созданию и изучению систем машинного обучения. Искусственный интеллект нашел много применений в жизни: с его помощью распознают ранние симптомы рака, улучшают изображения и звук, переводят с одного языка на другой в режиме реального времени. Однако мы до сих пор не понимаем, почему работает машинное обучение, зачастую такие системы вообще называют «черным ящиком». 

Другой крупный раздел теоретической информатики — теория алгоритмов. Многие из нас в школе строили блок-схемы: нужно помыть посуду, какая последовательность действий — алгоритм — поможет это сделать? В какой последовательности нужно брать тарелки со стола, тереть их губкой, ставить в шкаф? Теория алгоритмов решает как раз такие задачи — конечно, и на более абстрактном уровне.

Еще один раздел теоретической информатики — это теория сложности вычислений. Здесь различные задачи сравнивают по вычислительной сложность — по объему ресурсов, необходимому для решения. Задача считается сложной, если ее решение требует большого количества вычислительных ресурсов, независимо от используемого алгоритма.

Одна из главных задач теоретической информатики — задача P vs NP или проблема перебора. Математический институт Клэя включил проблему перебора в список семи задач тысячелетия — наиболее сложных проблем из разных областей математики.

Стандартный пример такой задачи: есть несколько целых чисел и одно пороговое число. Нас спрашивают, можно ли выбрать часть целых чисел и сложить их так, чтобы получилось пороговое число. 

Чем эта задача интересна? Мы не умеем решать ее эффективно за полиномиальное время, и если вдруг научимся, то по аналогии решим еще много других задач, имеющих совершенно разные формулировки. Мы хотим научиться решать их быстро и эффективно. Однако большинство ученых предполагают, что решать такие задачи за полиномиальное время невозможно, но доказать это мы не сможем. 

Хотя нам пока не удается решить проблему перебора, мы изучаем разные ослабления этого вопроса, сравниваем разные сложностные классы. Такой подход позволяет нам придумывать новые методы. Благодаря нему те задачи, которые были нерешаемы сорок лет назад, сейчас стали значительно понятнее. 

Бывает, что задачи, которые давно никто не мог решить, решаются довольно просто. Например, какая-нибудь задача долго «висела», а по факту решение оказалось коротким, подготовленный человек может понять его за 15 минут.

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

Для занятий теоретической информатикой самое главное — это интерес. Эта область, да и математика в целом — достаточно специфическая. Зачастую нельзя предугадать, как именно будет выглядеть результат решения задачи, и это может раздражать. Особенно это касается студентов, которые только начинают заниматься наукой. Может быть так, что в решении простой на первый взгляд задачи не получится продвинуться и за месяцы ежедневных размышлений, а, может, решение окажется таким простым, что появится очень быстро и не удостоится отдельной публикации. 

Оптимальный вариант — это задачи умеренной сложности с посильными решениями, но, к сожалению, нельзя узнать заранее, к какому виду относится задача, не потратив на ее анализ и решение определенное время. При этом не нужно быть гением — важно иметь абстрактное мышление и спокойно относиться к интеллектуальным тупикам. 

Для первого контакта с областью лучше начинать не с самой информатики, а познакомиться с книгами Верещагина и Шеня «Начала теории множеств», «Языки и исчисления» и «Вычислимые функции». По ним можно составить впечатление об области: они легко читаются, но при этом весьма содержательны. Николай Константинович Верещагин, кстати, на факультете компьютерных наук Вышки заведует лабораторией теоретической информатики. 

После этого можно прочитать стандартный учебник, но он довольно старый. Есть и более новая книга — она сложнее, но математически подготовленный человек с ней вполне справится. После первичного знакомства с областью стоит обратить внимание на курсы и книги Тима Ровгардена.