Виталий Брагилевский — JavaScript на службе у теоретической информатики

Ближайшая конференция — HolyJS 2025 Spring, 7—8 апреля, Москва + online. Подробности и билеты: https://jrg.su/gxfN4t — — . . При изучении теоретической информатики можно использовать самые разнообразные инструменты. Пожалуй, чаще всего нужно доказывать теоремы по индукции, но программированию место тоже можно найти. В этом докладе мы расскажем об одном подходе к изучению теоретической информатики (а конкретнее, теории алгоритмов), при котором программирование на JavaScript становится основным видом деятельности учащегося. Мы пройдёмся по основным разделам теории и посмотрим, чем нам там поможет Javascript. Для начала мы введём три модели вычислений (λ-исчисление, рекурсивные функции и машины Тьюринга), покрутим их немного, чтобы разобраться, что к чему, а потом попробуем применить к теории вычислимости (там доказывают существование неразрешимых задач) и теории сложности вычислений (там классифицируют задачи по объёмам требуемых для их решения ресурсов времени и памяти). Не то чтобы Javascript позволяет проделывать основную работу в рамках теоретической информатики, но вот иллюстрировать важные понятия и приёмы он точно способен, именно для этого мы им и воспользуемся. А ещё будет много упражнений по программированию. На Javascript! Все на изучение теоретической информатики с нашим любимым языком программирования!