Логика и теория алгоритмов 4 семестр 2013-14 уч г, спец. Иу7 модуль 1: Теория алгоритмов






Скачать 63.38 Kb.
НазваниеЛогика и теория алгоритмов 4 семестр 2013-14 уч г, спец. Иу7 модуль 1: Теория алгоритмов
Дата публикации16.02.2015
Размер63.38 Kb.
ТипДокументы
l.120-bal.ru > Математика > Документы

логика и теория алгоритмов


4 семестр 2013-14 уч. г, спец. ИУ7

МОДУЛЬ 1: Теория алгоритмов


Виды аудиторных занятий
и самостоятельной работы


Сроки проведения или выполнения,
недели

Трудоемкость, часы

Примечание

Лекции

1-9

18




Практические занятия

1-3

6




Домашние задания текущие

1-3

6




Домашние задание «Теория алгоритмов»

2-5

5




Рубежный контроль по модулю

7

2



МОДУЛЬ 2: Булевы функции


Виды аудиторных занятий
и самостоятельной работы


Сроки проведения или выполнения,
недели

Трудоемкость, часы

Примечание

Лекции

10-13

8




Практические занятия

4-5

4




Домашние задания текущие

4-5

4




Дом. задание «Булевы функции»

7-10

10




Рубежный контроль по модулю

11

2



МОДУЛЬ 3: Математическая логика


Виды аудиторных занятий
и самостоятельной работы


Сроки проведения или выполнения,
недели

Трудоемкость, часы

Примечание

Лекции

14-22

18




Практические занятия

6-8

6




Домашние задания текущие

6-8

6




Дом. задание «Исчисление высказываний»

9-15

5




Рубежный контроль по модулю

16

2






Литература

Основная литература


Э. Мендельсон. Введение в математическую логику. – М.: Наука, 1971. – 320 с.

Б.А. Кушнер. Лекции по конструктивному математическому анализу. – М.: Наука, 1973. – 448 с.

А.А. Марков, Н.М. Нагорный. Теория алгорифмов. – М.: Наука, 1984. – 432 с.

А.И. Белоусов, С.Б. Ткачев. Дискретная математика.- 4-е изд. - М.: Изд. МГТУ им. Н.Э. Баумана, 2006. – 744 с.

А.Н. Колмогоров, А.Г. Драгалин. Математическая логика.- 3-е изд. – М.: КомКнига, 2006. – 240 с.

С.В. Яблонский. Введение в дискретную математику.- 3-е изд. – М.: Высшая школа, 2002. – 384 с.

Г.П. Гаврилов, А.А. Сапоженко. Задачи и упражнения по курсу дискретной математики. – М.: Наука, 1992. – 408 с.

И.А. Лавров, Л.Л. Максимова. Задачи по теории множеств, математической логике и теории алгоритмов. – М.: Наука, 1975. – 240 с.

Дополнительная литература


  1. Математическая логика в программировании: Сб. статей: Пер. с англ. – М.: Мир, 1991. – 408 с.

  2. Н.К. Верещагин, А. Шень. Языки и исчисления. – М.: МЦНМО, 2000. – 291 с.

  3. Н. Катленд. Вычислимость: введение в теорию рекурсивных функций. – М.: Мир, 1983. – 256 с.

  4. Ч. Чень, Р. Ли. Математическая логика и автоматическое доказательство теорем. – М.: Наука, 1983. – 360 с.

Лекции

Модуль 1. Теория алгоритмов


Лекция 1. Предпосылки возникновения математической логики и теории алгоритмов. Проблемы математического определения алгоритма и доказательства. Интуитивная концепция алгоритма. Понятие конструктивного объекта. Алфавит, слово, язык, словарная функция.

ОЛ-1, предисловие; ОЛ-2, введение; ОЛ-4, Д1.1, 7.1.

Лекция 2. Машины Тьюринга. Вычислимость по Тьюрингу. Тезис Тьюринга.

ОЛ-4, Д7.4; ОЛ-1, гл. 5, §2.

Лекция 3. Понятие нормального алгорифма Маркова. Основные примеры. Вычислимость по Маркову. Принцип нормализации.

