Geum.ru

Учебно-методический комплекс дисциплины «Математическая логика и теория алгоритмов» специальности 230102 «Автоматизированные системы обработки информации и управления»

Вид материалаУчебно-методический комплекс

Содержание


Лист согласования
Математическая логика и теория алгоритмов
Цели и задачи дисциплины. требования к уровню освоения содержания учебной дисциплины.
Тематический план и содержание дисциплины
Раздел дисциплины
Раздел I. Основы математической логики
Тема 1. Логика высказываний
Тема 2. Функции алгебры логики
Тема 3. Приложения алгебры логики
Тема 4. Логика предикатов
Раздел II. Аксиоматические теории
Тема 5. Исчисление высказываний
Тема 6. Исчисление предикатов
Тема 7. Проблемы полноты и разрешимости формальных систем
Раздел III. Теория вычислимых функций
Тема 8. Формализация понятия алгоритма. Рекурсивные функции
Тема 9. Машины Тьюринга
Тема 10. Проблемы алгоритмической неразрешимости и сложности алгоритмов
Итого за 3 семестр
Подобный материал:
1   2   3   4   5




Начальник методического отдела БГТУ

___________________/ Емельянов В.Ю. /




САНКТ-ПЕТЕРБУРГ

2008 г.


ЛИСТ СОГЛАСОВАНИЯ


Рабочая программа составлена на основании государственного образовательного стандарта ВПО и рассмотрена на заседании кафедры И7


“__” _______ 2008 г Заведующий кафедрой __________________/ С.Д. Шапорев /


Программа согласована в учебно-методической комиссии факультета «И»


"__"_____2008 г. Председатель МК ________________________/ В.В. Смирнов /


СОГЛАСОВАНО:


Заведующий кафедрой И3 _________________________________________ /О.С. Ипатов /


"__"______2008 г.


Заведующий кафедрой И5 _________________________________________ /Н.Н. Смирнова /


"__"______2008 г.


Учебная дисциплина обеспечена основной литературой


Директор библиотеки БГТУ___________________________/ Н. В. Сесина /


"__"_____2008 г


Выдержка из ГОС ВПО РФ (2000 г.)

по направлению 230100 Информатика и вычислительная техника

для специальности 230102 Автоматизированные системы обработки информации и управления
по минимуму содержания программы дисциплины, входящей в цикл общих математических и естественнонаучных дисциплин из перечня обязательных дисциплин федерального компонента ГОС


ЕН.Ф.01.04 Общее число часов: 100


МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ


Логика высказываний; логика предикатов; исчисления; непротиворечивость; полнота; синтаксис и семантика языка логики предикатов. Клаузальная форма. Метод резолюций в логике предикатов. Принцип логического программирования. Темпоральные логики; нечеткая и модальные логики; нечеткая арифметика; алгоритмическая логика Ч. Хоара. Логика высказываний. Логическое следование, принцип дедукции. Метод резолюций. Аксиоматические системы, формальный вывод. Метатеория формальных систем. Понятие алгоритмической системы. Рекурсивные функции. Формализация понятия алгоритма; Машина Тьюринга. Тезис Черча; Алгоритмически неразрешимые проблемы. Меры сложности алгоритмов. Легко и трудноразрешимые задачи. Классы задач P и NP. NP – полные задачи. Понятие сложности вычислений; эффективные алгоритмы. Основы нечеткой логики. Элементы алгоритмической логики.

ЦЕЛИ И ЗАДАЧИ ДИСЦИПЛИНЫ.
ТРЕБОВАНИЯ К УРОВНЮ ОСВОЕНИЯ СОДЕРЖАНИЯ УЧЕБНОЙ ДИСЦИПЛИНЫ.

Преподавание данной дисциплины, предусмотренное обязательным минимумом содержания основной образовательной программы специальности 230102, преследует и реализует следующие цели и возможности:
  • развивает способности студентов к строгому абстрактно-формальному логическому и алгоритмическому мышлению;
  • является существенной частью общего математического образования студентов, ориентирует их на использование методов математической логики при решении прикладных задач.

Вопросы, изучаемые в курсе математической логики и теории алгоритмов, базируются на общематематических курсах, изучаемых студентами на предыдущих семестрах, в частности, в курсах математического анализа, вычислительной и дискретной математики.

В результате изучения дисциплины студенты должны:

знать основные понятия и факты исчисления высказываний, алгебры логики, исчисления предикатов, теории аксиоматических систем и доказательств;

знать определение и основные характеристики алгоритма, понятия, факты и проблемы теории алгоритмов;

уметь проводить формально-логические построения на основе теории и формул математической логики;

уметь определять и строить вычислимые функции на основе рекурсивных алгоритмов;

уметь строить машины Тьюринга, вычисляющие заданные функции и по программе машины Тьюринга определять её характеристики;

представлять значение и строение математических теорий как аксиоматических теорий, построенных на основе выбранных систем аксиом, строить интерпретации формул теории и её модели;

уметь строить доказательства теорем в наиболее значимых теориях исчисления высказываний и предикатов.

ТЕМАТИЧЕСКИЙ ПЛАН И СОДЕРЖАНИЕ ДИСЦИПЛИНЫ

( с распределением общего бюджета времени в часах)


