Опубликована: 05.04.2011 | Уровень: для всех | Стоимость: 490.00 руб. | Длительность: 14 дней
Курс посвящен знакомству с такими фундаментальными математическими понятиями, как вычисления и доказательство.
Курс предусматривает изучение теории алгоритмов и аксиоматического подхода к математической логике.
Необходимые знания: Изучение курса предполагает предварительное изучение курса Кузнецова О.П. "Дискретная математика".

План занятий

ЗанятиеЗаголовок <<Дата изучения
-
Лекция 1
Понятие алгоритма. Классификация алгоритмических моделей. Знакомство с машиной Тьюринга
В начале лекции рассказывается об истории возникновения математики, формировании понятий "Доказательство" и "Вычисление". Определяется понятие "Алгоритм", приводятся основные требования, предъявляемые к алгоритму. Во второй половине лекции рассказывается о классификации алгоритмических моделей, начинается знакомство с машинами Тьюринга.
Оглавление
-
Лекция 2
Машина Тьюринга. Вычислимость. Примеры. Способы задания
В начале лекции обсуждается понятие вычислимости. Далее приводится описание, способы задания, указываются особенности программирования машин Тьюринга (МТ). Рассматриваются основные операции над МТ, доказывается теорема о существовании универсальной МТ.
-
Лекция 3
Рекурсивные функции
Лекция посвящена введению в теорию рекурсивных функций. Дается определение, рассматриваются примеры, способы задания рекурсивных функций, формулируются и доказываются соответствующие теоремы.
-
Лекция 4
Разрешимые и перечисляемые множества. Введение в теорию конечных автоматов
Лекция состоит из двух частей. В первой части обсуждаются вопросы разрешимости и перечислимости множеств, сходимости алгоритмов, приводится формулировка теоремы Райса. Вторая часть лекции посвящена введению в теорию конечных автоматов (КА). Дается формальное определение КА, рассматриваются способы задания, примеры.
-
Тест 1
36 минут
-
Лекция 5
-
Лекция 6
Алгоритмические возможности конечных автоматов. Сети Петри
В лекции рассматривается понятие регулярного множества. Приводится формулировка теоремы Клини. Рассматривается блочное описание конечного автомата. Обсуждаются понятия композиции и декомпозиции. В заключение рассматриваются сети Петри.
Оглавление
-
Тест 2
36 минут
-
Лекция 7
-
Лекция 8
-
Тест 3
36 минут
-
Лекция 9
Логика. Исчисления высказываний и исчисление предикатов
В начале лекции рассказывается об истории возникновения понятия " Логика". Далее обсуждаются основные различия между исчислением высказываний и исчислением предикатов. Рассматриваются правила вывода Modus Ponens, приводятся примеры их использования.
-
Лекция 10
Метатеория. Введение в исчисление предикатов
В первой половине лекции обсуждается понятие метатеории и метатеорем. Приводится теорема о дедукции, ее доказательство, обратная теорема о дедукции. В завершение рассматривается пример. Вторая половина лекции посвящена введению в исчисление предикатов (ИП): рассматриваются основные определения и понятия, дается формальное определение ИП.
-
Лекция 11
Интерпретация и полнота исчисления предикатов
-
Лекция 12
Метод резолюций в исчислении высказываний и исчислении предикатов
Лекция целиком посвящена методу резолюций в исчислении высказываний и исчислении предикатов. Подробно излагается идея и суть метода, даются основные определения и понятия, на житейском примере разбирается алгоритм работы. В заключении рассматривается метод аналитических таблиц как альтернатива методу резолюций.
-
Тест 4
36 минут
-
5 часов
-