Федеральное государственное бюджетное образовательное учреждение
Высшего профессионального образования
«Вологодский государственный технический университет»
(ВОГТУ)
УТВЕРЖДАЮ
Проректор по учебной работе
____________ А.Н. Тритенко
«___»______________ 2012 г.
РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ
Математическая логика и теория алгоритмов
Направление подготовки: 231000.62 – ПРОГРАММНАЯ ИНЖЕНЕРИЯ
Профиль подготовки: разработка программно-информационных систем
Квалификация (степень) выпускника: бакалавр
Форма обучения: очная
Факультет: электроэнергетический
Кафедра: автоматика и вычислительная техника
Вологда
2012 г.
Составители рабочей программы
Доцент, к.т.н., доцент _________________ /Андрианов И.А./
(должность, уч.степень, звание) (подпись)
Рабочая программа утверждена на заседании кафедры автоматики и вычислительной техники
Протокол заседания № ___от «__»___ 20__ г.
Заведующий кафедрой
«___»________20___г. _________________ /Сердюков Н.А./
(подпись)
Рабочая программа одобрена методическим советом электроэнергетического факультета.
Протокол заседания № ___от «__»___ 20__ г.
Председатель методического совета
«___»________20___г. _________________ /Бабарушкин В.А. /
(подпись)
1. ЦЕЛИ ОСВОЕНИЯ УЧЕБНОЙ ДИСЦИПЛИНЫ
Целями освоения учебной дисциплины «Математическая логика и теория алгоритмов» являются:
1. Изучение основных объектов, задач и методов математической логики и теории алгоритмов, а также способов их применения для решения различных задач в области программирования и информационных технологий.
2. Развитие у студентов логического и абстрактного мышления.
2. МЕСТО УЧЕБНОЙ ДИСЦИПЛИНЫВ СТРУКТУРЕ ООП ВПО
Дисциплина относится к математическому и естественнонаучному циклу ООП ВПО, изучается в 3 семестре.
Для освоения данной дисциплины как последующей необходимо изучение следующих дисциплин: «Информатика», «Построение и анализ алгоритмов», «Математика. Математический анализ». Взаимосвязь данной дисциплины с предшествующими отражена в матрице междисциплинарных связей.
Требования к «входным» знаниям, умениям и готовности студента, необходимым при освоении данной дисциплины и приобретенным в результате освоения предшествующих дисциплин, включают следующее:
знать: основные понятия теории множеств; системы счисления; способы представления и измерения информации; основы алгоритмизации; способы описания алгоритмов; понятие вычислительной сложности алгоритма и задачи.
уметь: выполнять программную реализацию алгоритма по его описанию на языке высокого уровня; выполнять расчёт асимптотических оценок сложности.
владеть: навыками программирования на языке высокого уровня; способами описания, основами построения и анализа алгоритмов.
Освоение данной дисциплины как предшествующей необходимо при изучении следующих дисциплин и практик: «Функциональное и логическое программирование», «Технологии хранения данных», «Объектно-ориентированное программирование», а также для выполнения выпускной квалификационной работы.
Взаимосвязь данной дисциплины с последующими отражена в матрице междисциплинарных связей.
КОМПЕТЕНЦИИ СТУДЕНТА, ФОРМИРУЕМЫЕ В РЕЗУЛЬТАТЕ ОСВОЕНИЯ УЧЕБНОЙ ДИСЦИПЛИНЫ/ ОЖИДАЕМЫЕ РЕЗУЛЬТАТЫОБРАЗОВАНИЯ И КОМПЕТЕНЦИИ СТУДЕНТА ПО ЗАВЕРШЕНИИ ОСВОЕНИЯ ПРОГРАММЫУЧЕБНОЙ ДИСЦИПЛИНЫ
В результате освоения дисциплины студент должен:
знать: основные понятия математической логики, логические законы, формальные теории, исчисления высказываний и предикатов 1-го порядка; основные понятия теории алгоритмов: интуитивная концепция алгоритма, уточнения понятия алгоритма (машины Тьюринга и нормальные алгоритмы Маркова), понятия вычислимости, разрешимости, перечислимости; основные неразрешимые массовые проблемы; быть готовым к использованию методов и инструментальных средств исследования объектов профессиональной деятельности (ПК-3);
уметь: доказывать формулы в исчислении высказываний и предикатов 1-го порядка; составлять программы машин Тьюринга и схемы нормальных алгоритмов Маркова для решения простых вычислительных задач; готовить презентации, оформлять научно-технические отчеты по результатам выполненной работы, публиковать результаты исследований в виде статей и докладов на научно-технических конференциях (ПК-5);
владеть: основамисоставления программнаязыке логического программирования Пролог; культурой мышления, способами обобщения, анализа, восприятия информации; математическими методами формальной логики (ПК-3).
4. СТРУКТУРА И СОДЕРЖАНИЕ УЧЕБНОЙ ДИСЦИПЛИНЫ(МОДУЛЯ)
Общая трудоемкость дисциплины составляет 4 ЗЕТ (144 часа), в том числе в семестрах:
| Семестр № | Трудоемкость | РПР, курсовая работа, курсовой проект | Форма промежуточной аттестации | ||||
| Всего | Аудиторная | СРС | Экз. | ||||
| ЗЕТ | час. | час. | час. | час. | |||
| лек. – 16 лаб. раб. – 16 прак. – 32 | курсовая работа | зачет |
Взаимосвязь тем в дисциплине отражает матрица межтематических связей. Элементы матрицы характеризуют последовательность изучения тем и факт принадлежности темы в соответствии с ее содержанием к опирающейся и опорной.
Распределение результатов обучения и компетенций по семестрам, темам учебной дисциплины с указанием видов учебной деятельности и их содержания, образовательных технологий, последовательности учебных недель, трудоемкости, форм текущего контроля и промежуточных аттестаций представлено в соответствующей таблице.
Матрица межтематических связей в дисциплине
| № п/п, наименование темы опорной | № п/п, наименование темы опирающейся | |||||||
| 1. Основные понятия математической логики | 2. Исчисление высказываний | 3. Логика предикатов | 4. Исчисление предикатов, формальные аксиоматические теории | 5. Основы теории алгоритмов. Нормальные алгоритмы Маркова | 6. Элементы теории множеств. Машина Тьюринга. | 7. Рекурсивные функции. | 8. Неразрешимые алгоритмические проблемы | |
| 1. Основные понятия математической логики | + | + | + | + | + | + | + | |
| 2. Исчисление высказываний | + | + | + | + | ||||
| 3. Логика предикатов | + | + | + | |||||
| 4. Исчисление предикатов, формальные аксиоматические теории | + | + | ||||||
| 5. Основы теории алгоритмов. Нормальные алгоритмы Маркова. | + | + | + | |||||
| 6. Элементы теории множеств. Машина Тьюринга. | + | + | ||||||
| 7. Рекурсивные функции. | + | |||||||
| 8. Неразрешимые алгоритмические проблемы |
| № темы п/п | Результаты обучения | Семестр, тема. Виды учебной деятельности. Краткое содержание | Образова-тельные технологии | *Неделя | Трудоем-кость, час | Форма текущего/ промежу-точного контроля | ||
| 3 семестр | ||||||||
| Тема:Основные понятия математической логики | ||||||||
| Знать и понимать: задачи, цель и предмет дисципли-ны; основные понятия математической логики, логические законы Уметь:строить формулы по таблицам истинности, проводить преобразования формул с использованием законов алгебры логики Владеть: методом минимизации логических формул | Лекция 1: Введение. Логика в математике и информатике. Логические парадоксы. Понятие высказывания, основные логические связки. Булева алгебра. Законы алгебры логики. Пропорциональные формулы. Функция истинности формулы. Отношение семантического следования и семантической равносильности формул. Выполнимые формулы и множества формул. Классификация формул. Проблема разрешения в логике высказываний. Нормальные формы. Алгоритмы нормализации. Переключательные схемы. | Мультимедиа | 1,2 | |||||
| СРС:Изучение материала лекции 1. | 1,2 | |||||||
| Практическая работа 1: Построение булевых формул и цифровых логических схем по таблицам истинности | 1,2 | Защита отчета | ||||||
| СРС:Подготовка отчета по практической работе 1. | 1,2 | Проверка | ||||||
| СРС:Выполнение курсовой работы | 1,2 | |||||||
| Лабораторная работа 1: Моделирование цифровых логических схем с помощью специализированного ПО | 1,2 | Защита отчета | ||||||
| СРС:Подготовка отчета по лабораторной работе 1. | 1,2 | Проверка | ||||||
| Тема:Исчисление высказываний | ||||||||
| Знать и понимать:основные понятия и теоремы исчисления высказываний Уметь: применять правила вывода и следствия теорем Владеть: навыками применения результатов данной теории для решения задач мат. логики | Лекция 2: Логические исчисления (аксиоматические теории): алфавит, язык теорем, множества аксиом и правил вывода. Выводимость, элементарные свойства выводимости. Язык, аксиомы и правила вывода исчисления высказываний (ИВ), примеры выводов. Теорема дедукции и производные правила вывода. Непротиворечивые множества формул и их свойства. Семантические признаки непротиворечивости и семантическая пригодность ИВ. Теорема о семантической полноте и ее следствия. Семантическая и синтаксическая полнота. Независимость аксиом и правил вывода. Неклассические логики – вводные понятия. | Мультимедиа | 3,4 | |||||
| СРС:Изучение материала лекции 2. | 3,4 | |||||||
| Практическая работа 2: преобразования и минимизация булевых формул с использованием законов алгебры логики. | 3,4 | Защита отчета | ||||||
| СРС:Подготовка отчета по практической работе 2. | 3,4 | Проверка | ||||||
| СРС:Выполнение курсовой работы | 3,4 | |||||||
| Лабораторная работа 2: преобразования и минимизация цифровых логических схем. | 3,4 | Защита отчета | ||||||
| СРС:Подготовка отчета по лабораторной работе 2. | 3,4 | Проверка | ||||||
| Тема:Логика предикатов | ||||||||
| Знать и понимать: понятие предиката, кванторы, формулы логики предикатов и их свойства Уметь: строить и понимать формулы логики предикатов Владеть: правилами эквивалентных преобразований формул логики предикатов | Лекция 3: Понятие предиката. Логические и квантовые операции над предикатами. Область истинности предиката и теоретико-множественный смысл операций над предикатами. Понятие формулы логики предикатов. Запись суждений формулами логики предикатов. Алфавит и сигнатура языка логики предикатов. Термы и формулы. Синтаксис термов и формул. Подстановка терма в формулу. Интерпретация языка в предметной области. Значения термов и предметных переменных. Семантика термов и формул. Функция истинности формулы. Выполнимые и общезначимые формулы. Семантическое исследование и равносильность формул. Основные равносильности. Проблема общезначимости и разрешения в логике предикатов. Синтаксические свойства истинности. Модель множества формул. Предваренная нормальная форма и алгоритмы нормализации. | Мультимедиа | 5,6 | |||||
| СРС:Изучение материала лекции 3. | 5,6 | |||||||
| Практическая работа 3: Введение и использование правил в языке ПРОЛОГ. | 5,6 | Защита отчета | ||||||
| СРС:Подготовка отчета по практической работе 3 | 5,6 | Проверка | ||||||
| СРС:Выполнение курсовой работы | 5,6 | |||||||
| Лабораторная работа 3: Рекурсивное задание правил в языке ПРОЛОГ. | 5,6 | Защита отчета | ||||||
| СРС:Подготовка отчета по лабораторной работе 3 | 5,6 | Проверка | ||||||
| Тема:Исчисление предикатов, формальные аксиоматические теории | ||||||||
| Знать и понимать: основные понятия, аксиомы и теоремы исчисления предикатов Уметь:применять методы исчисления предикатов для решения задач Владеть базовыми навыками использования языка логического программирования Пролог | Лекция 4: Алфавит языка логики предикатов, аксиомы и правила вывода исчисления предикатов (ИП). Теоремы о семантической пригодности и полноте. Теории 1-го порядка: логические и собственные аксиомы. Примеры теорий 1-го порядка: теория графов, теория частично упорядоченных множеств, арифметика Пеано. Противоречивость и непротиворечивость теорий 1-го порядка. Непротиворечивость выполнимых теорий. Теорема Геделя о полноте. Основы лямбда-исчисления. Введение в язык логического программирования Пролог. | Мультимедиа | 7,8 | |||||
| СРС:Изучение материала лекции 4. | 7,8 | |||||||
| Практическая работа 4: Решение практических задач на применение метода резолюций. | 7,8 | Защита отчета | ||||||
| СРС:Подготовка отчета по практической работе 4 | 7,8 | Проверка | ||||||
| СРС:Выполнение курсовой работы | 7,8 | |||||||
| Лабораторная работа 4: Использование метода резолюций в языке Пролог. | 7,8 | Защита отчета | ||||||
| СРС:Подготовка отчета по лабораторной работе 4 | 7,8 | Проверка | ||||||
| Тема:Основы теории алгоритмов. Нормальные алгоритмы Маркова. | ||||||||
| Знать и понимать: понятие алгоритма, вычислимости, вычислимые функции, нормальные алгоритмы. Уметь выполнять программную реализацию алгоритмов Маркова на языке высокого уровня Владеть: навыками разработки нормальных алгоритмов Маркова для решения задач обработки данных | Лекция 5: Неформальные определения алгоритма. Конструктивные объекты и их типы. Нумерация конструктивных объектов. Алгоритмический процесс. Вычислимые функции. Сигнализирующее множество алгоритма. Словарные функции и множества. Нормальные алгоритмы Маркова. Тезис Маркова. | Мультимедиа | 9, 10 | |||||
| СРС:Изучение материала лекции 5. | 9, 10 | |||||||
| Практическая работа 5: Разработка нормальных алгоритмов Маркова для решения заданных практических задач | 9, 10 | Защита отчета | ||||||
| СРС:Подготовка отчета по практической работе 5. | 9, 10 | Проверка | ||||||
| СРС:Выполнение курсовой работы | 9, 10 | |||||||
| Лабораторная работа 5: Программная реализация и экспериментальная проверка разработанных алгоритмов Маркова | 9, 10 | Защита отчета | ||||||
| СРС:Подготовка отчета по лабораторной работе 5. | 9, 10 | Проверка | ||||||
| Тема:Элементы теории множеств. Машина Тьюринга | ||||||||
| Знать и понимать:основные понятия теории множеств, машина Тьюринга и её аналоги, тезис Черча. Уметь: строить машины Тьюринга для решения различных задач обработки данных Владеть: навыками перехода от алгоритмов Маркова к машине Тьюринга и наоборот | Лекция 6: Разделимые множества и некоторые их свойства. Полуразделимые множества и теорема Поста-Чёрча. Перечислимые множества и их сведения с полуразделимыми множествами. Вычислимость функции и перечислимость ее графика. Эвристическая модель машины Тьюринга. Точное определение машины Тьюринга. Конфигурации, протокол вычислений и функции, вычислимые по Тьюрингу. Эквивалентные машины Тьюринга, синтез машин Тьюринга. Тезис Черча-Тьюринга. Кодирование машин Тьюринга и нумерация их программ. Примеры построения машин Тьюринга. Понятие о многоленточной машине Тьюринга. Квантовый аналог машины Тьюринга, квантовые схемы вычислений. | Мультимедиа | 11,12 | |||||
| СРС:Изучение материала лекции 6. | 11,12 | |||||||
| Практическая работа 6: решение задач обработки текстов на машине Тьюринга | 11,12 | Защита отчета | ||||||
| СРС:Подготовка отчета по практической работе 6. | 11,12 | Проверка | ||||||
| СРС:Выполнение курсовой работы | 11,12 | |||||||
| Лабораторная работа 6: разработка и проверка алгоритмов на программном симуляторе машины Тьюринга | 11,12 | Защита отчета | ||||||
| СРС:Подготовка отчета по лабораторной работе 6. | 11,12 | Проверка | ||||||
| Тема:Рекурсивные функции | ||||||||
| Знать и понимать: разновидности рекурсивных функций и их различия Уметь: распознавать вид приведённой рекурсивной функции Владеть: навыками реализации рекурсивных функций на языках высокого уровня и на машине Тьюринга | Лекция 7: Арифметические функции и операции над ними: суперпозиция, примитивная рекурсия и ограниченный оператор минимизации. Описание и примеры примитивно-рекурсивных функций. Ограниченная сумма и произведение примитивно-рекурсивных функций. Частично-рекурсивные функции. Теорема о совпадении класса частично-рекурсивных функций и класса арифметических функций, вычислимых по Тьюрингу. | Мультимедиа | 13,14 | |||||
| СРС:Изучение материала лекции 7. | 13,14 | |||||||
| Практическая работа 7: Разработка рекурсивных функций для машины Тьюринга | 13,14 | Защита отчета | ||||||
| СРС:Подготовка отчета по практической работе 7 | 13,14 | Проверка | ||||||
| СРС:Выполнение курсовой работы | 13,14 | |||||||
| Лабораторная работа 7: Реализация рекурсивных функций на языке высокого уровня и на симуляторе машины Тьюринга | 13,14 | Защита отчета | ||||||
| СРС:Подготовка отчета по лабораторной работе 7 | 13,14 | Проверка | ||||||
| Тема:Неразрешимые алгоритмические проблемы | ||||||||
| Знать и понимать: разрешимость алгоритмических проблем, сложность алгоритмов и задач, классы сложности Уметь:доказывать неразрешимость ряда известных алгоритмических проблем Владеть методами доказательства принадлежности задачи к тому или иному классу сложности | Лекция 8: Примеры невычислимых функций и перечислимого неразрешимого множества. Проблемы самоприменимости и остановки машин Тьюринга, их алгоритмическая неразрешимость. Теорема Райса. Полугруппы слов, задание полугруппы образующими и соотношениями. Проблема равенства слов и теорема Маркова – Поста. Диофантово представление множеств и десятая проблема Гильберта. Теорема Матиясевича. Временная и емкостная сложности вычислений. Классы P, NP, E, NP-полные и NP-трудные задачи. | Мультимедиа | 15,16 | |||||
| СРС:Изучение материала лекции 8. | 15,16 | |||||||
| Практическая работа 8:Обоснование NP-полноты заданных вычислительных задач | 15,16 | Защита отчета | ||||||
| СРС:Подготовка отчета по практической работе 8 | 15,16 | Проверка | ||||||
| СРС:Выполнение курсовой работы | 15,16 | |||||||
| Лабораторная работа 8:Поиск эффективных решений для частных случаев NP-полных и NP-трудных задач | 15,16 | Защита отчета | ||||||
| СРС:Подготовка отчета по лабораторной работе 8 | 15,16 | Проверка | ||||||
| ИТОГО | Общий объем дисциплины | |||||||
| в том числе: | Аудиторная нагрузка | |||||||
| СРС | ||||||||
| Подготовка к промежуточной аттестации, аттестация | Зачет | |||||||
* - последовательность недель может быть изменена в связи с изменением графика учебного процесса и т.п.
ОЦЕНОЧНЫЕ СРЕДСТВА ДЛЯ ТЕКУЩЕГО КОНТРОЛЯ УСПЕВАЕМОСТИ, ПРОМЕЖУТОЧНОЙ АТТЕСТАЦИИ ПО ИТОГАМ ОСВОЕНИЯ ДИСЦИПЛИНЫИ УЧЕБНО-МЕТОДИЧЕСКОЕ ОБЕСПЕЧЕНИЕ САМОСТОЯТЕЛЬНОЙ РАБОТЫСТУДЕНТОВ
Темы, перечень контрольных вопросов для проведения текущего контроля и / или промежуточной аттестации
| № темы п/п | Тема, контрольные вопросы | ||||
| 3 семестр | |||||
| 1. | Тема:Основные понятия математической логики | ||||
| 1.1. Задачи, цель и предмет курса. 1.2. Понятие высказывания. 1.3. Основные логические операции. 1.4. Определение пропорциональной формулы. 1.5. Истинные значения пропорциональных формул в классической двузначной логике. 1.6. Отношение семантического следования и семантической равносильности формул. 1.7. Выполнимые формулы. 1.8. Классификация формул. 1.9. Основные законы булевой алгебры. 1.10. Проблема разрешения в логике высказываний. 1.11. Нормальные формы, СДНФ, СКНФ, хорновские дизъюнкты. 1.12. Минимизация формул. 1.13. Анализ и синтез цифровых электронных схем с базовыми логическими элементами. | |||||
| 2. | Тема:Исчисление высказываний | ||||
| 2.1. Понятие логического исчисления. 2.2. Выводимость в логическом исчислении. 2.3. Элементарные свойства выводимости. 2.4. Язык, аксиомы и правила вывода исчисления высказываний. 2.5. Теорема дедукции. 2.6. Непротиворечивые множества формул. 2.7. Семантическая и синтаксическая полнота. 2.8. Независимость аксиом и правил вывода. 2.9. Многозначные логики. | |||||
| 3. | Тема:Логика предикатов | ||||
| 3.1. Понятие предиката на наборе множеств. 3.2. Логические операции над предикатами. 3.3. Кванторы. 3.4. Область истинности предиката. 3.5. Теоретико-множественный смысл операций над предикатами. 3.6. Термы и формулы логики предикатов. 3.7. Семантика термов и формул. 3.8. Функция истинности формулы. 3.9. Выполнимые и общезначимые формулы. 3.10. Семантическое исследование и равносильность формул. 3.11 Основные равносильности. 3.12. Проблема общезначимости и разрешения в логике предикатов. | |||||
| 4. | Тема:Исчисление предикатов, формальные аксиоматические теории | ||||
| 4.1. Алфавит и аксиомы исчисления предикатов. 4.2. Правила вывода в исчислении предикатов. 4.3. Теоремы о семантической пригодности и полноте. 4.4. Теории 1-го порядка: логические и собственные аксиомы. 4.5. Примеры теорий 1-го порядка. 4.6. Противоречивость и непротиворечивость теорий 1-го порядка, непротиворечивость выполнимых теорий. 4.7. Теорема Геделя о полноте. 4.8. Основные понятия лямбда-исчисления. | |||||
| 5. | Тема:Основы теории алгоритмов. Нормальные алгоритмы Маркова | ||||
| 5.1. Определения алгоритма. 5.2. Конструктивные объекты и их типы. 5.3. Нумерация конструктивных объектов. 5.4. Алгоритмический процесс. 5.5. Вычислимые функции. 5.6. Сигнализирующее множество алгоритма. 5.7. Словарные функции и множества. 5.8. Формулы подстановки в нормальных алгоритмах Маркова. 5.9. Применение алгоритмов Маркова для преобразований над строками. 5.10. Возможности нормальных алгоритмов, тезис Маркова. | |||||
| 6. | Тема:Элементы теории множеств. Машина Тьюринга | ||||
| 6.1. Разделимые множества, их свойства. 6.2. Полуразделимые множества. 6.3. Теорема Поста-Чёрча. 6.4. Перечислимые множества, их связь с полуразделимыми. 6.5. Вычислимость и перечислимость. 6.6. Модель машины Тьюринга. 6.7. Функции, вычислимые по Тьюрингу. 6.8. Модели, эквивалентные машине Тьюринга. 6.9. Синтез машин Тьюринга. 6.10. Тезис Черча-Тьюринга. 6.11. Многоленточные машины Тьюринга. 6.12. Квантовый аналог машины Тьюринга. | |||||
| 7. | Тема:Рекурсивные функции | ||||
| 7.1. Арифметические функции. 7.2.Операции над арифметическими функциями. 7.3. Примитивно-рекурсивные функции. 7.4. Ограниченная сумма и произведение примитивно-рекурсивных функций. 7.5. Частично-рекурсивные функции. 7.6. Связь частично-рекурсивных функций с машиной Тьюринга | |||||
| 8. | Тема:Неразрешимые алгоритмические проблемы | ||||
| 8.1. Примеры невычислимых функций. 8.2. Проблемы самоприменимости и остановки машин Тьюринга, их алгоритмическая неразрешимость. 8.3. Теорема Райса. 8.4. Полугруппы слов. 8.5. Задание полугрупп образующими и соотношениями. 8.6. Проблема равенства слов и теорема Маркова-Поста. 8.7. Десятая проблема Гильберта. 8.8. Теорема Матиясевича. 8.9. Понятие сложности вычислений, временная сложность. 8.10. Полиномиальные алгоритмы и задачи, класс P. 8.11. Класс NP, NP-полные и NP-трудные задачи. 8.12 Класс сложности E. 8.13 Емкостная сложность алгоритма | |||||