КУРС
СЕМЕСТР


Раздел

дисциплины,

содержание
ВСЕГО
АУДИТОРНЫЕ
Самостоятельная

работа студентов

Лекции
Аудиторный

практикум

Лабораторный

практикум

2
3
Раздел I. Основы математической логики

42
12
16



14

Тема 1. Логика высказываний

Высказывание как первичное понятие алгебры логики. Основные операции над высказываниями. Пропозициональные связки. Истинностные функции. Формулы алгебры высказываний, их виды. Метод истинностных таблиц. Три группы равносильных формул. Равносильные преобразования формул. Полные системы связок. Понятие о нечётких и модальных логиках.

6
2
2



2

Тема 2. Функции алгебры логики

Понятие булевой функции (функции двузначной логики). Элементарные булевы функции, логические связки. Формулы алгебры логики, функции, их реализующие. Основные эквивалентные формулы алгебры логики. Метод истинностных таблиц. Представление произвольной функции алгебры логики в виде формулы алгебры логики. Свойства совершенства. Закон двойственности и двойственные операции. Нормальные формы. Алгоритмы приведения к совершенным дизъюнктивной и конъюнктивной нормальным формам. Полиномы Жегалкина. Двойственность. Принцип двойственности. Теорема Поста. Проблемы полноты и разрешимости.

16
4
6



6

Тема 3. Приложения алгебры логики

Релейно-контактные схемы, их математическое описание и методы построения. Решение логических задач.
10
2
4



4

Тема 4. Логика предикатов

Кванторные операции как обобщения операций конъюнкции и дизъюнкции. Предикаты. Синтаксис и семантика языка логики предикатов. Формулы логики предикатов. Свободные и связанные переменные. Интерпретации, выполнимость и общезначимость формул логики предикатов. Равносильности логики предикатов. Приведенная нормальная форма. Общезначимость и выполнимость формул логики предикатов. Эквивалентные формулы логики предикатов. Примеры распознавания общезначимости в частных случаях.

Запись математических предложений на языке логики предикатов. Запись математических определений. Формулировка математических теорем. Построение противоположных утверждений. Доказательство методом от противного. Формулировка обратных и противоположных теорем. Формулировка необходимых и достаточных условий.
10
4
4



2

Раздел II. Аксиоматические теории

34
12
10



12







Тема 5. Исчисление высказываний

Задание формальной аксиоматической теории: алфавит, система аксиом, основные и производные правила вывода. Основные понятия теории доказательств: гипотеза, следствие, вывод, теорема, разрешимая и неразрешимая теория. Построение аксиоматической теории исчисления высказываний. Основные и производные правила вывода. Понятие выводимости формул. Правило одновременной подстановки, правило сложного заключения, правило силлогизма, правило контрпозиции, правило снятия двойного отрицания. Формулы и правила, выводимые из совокупности формул. Правила вывода теории исчисления высказываний. Теорема дедукции, обобщение теоремы дедукции. Закон перестановки посылок, законы соединения и разъединения посылок. Примеры доказательств некоторых теорем теории исчисления высказываний. Теории исчисления высказываний Клини, Гильберта-Аккермана, Россера, интуиционистская.
18
6
6



6

Тема 6. Исчисление предикатов

Построение аксиоматической теории исчисления предикатов первого порядка. Правила вывода теории исчисления предикатов. Коллизия переменных в формулах исчисления предикатов. Правила вывода. Замена переменных: а) замена переменного высказывания, б) замена переменного предиката, в) замена свободной предметной переменной, г) правило переименования связанных предметных переменных. Правила связывания квантором. Теорема дедукции. Эквивалентные и дедуктивно эквивалентные формулы. Непротиворечивость исчисления предикатов. Полнота в узком и широком смысле.

Примеры доказательств некоторых теорем. Примеры теорий первого порядка. Метод резолюций в логике предикатов.

12
4
4



4

Тема 7. Проблемы полноты и разрешимости формальных систем

Метаязык и метатеория. Проблемы разрешимости, полноты и непротиворечивости формальных аксиоматических теорий. Теоремы о полноте и непротиворечивости теории исчисления высказываний. Непротиворечивость теорий первого порядка. Теорема Гёделя о полноте.


4
2






2

Раздел III. Теория вычислимых функций

26
10
8



8

Тема 8. Формализация понятия алгоритма. Рекурсивные функции

Эффективная вычислимость функции. Уточнение понятия алгоритма. Разрешимые и перечислимые множества. Примитивная рекурсия. Примитивно-рекурсивные функции. Оператор минимизации. Частично-рекурсивные функции. Общерекурсивные функции. Примитивная рекурсивность и общерекурсивность некоторых арифметических функций. Тезис Чёрча. Словарные множества и функции. Операции над словарными функциями. Словарная примитивная рекурсия.

8
4
2



2

Тема 9. Машины Тьюринга

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

14
4
6



4







Тема 10. Проблемы алгоритмической неразрешимости и сложности алгоритмов

Алгоритмически неразрешимые проблемы. Меры сложности алгоритмов. Легко и трудноразрешимые задачи. Классы задач P и NP. NP – полные задачи. Понятие сложности вычислений; эффективные алгоритмы.

4
2






2

Итого за 3 семестр:
102
34
34



34