JavaScript на службе у теоретической информатики

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

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

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

Комментарий программного комитета:

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