Город: Санкт-Петербург Новосибирск Казань Язык: Русский English
Что: Лекция
Когда: Четверг, 26 октября 2017, 17:00–20:10
Где: Физический корпус КФУ, ауд. 305

Описание

Представления булевых функций: таблицы истинностей, деревья решений, КНФ, ДНФ, формулы в базисе AND-OR-NOT, ветвящиеся программы, булевы схемы.

Моделирование машин Тьюринга булевыми схемами. Класс NP, полные задачи. NP-полнота задачи SAT. Материалы: конспект курса Обзорный курс по теоретической информатике

Деревья решений, как доказательство невыполнимости формулы. Принцип Дирихле. Доказательство нижних оценок с помощью игры. Связь с методом резолюций. Материалы: конспект курса Сложность пропозициональных доказательств