МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Саратовский государственный университет имени
Факультет компьютерных наук и информационных технологий
УТВЕРЖДАЮ
_______________________
"_____"__________________20___ г.
ПРОГРАММА УЧЕБНОЙ ДИСЦИПЛИНЫ
Математическая логика и теория алгоритмов
Направление подготовки
010300 – Фундаментальная информатика и информационные технологии
Профиль подготовки
Информатика и компьютерные науки
Квалификация (степень) выпускника
Бакалавр
Форма обучения
Очная
Саратов
2011
1. Цели освоения дисциплины
Целью освоения данной дисциплины является изучение теоретических основ исчисления высказываний с приложениями, исчисления предикатов и теории алгоритмов.
2.Место дисциплины в структуре ООП бакалавриата
Данная учебная дисциплина входит в раздел «Математический и естественнонаучный цикл. Базовая часть» ФГОС-3.
Для изучения дисциплины необходимы компетенции, сформированные у обучающихся в результате изучения дисциплин «Теоретическая информатика», «Основы программирования», «Дискретная математика».
Сформированные в процессе изучения дисциплины «Математическая логика и теория алгоритмов» компетенции, необходимы студенту при изучении дисциплин «Теория автоматов и формальных языков», «Неклассические логики», «Прикладная универсальная алгебра».
3. Компетенции обучающегося, формируемые в результате освоения дисциплины
Данная дисциплина способствует формированию следующих компетенций:
способность профессионально владеть базовыми математическими знаниями и информационными технологиями, эффективно применять их для решения научно-технических задач и прикладных задач, связанных с развитием и использованием информационных технологий (ПК-8);
понимание концепций и абстракций, способность использовать на практике базовые математические дисциплины (ПК-15), включая: Математический анализ I; Математический анализ II; Кратные интегралы и ряды; Алгебра и геометрия; Теория функций комплексной переменной; Функциональный анализ; Математическая логика и теория алгоритмов; Теория автоматов и формальных языков; Дифференциальные и разностные уравнения; Теория вероятностей и математическая статистика; Вычислительные методы;
детальное знание методов и базовых алгоритмов обработки информационных структур, методов анализа сложности алгоритмов (ПК-17);
способность решать задачи производственной и технологической деятельности на высоком профессиональном уровне, включая: разработку алгоритмических и программных решений в области системного и прикладного программирования; разработку математических, информационных и имитационных моделей по тематике выполняемых опытно-конструкторских работ и проектов; создание информационных ресурсов глобальных сетей, образовательного контента, прикладных баз данных; разработку тестов и средств тестирования систем и средств на соответствие стандартам и исходным требованиям; разработку эргономичных человеко-машинных интерфейсов в соответствии с профилизацией (ПК-28)
В результате освоения дисциплины обучающийся должен:
Знать:
· значение приложений математической логики и теории алгоритмов в современной математике и информатике,
· требования информационной безопасности;
· классы математико-информационных моделей;
· основные методы построения доказательств в математике,
· приложения логики высказываний в современной электронике,
· понятие об алгоритмических процессах и вычислениях.
Уметь:
· применять математический аппарат для задач анализа и синтеза информационных систем;
· применять методы математической логики для построения доказательств в математике,
· проводить вычисления с помощью машин Тьюринга, в языке нормальных алгоритмов Маркова, представлять вычислимые объекты схемами Клини,
· использовать аппарат сложности вычислений.
Владеть
· навыками использования современного математического аппарата при решении прикладных задач;
· базовыми математическими знаниями и информационными технологиями;
· навыками эффективного применения их для решения научно-технических задач и прикладных задач, связанных с развитием и использованием информационных технологий.
4. Структура и содержание дисциплины
Общая трудоемкость дисциплины составляет 4 зачетные единицы, 144 часа (72 часа аудиторных).
№ п/п | Раздел дисциплины | Семестр | Неделя семестра | Виды учебной работы, включая самостоятельную работу студентов и трудоемкость (в часах) | Формы текущего контроля успеваемости (по неделям семестра) Формы промежуточной аттестации (по семестрам) | ||
1 | Введение. Предмет математической логики и теории алгоритмов | 3 | 1 | Л:1 | |||
2 | Элементы логики высказываний. Нормальные формы. Свойства булевых функций. Полнота систем булевых функций. | 3 | 1-4 | Л:7 | СР:14 | ПЗ:10 | Тест №1 на 4 неделе Контрольная работа N1 |
3 | Формализация. Аксиоматизация логики высказыва - ний. Теорема Геделя о полноте. | 3 | 5-7 | Л:6 | СР4 | ПЗ:6 | Тест №2 на 7 неделе Контрольная работа N2 |
4 | Приложения. Релейно-контактные схемы. Методы минимизации булевых функций. Метод резолюции. | 3 | 8-9 | Л4 | СР4 | ПЗ:4 | Тест №3 на 9 неделе |
5 | Элементы логики предикатов. Теорема Геделя о полноте. | 3 | 10-11 | Л4 | СР2 | ПЗ:4 | Тест №4 на 10 неделе Контрольная работа N3 |
6 | Интуитивное и точное математическое понятие алгоритма. Машина Тьюринга. | 3 | 12-13 | Л:4 | СР:4 | ПЗ:4 | |
7 | Схемы Клини. Класс примитивно рекурсивных функций. Тезис Черча.. | 3 | 14-17 | Л:8 | СР:6 | ПЗ:8 | Тест №5 на 15 неделе Контрольная работа N4 |
8 | Введение в теорию сложности вычислений. | 3 | 18 | Л:2 | СР:2 | Тест №6 на 18 неделе | |
Промежуточная аттестация | 3 | Экзамен | |||||
ИТОГО | 36 | 36 | 36 | 36 |
Раздел 1. «Введение. Предмет математической логики и теории алгоритмов». Опии саны составляющие части математической логики и ее роль в отношении других математических наук. Теория множеств, как составная часть математической логики, дает язык всей математики, исчисления и теория доказательств – правила построения правильных доказательств. Теория алгоритмов дает точное определения алгоритмической процедуры и вычислимых объектов..
Раздел 2.«Элементы логики высказываний. Нормальные формы. Свойства булевых функций. Полнота систем булевых функций». Предмет логики высказываний. Основные теоремы логики высказываний. Основные тавтологии. Нормальные формы, свойства монотонности, самодвойственности, линейности, принадлежности классам T0 и T1. Теорема Поста о полноте.
Самостоятельная работа: Построение истинностных таблиц для формул логики высказываний. Эквивалентные преобразования формул. Построение нормальных форм. Исследование свойств булевых функций.
Раздел 3. «Формализация. Аксиоматизация». Язык исчисления высказываний. Система аксиом и правил вывода. Примеры доказательств.
Самостоятельная работа: Построение выводов формул логики высказываний.
Раздел 4. «Приложения. Релейно-контактные схемы. Методы минимизации булевых функций. Метод резолюции». Приложения логики высказываний.
Самостоятельная работа: Построение эффективных релейно-контактных схем. Изучение методов минимизации булевых функций.
Раздел 5. «Логика предикатов». Язык логики предикатов. Интерпретация предикатных букв над непустыми областями. Основные тавтологии с кванторами.
Самостоятельная работа: Построение истинностных таблиц формул логики предикатов. Нахождение нормальных пренексных форм для формул логики предикатов.
Раздел 6. «Интуитивное и точное математическое понятие алгоритма. Машина Тьюринга». Свойства алгоритма. Машина Тьюринга. Примеры вычислений на машине Тьюринга..
Самостоятельная работа: разбор примеров по материалам лекций.
Раздел 7. «Схемы Клини. Класс примитивно рекурсивных функций. Тезис Черча». Математическое определение вычислимых объектов - частично рекурсивные функции. Тезис Черча. Базисные функции и вычислимые операторы класса примитивно рекурсивных функций. Разрешимые множества, отношения, предикаты. Оператор минимизации. Неразрешимые множества. Рекурсия второй ступени. Универсальные множества.
Самостоятельная работа: Построение схем примитивной рекурсии для известных арифметических функций. Доказательство примитивной рекурсивности множеств и предикатов.
Раздел 8. «Введение в теорию сложности вычислений». Классы P и NP. Труднорешаемые задачи.
Самостоятельная работа: Представление вычислений на недетерминированных машинах Тьюринга.
5. Образовательные технологии
В учебном процессе при реализации компетентностного подхода
используются такие активные и интерактивные формы проведения занятий
как модельный метод обучения, разбор конкретных ситуаций. Широко
используются мультимедийные презентации при представлении учебного
материала.
6. Учебно-методическое обеспечение самостоятельной работы студентов. Оценочные средства для текущего контроля успеваемости, промежуточной аттестации по итогам освоения дисциплины.
7. Учебно-методическое и информационное обеспечение дисциплины
а) основная литература:
1. Н. Математическая логика и теория алгоритмов./Учебное пособие. 3-е издание, дополненное. Саратов.:CГУ, 2006.-84 c.
2. Введение в дискретную математику: Учеб. пособие для студентов вузов, обучающихся по спец."Прикл. математика" / . – 3-е изд., стер. - М. : Высш. шк., 20с.
В. Введение в дискретную математику : учеб. пособие / ; под ред. . - 4-е изд., стер. - М. : Высш. шк., 20с.
В. Введение в дискретную математику : учеб. пособие / ; под ред. ; Моск. гос. ун-т им. . - 4-е изд., стер. - М. : Высш. шк., 20с.
б) дополнительная литература:
1. C.К. Клини. Математическая логика. Изд-во Мир. М, 1973.
2. , . Задачи по теории множеств, математической логике и теории алгоритмов. М:Наука,1975.
3. , , . Вводный курс математической логики. М:ФИЗМАТЛИТ,2002.
4. . Алгоритмы и рекурсивные функции. М:Наука,1965.
5. К. Катленд. Вычислимость. Введение в теорию рекурсивных функций. Пер. с англ. М:Мир,1983.
6. . Основы информатики. М.: Изд-во МГТУ им. Н.Э. Баумана,2001.
7. . Нечеткое моделирование в среде MATLAB и fuzzyTECH.-СПб.:БХВ-Петербург,2003.
8. Дж. Хопкрофт, Рад. Мотвани, Дж. Ульман. Введение в теорию автоматов, языков и вычислений, 2-е изд..:Пер. с англ.-М.:Издательский дом “Вильямс” , 2002.
в) программное обеспечение и Интернет-ресурсы:
Не требуется
8. Материально-техническое обеспечение дисциплины
Лекционная аудитория с возможностью демонстрации электронных презентаций при уровне освещения, достаточном для работы с конспектом.
Программа составлена в соответствии с требованиями ФГОС ВПО с учетом рекомендаций и Примерной ООП ВПО по направлению и профилю подготовки «Информатика и компьютерные науки».
Автор
доцент ________
Программа одобрена на заседании кафедры теоретических основ компьютерной безопасности и криптографии и от “_____” _______2011 года
протокол № ________
Заведующий кафедрой
теоретических основ компьютерной
безопасности и криптографии,
профессор ___________
Декан факультета КНиИТ,
доцент ___________
