RU / День 2 / 18:00 / Зал 1

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

В этом докладе мы расскажем об одном подходе к изучению теоретической информатики (а конкретнее, теории алгоритмов), при котором программирование на JavaScript становится основным видом деятельности учащегося. Мы пройдёмся по основным разделам теории и посмотрим, чем нам там поможет Javascript.

Для начала мы введём три модели вычислений (λ-исчисление, рекурсивные функции и машины Тьюринга), покрутим их немного, чтобы разобраться, что к чему, а потом попробуем применить к теории вычислимости (там доказывают существование неразрешимых задач) и теории сложности вычислений (там классифицируют задачи по объёмам требуемых для их решения ресурсов — времени и памяти). Не то чтобы Javascript позволяет проделывать основную работу в рамках теоретической информатики, но вот иллюстрировать важные понятия и приёмы он точно способен, именно для этого мы им и воспользуемся. А ещё будет много упражнений по программированию. На Javascript! Все на изучение теоретической информатики с нашим любимым языком программирования!

Виталий Брагилевский

Преподаватель функционального программирования, теории языков программирования и теории вычислений, член комитета по стандартизации языка программирования Haskell и наблюдательного комитета по разработке компилятора GHC языка Haskell, автор книги «Haskell in Depth» (Manning Publications).