Сайт использует сервис веб-аналитики Яндекс Метрика с помощью технологии «cookie». Пользуясь сайтом, вы даете согласие на использование данной технологии.
Английский термин Theoretical computer science, который принято переводить как "теоретическая информатика", выглядит парадоксально. Компьютер практически полезен, кто бы сомневался — но можно ли его изучать теоретически? Я попытаюсь рассказать о разных примерах, когда именно теоретические (математические) вопросы и ответы на них оказались существенными и с практической точки зрения. В зависимости от пожеланий слушателей и времени мы попробуем обсудить что-то из следующего: общая идея алгоритма и алгоритмической неразрешимости, универсальность (хранимая программа), языки описания мира (пример: реляционные базы), практические отходы (конечные автоматы, контекстно-свободные грамматики), вероятностные алгоритмы, теория кодирования, конкретные быстрые алгоритмы, NP-полнота и граница между возможным и невозможным, отсутствие алгоритма как ресурс (криптография и др), философия науки и простейшие описания. Александр Шень — ассоциированный сотрудник международной лаборатории теоретической информатики.
