Bodrenko.com
Bodrenko.org

Учебные дисциплины на сайте Bodrenko.org
Портабельные Windows-приложения на сайте Bodrenko.com
"Геометрические методы математической физики" Компьютерные науки Математика и информатика Векторный и тензорный анализ Теория игр Аналитическая геометрия и линейная алгебра Римановы многообразия Элементы вариационного исцисления Дифференциальная геометрия и топология "Геометрия подмногообразий" Дополнительные главы дифференциальной геометрии "Диффиренциальные уравнения на многообразиях" "Дифференциальная геометрия и топология кривых" Bodrenko.com Bodrenko.org

Bodrenko.org

 

 

Федеральное агентство по образованию Российской Федерации

ГОУ ВПО "ВОЛГОГРАДСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ"

ФАКУЛЬТЕТ МАТЕМАТИКИ И ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ 

КАФЕДРА ФУНДАМЕНТАЛЬНОЙ ИНФОРМАТИКИ И

ОПТИМАЛЬНОГО УПРАВЛЕНИЯ




 
    УТВЕРЖДЕНО                                                          УТВЕРЖДАЮ
   Ученым советом                                                    Декан факультета
     факультета
Протокол №        от                                                 _____________ А.Г. Лосев
"______ " ___________  2008   г.                            "______ " ___________  2008   г.
 
 




Программа учебной дисциплины
" Математическая логика и теория алгоритмов "
по направлению подготовки бакалавров  
 "Информатика и вычислительная техника", "Информационные системы и технологии",  

          по направлению подготовки специалистов

 Факультет математики и информационных технологий.

552800 Информатика и вычислительная техника.

 230200  Информационные системы и технологии. 

 
Составитель рабочей программы:
 
Доцент кафедры ФИОУ, к.ф.- м. н., доцент   Бодренко А.И. _____________
 



Волгоград  2008 г.

 

 

 

 

 

 

I. Аннотация.

 

Рабочая программа составлена на основании государственного образовательного стандарта высшего профессионального образования и учебных планов математического факультета ВолГУ по направлению подготовки бакалавров «ИВТ, ИСТ, АСОИОУ».

 

Дисциплина «Математическая логика и теория алгоритмов» изучается в 6-ом  семестре. Программа курса рассчитана на 36 часов лекций и 36 часов практики в первом семестре. Курс завершается экзаменом.

 

Преподавание дисциплины «Математическая логика и теория алгоритмов»  имеет целью формирование у студентов общей математической культуры, формализации понятий алгоритма и логического обоснования.

 

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

 

В разделе III данной программы учебной дисциплины представлена программа экзамена.

 

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

 

II. Содержание учебной дисциплины.

 

1.     Объем дисциплины и виды учебной работы

 

 

п/п

Вид учебной работы

Всего часов

1.

Аудиторные занятия (всего)

72

   1.1.

Лекции

36

   1.2.

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

36

2.

Самостоятельная работа (всего)

28

3.

Общая трудоемкость дисциплины

100

4.

Вид итогового контроля

Экзамен

 

 

 

 

 

 

 

 

 

2.     Тематический план дисциплины.

п/п

 

Кол-во часов

Лекции

Практ. Занятия

1.

ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ

12

12

2.

ИСЧИСЛЕНИЕ ПРЕДИКАТОВ

12

12

3.

ТЕОРИЯ АЛГОРИТМОВ

12

12

 

Всего часов

36

36

 

 

 

3.     Содержание лекций и практических занятий

 

Тема 1 Лекции -12 ч., практики 12 ч., контрольная работа 1

Логические исчисления, модели: исчисление высказываний (ИВ); аксиомы; правило вывода; тождественная истинность. Непротиворечивость ИВ; теорема о полноте ИВ.

 

Тема 2 Лекции-12 ч., практики 12 ч., контрольная работа 1.

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

 

 

Тема 3 Теория алгоритмов

Лекции-12 ч., практики 12 ч., контрольная работа 1.

Вычислимые функции: машины Тьюринга; вычислимые функции; тезис Черча; примеры вычислимых функций; рекурсивные, рекурсивно-перечислимые множества и их алгоритмическая характеристика. Теорема Поста; примеры алгоритмически неразрешимых проблем; неразрешимость проблем самоприменимости, применимости. Операции суперпозиции и примитивной рекурсии; примитивно-рекурсивные функции; Операции суперпозиции и примитивной рекурсии; примитивно-рекурсивные функции; операция минимизации; частично-рекурсивные функции; вычислимость частично-рекурсивных функций; частичная рекурсивность вычислимых функций; формула Клини.

 

План практических занятий по курсу “ Математическая логика и теория алгоритмов”

[1] Игошин В.И.  “Задачи и упражнения по математической логике и  теории алгоритмов” ,

 М.: Издательский  центр «Академия», 2007. — 304 с.

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

 [3] Игошин В.И.  “Математическая логика и теория алгоритмов“,  М.: Издательский центр «Академия», 2008. — 448 с.

Тема 1. АЛГЕБРА ВЫСКАЗЫВАНИЙ.  Задачи  [2] Часть 2 §1. 1-47,  §3. 1-48,

1.1-1.71  [1] стр.6-40; (1-3-ая неделя)                                                                                                                                                                      1. Основные понятия алгебры высказываний.
2. Высказывания и операции над ними.

3. Формулы алгебры высказываний.

4. Тавтологии алгебры высказываний.

5.  Логическое следование. 

6. Равносильность формул.

7.  Упрощение систем высказываний.
 Тема 2. ФОРМАЛИЗОВАННОЕ ИСЧИСЛЕНИЕ  ВЫСКАЗЫВАНИЙ. 

Задачи  8.1-8.27  [1] стр.143-161; (4-8-ая неделя)                                                                                                                                                                     

