Theoretical computer science — сухое плавание? (Александр Шень)

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