ОЛ-1, гл. 5, §1; ОЛ-2, §1, пп. 1.1 – 1.4, 1.9.

Лекция 4. Эквивалентность алгорифмов. Теорема о переводе. Способы сочетания нормальных алгорифмов: теорема композиции.

ОЛ-1, гл. 5, §1; ОЛ-2, §1, пп. 1.5– 1.7.

Лекция 5. Способы сочетания нормальных алгорифмов: теоремы объединения, разветвления и повторения. Универсальный алгорифм.

ОЛ-1, гл. 5, §1; ОЛ-2, §1, пп. 1.7– 1.8.

Лекция 6. Разрешимые и перечислимые множества. Перечислимые множества и области применимости нормальных алгорифмов.

ОЛ-2, §§2, 3.

Лекция 7. Проблема применимости для нормальных алгорифмов и доказательство ее неразрешимости.

ОЛ-2, §§2, 3.

Лекция 8. Понятие частично рекурсивной функции. Подстановка, рекурсия, минимизация. Тезис Черча.

ОЛ-5, Дополнительные главы, гл. 2, §§3, 4; ОЛ-6, ч. I, гл.4, §§4-7; ДЛ-3, гл. 2, 3.

Лекция 9. Нумерация рекурсивных функций. S-m-n-теорема.

ДЛ-3, гл. 4.

Модуль 2. Булевы функции


Лекции 10-11. Булевы функции, равенство функций, суперпозиция, формулы. Реализация булевых функций стандартными формулами. ДНФ, СДНФ, минимизация в классе ДНФ.

ОЛ-4, 6.1 – 6.6.

Лекции 12-13. Полные и замкнутые множества булевых функций. Классы Поста. Критерий Поста функциональной полноты.

ОЛ-4 6.7.

Модуль 3. Математическая логика


Лекция 14. Понятие формальной теории. Аксиомы и правила вывода. Выводимость и доказуемость. Примеры теорий. Исчисление высказываний (ИВ).

ОЛ-1, гл. 1, §4..

Лекция 15. Теорема дедукции для ИВ. Правила естественного вывода. Примеры построения доказательств в ИВ.

ОЛ-1, гл. 1, §4.

Лекция 16. Полнота и непротиворечивость ИВ.

ОЛ-1, гл. 1, §4; ДЛ-2, гл.1, гл. 2: 2.1, 2.2.

Лекции 17–18. Понятие алгебраической системы. Операции и предикаты. Термы и формулы. Понятие интерпретации. Выполнимость, истинность и логическая общезначимость. Аксиомы и правила вывода исчисления предикатов 1-го порядка (ИП1).

ОЛ-4, 4.1; ОЛ-1, гл. 2, §§ 1 – 4.

Лекции 19-20. Теорема дедукции для ИП1. Примеры доказательств. Полнота и непротиворечивость ИП1. Теории первого порядка. Проблемы полноты и разрешимости.

ОЛ-1, гл. 2, §§ 3, 4, 8; ДЛ-2, 4.1 – 4.5.

Лекции 21–22. Метод резолюций для ИВ и ИП1.

ДЛ-4, гл. 5.

ПрАКТИЧЕСКИЕ ЗАНЯТИЯ


Занятия 1-2. Машины Тьюринга и нормальные алгорифмы.

ОЛ-4, задачи 7.37, 7.38; ОЛ-8, ч. III, §2; МРК.

Занятие 3. Рекурсивные функции.

ОЛ-7, гл. V, §2; ОЛ-8, ч. III, §1; ДЛ-3, упр. к главам 2 и 3; МРК.

Занятие 4. Построение минимальной ДНФ для булевой функции.

ОЛ-4, задачи 6.11 – 6.18.

Занятие 5. Полные множества булевых функций.

ОЛ-4, задачи 6.21-6.25.

Занятие 6-7. Исчисление высказываний.

ОЛ-1, упр. к. гл. 1; ДЛ-4, упр. к гл. 2, 5.

Занятие 8. Исчисление предикатов.

ОЛ-1, упр. к гл. 1; ДЛ-4, упр. к гл. 3, 5.

Контрольные мероприятия


Модуль 1 Теория алгоритмов (7 неделя, максимум 30 баллов, минимум 16 баллов).

