Лекция профессора Охотина

29 марта в среду в 18:10 в ауд. 3107 НГУ (новый корпус) состоится лекция профессора Александра Сергеевича Охотина (СПбГУ) для студентов ММФ и ФИТ на тему: "Об отрицании и необратимости. Опыт теоретической информатики".

Аннотация

Теоретическая информатика изучает математические идеи, лежащие в основе технологий обработки информации. В лекции будут рассмотрены два класса задач, типичных для этой области науки. Первая задача — это выражение отрицания в некоторой формальной модели — например, в вычислительном устройстве или в логической системе. Если в определённой модели выразимо некое свойство (такое, как "в графе есть путь"), то вопрос состоит в том, можно ли в этой же модели выразить отрицание того же свойства ("в графе нет пути")? Вторая задача — о логической обратимости вычислений.

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