1. Построение формализованного исчисления высказываний

и исследование системы аксиом на независимость.

2. Построение выводов из аксиом.

3. Построение выводов из гипотез.

4. Теорема о дедукции и её применение.

5. Производные правила вывода и их применение.

6.  Независимость системы аксиом.

Тема 3. ЛОГИКА ПРЕДИКАТОВ

Задачи  [2] Часть 2 §4. 1-47

9.1-9.71  [1] стр.162-204; (9-13-ая неделя)                                                                                                         1. Основные понятия логики предикатов.

2. Понятие предиката и операции над предикатами.

3. Множество  истинности предиката.

4. Равносильность и следование предикатов.

5. Формулы логики предикатов, их интерпретация и классификация.

6. Равносильность формул логики предикатов.

7. Тавтологии логики предикатов. 

8. Равносильные преобразования формул.

9. Проблемы разрешимости для общезначимости и выполнимости формул.

10. Логическое следование формул логики предикатов.

Тема 4.   ЭЛЕМЕНТЫ ТЕОРИИ АЛГОРИТМОВ.

Задачи  12.1-12.38, 13.1-13.16, 14.1-14.29  [1] стр.221-256; (14-18-ая неделя)                                                             

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

2. Применение машин Тьюринга к словам.

3. Конструирование машин Тьюринга.

4.  Вычислимые по Тьюрингу функции.

5. Рекурсивные функции.

6. Примитивно рекурсивные функции.

7. Примитивно рекурсивные предикаты.

8. Нормальные алгоритмы Маркова.

9. Марковские подстановки.

10. Нормальные алгоритмы и их применение к словам.

11. Нормально вычислимые функции.

 

 

4 Контрольные работы

 

Контрольная работа 1.

1)      Построить вывод теоремы  в ИВ.

2)      Является ли формула теоремой ИВ

3)      Является ли выражение формулой ИВ

 

Контрольная работа 2.

 

1) Является ли формула ИП:

общезначимой

2)  Является ли формула ИП: общезначимой.

 

3)  Постройте вывод формулы в ИП.

 

Контрольная работа 3.

 

1)      Постройте машину Тьюринга, вычисляющую оператор копирования

2)      Покажите примитивную рекурсивность множества четных  чисел.

3)      Является ли множество теорем исчисления высказываний рекурсивным.

 

 

 

III.           Программа экзамена.

 

Баллы ставятся по результатам трех контрольных работ ( по 20 баллов каждая). Практические задачи контрольных работ представлены в пособиях [2], [3], [4], [5] пункта  V.

.

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

[1] Игошин В.И.  “Задачи и упражнения по математической логике и  теории алгоритмов” ,

 М.: Издательский  центр «Академия», 2007. — 304 с.

 [2] Игошин В.И.  “Математическая логика и теория алгоритмов“,  М.: Издательский центр «Академия», 2008. — 448 с.

Тема 1. АЛГЕБРА ВЫСКАЗЫВАНИЙ.  Задачи  1.1-1.71  [1] стр.6-40;

1. Основные понятия алгебры высказываний.
2. Высказывания и операции над ними.

3. Формулы алгебры высказываний.

4. Тавтологии алгебры высказываний.

5.  Логическое следование. 

6. Равносильность формул.

7.  Упрощение систем высказываний.
 Тема 2. ФОРМАЛИЗОВАННОЕ ИСЧИСЛЕНИЕ  ВЫСКАЗЫВАНИЙ. 

Задачи  8.1-8.27  [1] стр.143-161;

1. Построение формализованного исчисления высказываний

и исследование системы аксиом на независимость.

2. Построение выводов из аксиом.

3. Построение выводов из гипотез.

4. Теорема о дедукции и её применение.

5. Производные правила вывода и их применение.

6.  Независимость системы аксиом.

Тема 3. ЛОГИКА ПРЕДИКАТОВ

Задачи  9.1-9.71  [1] стр.162-204;

1. Основные понятия логики предикатов.

2. Понятие предиката и операции над предикатами.

3. Множество  истинности предиката.

4. Равносильность и следование предикатов.

5. Формулы логики предикатов, их интерпретация и классификация.

6. Равносильность формул логики предикатов.

7. Тавтологии логики предикатов. 

8. Равносильные преобразования формул.

9. Проблемы разрешимости для общезначимости и выполнимости формул.

10. Логическое следование формул логики предикатов.

Тема 4.   ЭЛЕМЕНТЫ ТЕОРИИ АЛГОРИТМОВ.

Задачи  12.1-12.38, 13.1-13.16, 14.1-14.29  [1] стр.221-256;

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

2. Применение машин Тьюринга к словам.

3. Конструирование машин Тьюринга.

4.  Вычислимые по Тьюрингу функции.

5. Рекурсивные функции.

6. Примитивно рекурсивные функции.

7. Примитивно рекурсивные предикаты.

8. Нормальные алгоритмы Маркова.

9. Марковские подстановки.

10. Нормальные алгоритмы и их применение к словам.

11. Нормально вычислимые функции.

 

 

 

 

IV.           Учебно–методическое обеспечение

 

Основные пособия по курсу «математическая логика и теория алгоритмов» для специальности «математика» - [3], [4], [5].  Методы решения задач представлены в учебниках [2] и [3]. Кроме этого, имеются электронные обучающие программы и электронные учебники.

 

 

 

V.               Литература

1. Яблонский С.В. Введение в дискретную математику. - М. 1987

2. Гаврилов Г. П., Сапоженко А.А. "Сборник задач по дискретной математике". - М. 1989.

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

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

5. Верещагин Н.К., Шень А. Вычислимые функции. М.: МЦНМО, 1999