Домашнее задание №1 «Теория алгоритмов» (выдача 2 неделя, прием 5 неделя).

Рубежный контроль по модулю 1 (7 неделя).

Модуль 2. Булевы функции ( 11 неделя, максимум 30 баллов, минимум 16 баллов).

Домашнее задание №2 «Булевы функции» (выдача 7 неделя, прием 10 неделя).

Модуль 3. Математическая логика (16 неделя, максимум 30 баллов, минимум 18 баллов).

Домашнее задание №3 «Исчисление высказываний» (выдача 9 неделя, прием 15 неделя).

Рубежный контроль по модулю (16 неделя).

Кафедра ФН-12
Ответственный по кафедре А.Н. Канатников
Автор документа А.И. Белоусов

Телефон (499) 263-62-88


Добавить документ в свой блог или на сайт

Похожие:

Логика и теория алгоритмов 4 семестр 2013-14 уч г, спец. Иу7 модуль 1: Теория алгоритмов iconРабочая программа дисциплины Математическая логика и теория алгоритмов Направление
Целями освоения дисциплины «Математическая логика и теория алгоритмов» являются получение теоретических знаний по основам математическая...

Логика и теория алгоритмов 4 семестр 2013-14 уч г, спец. Иу7 модуль 1: Теория алгоритмов iconРабочая программа составлена в соответствии с требованиями фгос впо...
Дёгтев А. Н. Теория алгоритмов. Учебно-методический комплекс. Рабочая программа для студентов направления 010100. 62 – математика,...

Логика и теория алгоритмов 4 семестр 2013-14 уч г, спец. Иу7 модуль 1: Теория алгоритмов iconПрограмма дисциплины Математическая логика и теория алгоритмов Для...
Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления 230400. 62 «Информационные...

Логика и теория алгоритмов 4 семестр 2013-14 уч г, спец. Иу7 модуль 1: Теория алгоритмов iconМетодические указания к выполнению лабораторных работ по дисциплине...
Практикум содержит набор лабораторных работ по предмету «теория алгоритмов» во время проведения которых изучаются: основные принципы...

Логика и теория алгоритмов 4 семестр 2013-14 уч г, спец. Иу7 модуль 1: Теория алгоритмов iconА. Л. Гудков 16 января 2012 г
«Математическая логика и теория алгоритмов» является формирование представлений о методах и моделях описания предметной и проблемной...

Логика и теория алгоритмов 4 семестр 2013-14 уч г, спец. Иу7 модуль 1: Теория алгоритмов iconРабочая программа дисциплины Математическая логика и теория алгоритмов
Федеральное государственное автономное образовательное учреждение высшего профессионального образования

Логика и теория алгоритмов 4 семестр 2013-14 уч г, спец. Иу7 модуль 1: Теория алгоритмов iconУчебно-методический комплекс по дисциплине «Математическая логика и теория алгоритмов»
Сперанский Д. В., доктор технических наук, профессор кафедры «Высшая и прикладная математика»

Логика и теория алгоритмов 4 семестр 2013-14 уч г, спец. Иу7 модуль 1: Теория алгоритмов iconМатематическая логика и теория алгоритмов
Большое внимание уделено практическим аспектам обсуждаемых понятий: автоматизации логического вывода, проверки корректности программ,...

Логика и теория алгоритмов 4 семестр 2013-14 уч г, спец. Иу7 модуль 1: Теория алгоритмов iconРоссийской Федерации Федеральное государственное бюджетное образовательное...
Изучение дисциплины базируется на курсах “Информатика”, “Дискретная математика”, “Математическая логика и теория алгоритмов”, “Структуры...

Логика и теория алгоритмов 4 семестр 2013-14 уч г, спец. Иу7 модуль 1: Теория алгоритмов iconРабочая программа составлена в соответствии с требованиями фгос впо...
Дёгтев А. Н. Теория алгоритмов. Учебно-методический комплекс. Рабочая программа для студентов направления 010200. 62 – математика...

Вы можете разместить ссылку на наш сайт:


Литература


При копировании материала укажите ссылку ©ucheba 2000-2015
контакты
l.120-bal.ru
..На главную