Рабочая программа дисциплины математическая логика и теория алгоритмов (наименование дисциплины)



Скачать 187.7 Kb.
Дата08.11.2012
Размер187.7 Kb.
ТипРабочая программа
Министерство образования и науки Российской Федерации
Государственное образовательное учреждение высшего профессионального образования

«Новосибирский государственный университет» (НГУ)
Факультет информационных технологий

УТВЕРЖДАЮ

_______________________

« ___» _____________ 20___г.

РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ

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

(наименование дисциплины)

НАПРАВЛЕНИЕ ПОДГОТОВКИ 230100 «ИНФОРМАТИКА И ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА»

Квалификация (степень) выпускника

Бакалавр
Форма обучения очная

Новосибирск

2011

Программа дисциплины «Математическая логика и теория алгоритмов» составлена в соответствии с требованиями ФГОС ВПО к структуре и результатам освоения основных образовательных программ бакалавриата по математическому и естественнонаучному циклу по направлению подготовки «Информатика и вычислительная техника», а также задачами, стоящими перед Новосибирским государственным университетом по реализации Программы развития НГУ.
Автор: д.ф.-м.н., доцент Пальчунов Д.Е.
Факультет информационных технологий

Кафедра общей информатики

1. Цели освоения дисциплины (курса)

Дисциплина (курс) «Математическая логика и теория алгоритмов» имеет своей целью ознакомление студентов с основами теории множеств, теории моделей, теории доказательств и теории вычислимости. Основной целью освоения дисциплины является: приобретение студентами теоретических знаний и навыков решения задач по теории множеств, логике высказываний, логике предикатов, исчислению высказываний и исчислению предикатов, теории моделей, теории алгоритмов и теории вычислимости; приобретение студентами навыков и компетенций по формализации на строгом математическом языке знаний, относящихся к различным предметным областям, возникающих в этих областях проблем и задач; овладение методами построения дискретных моделей предметных областей.
2. Место дисциплины в структуре образовательной программы

Дисциплина (курс) «Математическая логика и теория алгоритмов» относится к вариативной части цикла математических и естественнонаучных дисциплин ОП бакалавра.
Содержание дисциплины является обязательным минимум для последующих курсов: «Дискретная математика», «Введение в теорию кодирования», «Логические основы программирования», «Методы трансляции и компиляции», «Объектно-ориентированное программирование», «Объектно-ориентированный анализ и дизайн», «Операционные системы», «Базы данных», «Логические методы в инженерии знаний», «Формальные методы программной инженерии», «Анализ алгоритмов», «Интеллектуальные системы».
3.
Компетенции обучающегося, формируемые в результате освоения дисциплины:


Дисциплина участвует в формировании следующих компетенций:

ОК-1

владеет культурой мышления, способен к обобщению, анализу, восприятию информации, постановке цели и выбору путей ее достижения

ОК-2

умеет логически верно, аргументировано и ясно строить устную и письменную речь

ОК-6

стремится к саморазвитию, повышению своей квалификации и мастерства

ОК-10

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

ОК-11

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

ПК-26

Владеет теоретическими основами программирования, основами логического и декларативного программирования

ПК-28

Владеет понятиями синтаксиса и семантики формальных языков. Владеет навыками формального представления содержательных знаний средствами формальных языков

ПК-65

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

ПК-66

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



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

  • Знать основные понятия и теоремы из теории множеств, логики высказываний, логики предикатов, теории доказательств, теории моделей, теории алгоритмов и теории вычислимости;

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

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


4. Структура и содержание дисциплины

Общая трудоемкость дисциплины составляет 6 зачетных единиц, 216 часов.






п/п


Раздел

дисциплины

Семестр

Неделя семестра

Виды учебной работы, включая самостоятельную работу студентов и трудоемкость (в часах)

Формы текущего контроля успеваемости

(по неделям семестра)

Форма промежуточной аттестации

(по семестрам)














Лекции


Семинары

Самостоятельная работа

Экзамен




1

Основы теории множеств

1

1

2

2

-

-

Тест

2


Логика высказываний

1

2-3

4

4

1

-

Тест

3

Логика предикатов

1

4

2

2

-

-

Тест

4

Основы теории алгоритмов

1

5-6

4

4

1

-

Тест

5

Отношения и функции.

1

7

2

2

1

-

Тест

6

Мощность множества

1

8

2

2

1

-

Тест

7

Булевы алгебры

1

9-10

4

4

1

-

Тест

8

Секвенциальное исчисление высказываний.

1

11-12

4

4

1

-

Тест

9

Семантика исчисления секвенций.

1

13-14

4

4

1

-

Тест

10

Семантика исчисления секвенций.

1

15-16

4

4

1

-

Тест

11

Экзамен

1

19-21

-

-

-

36




12

Гомоморфизм и изоморфизм алгебраических систем.

2

24-25

4

4

1

-

Тест

13

Секвенциальное исчисление предикатов

2

26-27

4

4

-

-

Тест

14

Теорема о полноте

2

28-29

4

4

1

-

Тест

15

Исчисление предикатов гильбертовского типа

2

30

2

2

-

-

Тест

16

Основы теории моделей

2

31

2

2

1

-

Тест

17

Машины Тьюринга

2

32-33

4

4

1

-

Тест

18

Универсальные рекурсивные функции

2

34-35

4

4

1

-

Тест

19

Клиниевская нумерация

2

36

2

2

1

-

Тест

20

Рекурсивные и рекурсивно-перечислимые множества



2

37-38

4

4

1

-

Тест

21

Алгоритмически разрешимые и неразрешимые проблемы

2

39

2

2

1

-

Тест

22

Экзамен




41-43










36







ВСЕГО







64

64

16

72

216 часов

Содержание разделов и тем курса:

1 семестр

  • Основы теории множеств

Множества и операции над ними. Простейшие теоретико-множественные тождества.

  • Логика высказываний

Язык логики высказываний. Понятие формулы. Таблицы истинности. Эквивалентность формул. Связь теоретико-множественных тождеств и тождеств логики высказываний. Основные тождества логики высказываний и теории множеств. Нормальные формы. Приведение формулы к СДНФ и СКНФ.

  • Логика предикатов

Понятие алгебраической системы, алгебры, модели. Примеры. Термы и формулы логики предикатов. Истинность формулы на модели. Тождественно истинные и выполнимые формулы. Семантическая эквивалентность формул. Основные тождества логики предикатов.

  • Основы теории алгоритмов

Понятие алгоритма. Вычислимые функции, разрешимые и перечислимые множества. Счётность множества вычислимых функций, существование невычислимых функций и неразрешимых множеств. Машины Тьюринга. Функции, вычислимые на машинах Тьюринга. Примитивно-рекурсивные, общерекурсивные и частично-рекурсивные функции.

  • Отношения и функции.

Предпорядок, отношения эквивалентности и частичного порядка. Эквивалентность и разбиение, фактор-множество. Максимальные и минимальные, наибольшие и наименьшие элементы, точная верхняя и нижняя грани. Понятие решетки.

  • Мощность множества.

Теорема Кантора-Бернштейна, теорема Кантора. Счётные множества. Счётность множества слов в конечном алфавите. Континуум. Несчётность множества вещественных чисел. Равномощность множества вещественных чисел и множества всех подмножеств множества натуральных чисел. Бесконечность класса бесконечных мощностей. Континуум-гипотеза и обобщённая континуум-гипотеза. Ординальные и кардинальные числа.

  • Булевы алгебры

Множество-степень, понятие и основные свойства булевой алгебры. Примеры. Атомные и безатомные элементы булевых алгебр. Конечные булевы алгебры, теорема Стоуна для конечных булевых алгебр.

  • Секвенциальное исчисление высказываний.

Секвенциальное исчисление высказываний. Понятие вывода. Допустимые правила вывода.

  • Семантика исчисления секвенций.

Теорема о корректности. Теорема о подстановке. Теорема о замене. Теорема о существовании КНФ. Теорема о полноте исчисления секвенций. Теорема об адекватности. Исчисление высказываний гильбертовского типа.
2 семестр

  • Гомоморфизм и изоморфизм алгебраических систем.

Гомоморфизм и изоморфизм алгебраических систем. Подсистемы. Отношение конгруэнтности, фактор-система, общая формулировка теоремы о гомоморфизмах (без доказательства).

  • Секвенциальное исчисление предикатов

Секвенциальное исчисление предикатов, аксиомы и правила вывода. Теорема о корректности. Допустимые правила вывода. Теорема о замене. Вывод основных эквивалентностей. Приведение формулы к предваренной нормальной форме.

  • Теорема о полноте

Полные теории. Теорема о существовании модели. Теорема Гёделя о полноте и теорема компактности Мальцева. Теорема Мальцева о расширении. Понятие о нестандартных моделях. Существование нестандартной модели арифметики.

  • Исчисление предикатов гильбертовского типа

Исчисление предикатов гильбертовского типа. Теорема о дедукции (без доказательства). Теорема об эквивалентности гильбертовского и секвенциального исчислений предикатов (без доказательства).

  • Основы теории моделей

Обогащение модели константами. Элементарная и полная диаграммы. Подмодели и расширения, связь с универсальными и экзистенциальными формулами. Элементарные расширения и подмодели, элементарные вложения. Критерий элементарности вложения. Теоремы Ливенгейма-Скулема. Парадокс Скулема. Аксиоматизируемые классы. Теория класса и класс теории. Конечно аксиоматизируемые классы. Характеризация классов, замкнутых относительно подмоделей и расширений. Интерполяционная теорема Крейга (без доказательства) и её следствия. Явная и неявная определимость. Теорема Бета об определимости (без доказательства).

  • Машины Тьюринга

Правильно вычислимые функции на машинах Тьюринга. Теорема о правильной вычислимости частично-рекурсивных функций. Кодировка машин Тьюринга. Теорема о нормальной форме Клини. Эквивалентность классов вычислимых функций. Тезис Чёрча.

  • Универсальные рекурсивные функции

Универсальные рекурсивные функции. Несуществование универсальной примитивно рекурсивной функции и универсальной общерекурсивной функции, существование универсальной частично рекурсивной функции.

  • Клиниевская нумерация

Клиниевская нумерация. s-m-n теорема. Теорема о неподвижной точке. Теорема о рекурсии. Теорема Райса.

  • Рекурсивные и рекурсивно-перечислимые множества

Операции над рекурсивными и рекурсивно перечислимыми множествами. Теорема Поста. Теорема о проекции. Теорема об эквивалентных определениях рекурсивно-перечислимых множеств. Теорема о графике. Существование рекурсивно-перечислимого, но не рекурсивного множества. Неразрешимость проблемы остановки программы.

  • Алгоритмически разрешимые и неразрешимые проблемы

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

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

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

Текущий контроль осуществляется в форме тестов – в течение 5 минут вначале каждого семинара студенты выписывают по памяти 3-4 определения по пройденной теме. Тесты стоятся на основе формулировок определений и теорем.
6. Оценочные средства для текущего контроля успеваемости, промежуточной аттестации по итогам освоения дисциплины и учебно-методическое обеспечение самостоятельной работы студентов
Вопросы к экзамену (1 семестр):

  1. Множества, операции над множествами.

  2. Логика высказываний: таблицы истинности, понятия формулы, тождественно истинной, тождественно ложной, выполнимой и опровержимой формулы.

  3. Логика высказываний: таблицы истинности, понятия формулы, эквивалентности формул.

  4. Выражение теоретико-множественных операций через логические связки

  5. ДНФ, КНФ, СДНФ, СКНФ

  6. Понятие алгебраической системы

  7. Термы и формулы логики предикатов

  8. Истинность формул на модели

  9. Семантическая эквивалентность формул

  10. Предваренная нормальная форма

  11. Отношения и функции

  12. Свойства бинарных отношений

  13. Отношения эквивалентности.

  14. Отношения порядка. Упорядоченные множества

  15. Точная нижняя грань и точная верхняя грань. Решетки.

  16. Определение булевой алгебры. Примеры булевых алгебр.

  17. Свойства булевых алгебр.

  18. Атомные и безатомные булевы алгебры

  19. Теорема Стоуна для конечной булевой алгебры.

  20. Равномощные множества. Теорема Кантора-Бернштейна.

  21. Конечные и бесконечные множества. Теорема Кантора.

  22. Счетные множества

  23. Континуальные множества

  24. Континуум гипотеза

  25. Ординалы и кардиналы.

  26. Машина Тьюринга

  27. ЧРФ, ПРФ, ОРФ.

  28. Канторовская нумерация.

  29. Секвенциональное исчисление высказываний

  30. Семантика исчисления секвенций. Теорема о корректности.

  31. Теорема о замене в исчислении высказываний

  32. Теорема о полноте секвенционального исчисления высказываний

  33. Исчисление высказываний гильбертовского типа.

  34. Гомоморфизмы, изоморфизмы.

  35. Подмодель.

  36. Теорема о существовании наименьшей подмодели

  37. Теорема о модели, порожденной множеством замкнутых термов

  38. Сохранение истинности формул на подмоделях

  39. Отношение конгруэнции. Теорема о факторизации

  40. Теорема о сильных эпиморфизмах

  41. Основная теорема о гомоморфизмах

  42. Секвенциональное исчисление предикатов

  43. Семантика исчисления секвенций. Теорема о корректности

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

  45. Приведение формулы к предваренной нормальной форме

  46. Противоречивые, непротеречивые множества формул. Теории, полные теории


Вопросы к экзамену (2 семестр):

  1. Противоречивые, непротиворечивые множества формул. Теории, полные теории.

  2. Теорема о существовании модели. Случай с равенством.

  3. Теорема о существовании модели. Случай без равенства

  4. Теорема Мальцева о компактности

  5. Теорема о полноте

  6. Теорема Мальцева о расширении

  7. Теорема о нестандартной арифметике

  8. Исчисление предикатов гильбертовского типа.

  9. Нумерация машин Тьюринга

  10. Основная теорема о вычислимых функциях

  11. Тезис Черча

  12. Универсальные функции

  13. Не существование универсальной ПРФ и ОРФ.

  14. Существование универсальной ОРФ

  15. Клиниевские универсальные функции

  16. s-m-n-теорема

  17. Теорема о неподвижной точке

  18. Теорема Райса.

  19. Рекурсивные и рекурсивно перечислимые множества. Операции над РМ и РПМ.

  20. Теорема Поста

  21. Теорема об эквивалентных определениях РПМ

  22. Теорема о существовании РПМ не РМ

  23. Теорема о составном определении.

  24. Геделевская нумерация термов и формул сигнатуры Пеано

  25. Предложение о перечислимости тождественно истинных формул

  26. Предложение о перечислимости множества доказуемых формул

  27. Теорема о полной перечислимой теории

  28. Формальная арифметика Пеано

  29. Теорема о представимости ОРФ в арифметике Пеано

  30. Теорема Геделя о неразрешимости

  31. Теорема Черча о неразрешимости

  32. Теорема Геделя о неполноте.


7. Учебно-методическое и информационное обеспечение дисциплины
а) основная литература:

  1. Ершов Ю.Л., Палютин Е.А. Математическая логика, М.: Наука. 1987. –336 с.

  2. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов, М.: Физмалит. 2001. 256 с.


