Фрагменты лекции от 12 апреля по теме "Теорема Поста"
Теорема Поста. Основные моменты доказательства достаточности критерия Поста
Пример полной системы, состоящей из одной функции f(x_1,x_2,x_3). Последовательное получения формул для отрицания и констант через функцию f(x_1,x_2,x_3). Демонстрация схем, сопровождающих эти формулы.
Продолжение исследования функции f(x_1,x_2,x_3) с предыдущих снимков. Получение формул для конъюнкции и дизъюнкции по лемме L. Демонстрация схем, сопровождающих эти формулы.
Пример полной системы, состоящей из двух функции f(x_1,x_2,x_3) и g(x_1,x_2,x_3). Заполнение таблицы Поста. Последовательное получения формул для констант и отрицания через функции f(x_1,x_2,x_3) и g(x_1,x_2,x_3)
Фрагменты лекции от 19 апреля
Алгоритм Краскала для отыскания минимального остова во взвешенном графе. Пример применения этого метода.
Пример применения метода Дейкстры для отыскания кратчайшего пути (между начальной и конечной вершинами графа).
Фрагменты лекции от 26 апреля
Задачи с лекции 3 мая
Фрагменты лекции от 17 мая. Подготовка к поточной контрольной работе -- разбор примерного варианта.
Задача на отыскание кратчайшего пути:
Задача на отыскание минимального остова:
Задача об оптимальном назначении:
Задача на построение максимального потока и отыскание минимального сечения:
