Программа дисциплины ен. Ф. 01. 04 «математическая логика и теория алгоритмов» Рекомендуется умц кгту им. А. Н. Туполева для направления (специальностей) направление
| скачать КАЗАНСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ им. А.Н. ТУПОЛЕВА УТВЕРЖДАЮ: Проректор по учебной и методической работе _________________ И.К. Насыров «_____» _______________ 200_ г. ПРОГРАММА ДИСЦИПЛИНЫЕН.Ф.01.04 «МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ»Рекомендуется УМЦ КГТУ им. А.Н. Туполева для направления (специальностей) направление: 230100* «Информатика и вычислительная техника» формы обучения: очная *) коды направлений и специальностей указаны по Общероссийскому классификатору специальностей по образованию (ОК 009-2003) ^ Целью дисциплины является изучение понятий и методов математической логики и теории алгоритмов с ориентацией на их использование в задачах практической информатики. Задачи дисциплины: приобретение знаний, умений и навыков решения задач математической логики и теории алгоритмов и их приложений в различных задачах дискретной математики, информатики и вычислительных систем. При изучении курса используются основные понятия теории множеств, линейной алгебры и теории функций. Знания, умения и навыки, приобретенные в данной дисциплине, используются при изучении последующих дисциплин учебного плана, особенно математических дисциплин, дисциплин по основам ЭВМ, математическому обеспечению ЭВМ. ^ В результате изучения дисциплины студенты должны: знать:
уметь:
иметь навыки: - анализа выполнимости и логической общезначимости формул логики высказываний;
иметь представление:
^ 4.1. Тематический план
^ (курсивом выделены разделы, указанные в ГОСах и рекомендованной программе дисциплины). Для указания объема занятий даны внутри скобок два числа: число часов аудиторных занятий и число часов самостоятельной работы. Введение (1/0.5) Предмет дисциплины, ее структура и содержание, литература. Связь дисциплины с предшествующими и последующими дисциплинами. Краткие сведения об истории развития дисциплины. Логика высказываний (6/4) Язык логики высказываний. Интерпретация формул. Общезначимость, выполнимость, противоречивость. Методы анализа выполнимости и общезначимости формул. Алгоритм приведения формул в КНФ. Алгоритм проверки общезначимости формул. Логика предикатов (10/6) Синтаксис и семантика языка логики предикатов. Формулы логики предикатов, интерпретация. Логически общезначимые, выполнимые формулы. Равносильные преобразования формул логики предикатов. Предваренная нормальная форма. Алгоритм ее получения. Логическое следствие и метод резолюций (7/4) Логическое следствие, проблема дедукции. Хорновские дизъюнкты. Метод резолюций в логике высказываний, стратегии метода резолюций. Сколемовская стандартная форма. Подстановка, композиция подстановок, унификатор. Алгоритм унификации. Метод резолюций в логике предикатов. Теорема Робинсона. Принцип логического программирования. Использование метода резолюций в языке ПРОЛОГ. Формальные системы (8/4) Понятие формальной системы, формальный вывод, свойства формальных систем. Исчисление высказываний как формальная система. Теорема дедукции, связь выводимости и истинности формул в логике высказываний. Теории первого порядка. Исчисление предикатов как формальная система. Метатеория формальных систем: непротиворечивость, полнота, разрешимость. Теория алгоритмов (10/7) Нормальные алгоритмы. Машины Тьюринга. Частично-рекурсивные функции. Примитивно, обще и частично-рекурсивные функции. Рекурсивно и рекурсивно-перечислимые множества. Тезис Черча. Алгоритмически разрешимые и неразрешимые задачи. Многозначные, нечеткие, модальная и темпоральные логики (5/6) Многозначные логики. Понятие нечеткого множества. Нечеткие логики. Модальная логика. Темпоральная логика. Пороговые логики. Сложность вычислений с помощью алгоритмов (3/3;) Меры сложности алгоритмов. Временная и емкостная сложность. Сложность в среднем и в худшем случае. Легко- и трудноразрешимые задачи. Классы задач Р и NP. NP –трудные и NP – полные задачи. Примеры NP-полных задач. Класс Е. Заключение (1/0.5) Направления использования аппарата математической логики в задачах практической информатики: спецификация и верификация программно-аппаратных проектов, логическое программирование, языки общения интеллектуальных агентов. ^
4.4. В рамках самостоятельной работы по дисциплине выполняется домашнее задание (расчетно-графическая работа). Цель домашнего задания – закрепление навыков решения задач по курсу. Домашнее задание состоит в решении задач по следующим темам:
Каждому студенту выдается 1-3 задачи по каждой из перечисленных тем. Задание выполняется в отдельной тетради и сдается преподавателю. ^ Рекомендуемая литература а) основная литература: 1. Мендельсон Э. Введение в математическую логику. -М.: Наука, 2004.
б) дополнительная литература:
^ Персональные компьютеры ИВЦ КГТУ. 7. Методические рекомендации по организации изучения дисциплины Рекомендуемый список вопросов и тем по дисциплине.
Программа составлена в соответствии с Государственным образовательным стандартом высшего и среднего образования по направлению подготовки 654600 – Информатика и вычислительная техника и рекомендованной примерной программой дисциплины «Математическая логика и теория алгоритмов» для направления 654600. Программу составил: Галиев Ш. И., д.т.н., профессор каф. ПМИ КГТУ им. А.Н. Туполева Программа обсуждена и одобрена на заседании кафедры ПМИ __ ___________ 200 г., протокол № __. Зав. кафедрой ПМИ Н. Е. Роднищев д.т.н., профессор Зав. выпускающей кафедрой КС В. А. Песошин д.т.н., профессор Зав. выпускающей кафедрой АСОИУ Л. М. Шарнин д.т.н., профессор Председатель Учебно-методической В. А. Суздальцев комиссии факультета, к.т.н., доцент Декан факультета ТКиИ Л. М. Шарнин д.т.н., профессор
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Ваша оценка этого документа будет первой.
Ваша оценка: 