б) дополнительная литература:

  1. Гончаров С.С., Дроботун Б.Н., Никитин А.А. Методические аспекты изучения алгебраических систем высшем учебном заведении. Новосибирск: НГУ, 2007.

  2. Клини С. Математическая логика. М.:Мир, 1973, 480 с.

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

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

  5. Верещагин Н.К., Шень А. Языки и исчисления. 2004.

  6. Успенский В.А., Верещагин Н.К., Плиско В.Е. Вводный курс математической логики. 2004. 128 с.

  7. Лавров И.А. Математическая логика. Учебное пособие для вузов. М.: Академия, 2006.

  8. Колмогоров А.Н., Драгалин А.Г. Математическая логика. Серия "Классический университетский учебник". Изд.3, 2006, 240 с.


в) программное обеспечение и Интернет-ресурсы: не требуется.
8. Материально-техническое обеспечение дисциплины не требуется
Рецензент (ы) _________________________
Программа одобрена на заседании ____________________________________________

(Наименование уполномоченного органа вуза (УМК, НМС, Ученый совет)

от ___________ года.




Похожие:

Рабочая программа дисциплины математическая логика и теория алгоритмов (наименование дисциплины) iconРабочая программа дисциплины Математическая логика и теория алгоритмов Направление подготовки 230700 Прикладная информатика
Целями освоения дисциплины «Математическая логика и теория алгоритмов» являются получение теоретических знаний по основам математическая...
Рабочая программа дисциплины математическая логика и теория алгоритмов (наименование дисциплины) iconУчебная программа Дисциплины р2 «Математическая логика и теория алгоритмов»
Фгос впо, содействует формированию мировоззрения и системного мышления. Целью преподавания дисциплины «Математическая логика и теория...
Рабочая программа дисциплины математическая логика и теория алгоритмов (наименование дисциплины) iconРабочая программа дисциплины Математическая логика и теория алгоритмов

Рабочая программа дисциплины математическая логика и теория алгоритмов (наименование дисциплины) iconРабочая программа дисциплины математическая логика и теория алгоритмов
Рабочая программа обсуждена на заседании кафедры вычислительной техники “ ” 2002 г., протокол №
Рабочая программа дисциплины математическая логика и теория алгоритмов (наименование дисциплины) iconПрограмма дисциплины дпп. 04 Математическая логика и теория алгоритмов
Цель дисциплины: ознакомление студентов с основными приемами символической логики, используемыми при исследовании структуры математических...
Рабочая программа дисциплины математическая логика и теория алгоритмов (наименование дисциплины) iconРабочая программа по курсу «Математическая логика и теория алгоритмов» для специальности 090102 «Компьютерная безопасность»
«Математическая логика и теория алгоритмов», рекомендованной Министерством образования Российской Федерации в 2000 году для специальностей...
Рабочая программа дисциплины математическая логика и теория алгоритмов (наименование дисциплины) iconУчебно-методический комплекс учебной дисциплины Математическая логика и теория алгоритмов Специальность 032200. 00 Физика
Рабочая программа составлена на основании Государственного образовательного стандарта высшего профессионального образования по специальности...
Рабочая программа дисциплины математическая логика и теория алгоритмов (наименование дисциплины) iconРабочая программа дисциплины теория чисел (наименование дисциплины )
Теория чисел имеет дело с доступными непосредственному восприятию объектами – с целыми рациональными числами. Поэтому в теории чисел...
Рабочая программа дисциплины математическая логика и теория алгоритмов (наименование дисциплины) iconРабочая программа дисциплины математическая логика и теория алгоритмов
Для подготовки бакалавров по направлению 552800 – “Информатика и вычислительная техника” и дипломированных специалистов по направлению...
Рабочая программа дисциплины математическая логика и теория алгоритмов (наименование дисциплины) iconПрограмма-минимум кандидатского экзамена по специальности 01. 01. 06 «Математическая логика, алгебра и теория чисел» по физико-математическим наукам
В основу настоящей программы положены следующие дисциплины: математическая логика; алгебра; теория чисел
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org