Скачать 186.66 Kb.
|
Государственное образовательное учреждение высшего профессионального образования Тихоокеанский государственный университет
ПРОГРАММА ДИСЦИПЛИНЫ по кафедре Прикладная математика и информатика МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВУтверждена научно-методическим советом университета для направлений подготовки (специальностей) в области информатики и вычислительной техники Хабаровск 2006 г. Программа разработана в соответствии с требованиями государственного образовательного стандарта, предъявляемыми к минимуму содержания дисциплины и в соответствии с примерной программой дисциплины, утвержденной департаментом образовательных стандартов профессионального образования с учетом особенностей региона и условий организации учебного процесса Тихоокеанского государственного университета Программу составила Хан Сун Э, к.ф.м.н, доцент кафедры ПМИ Программа рассмотрена и утверждена на заседании кафедры ПМИ протокол № ____ от «_____»__________200_ г Зав.кафедрой _________________ «______»_________200_ г. Зарубин А.Г. Программа рассмотрена и утверждена на заседании УМК и рекомендована к изданию протокол № ____ от «_____»__________200_ г Прекдседатель УМК _________________ _________200_ г ________________Подпись дата Ф.И.О. Директор института _________________ _________200_ г ________________Подпись дата Ф.И.О. (декан факультета)Цели и задачи дисциплины Целью преподавания дисциплины «Математическая логика и теория алгоритмов» является ознакомление студентов с важнейшими разделами математической логики и теории вычислимости, оказывающими наибольшее влияние на теорию и практику современного программирования. При преподавании учебной дисциплины «Математическая логика и теория алгоритмов» ставятся следующие задачи:
Требования к уровню освоения содержания дисциплины Математическое образование должно быть фундаментальным и в то же время иметь четко выраженную прикладную направленность, быть в известной мере индивидуализированным. После изучения дисциплины «Математическая логика и теория алгоритмов» студент должен знать основные направления математической логики, формальные методы логического обоснования, способы формального описания алгоритмов. Студент должен владеть навыками формализации рассуждений, методами построения формальных логических выводов, он должен иметь опыт составления алгоритмов и уметь оценивать вычислительную сложность алгоритмов. Студент должен иметь представление о направлениях развития дисциплины «Математическая логика и теория алгоритмов» и перспективах ее использования в информационных системах. Объем дисциплины и виды учебной работы
Содержание дисциплины ЛОГИКА ВЫСКАЗЫВАНИЙ Язык логики высказываний. Понятие логического высказывания. Логические операции над высказываниями. Формулы алгебры высказываний. Равносильные формулы алгебры высказываний. Принцип двойственности. Дизъюнктивные и конъюнктивные нормальные формы, совершенные дизъюнктивные и конъюнктивные нормальные формы. Минимизация СДНФ методом Квайна. Логические функции ![]() ЛОГИКА ПРЕДИКАТОВ Синтаксис языка логики предикатов: алфавит, термы, атомы, правила построения формул. Свободные и связанные вхождения переменных, замкнутые формулы. Семантика языка логики предикатов, интерпретация формул. Предваренная нормальная форма. Применение языка логики предикатов для записи математических предложений. ФОРМАЛЬНЫЕ (АКСИОМАТИЧЕСКИЕ) СИСТЕМЫ Понятия формальной системы и формального вывода. Исчисление высказываний как формальная система, множественность аксиоматизаций. Теорема дедукции. Связь выводимости и истинности формул в логике высказываний. Примеры формального вывода. Основные свойства формальных систем: непротиворечивость, полнота, разрешимость. Теоремы о неполноте формальных систем. ТЕОРИЯ АЛГОРИТМОВ Понятие алгоритма и его характерные черты. Вычислимые функции. Примитивно рекурсивные, частично-рекурсивные функции, тезис Черча. Машины Тьюринга, тезис Тьюринга. Рекурсивные и рекурсивно-перечислимые множества и языки. Алгоритмически разрешимые и неразрешимые задачи. Меры сложности алгоритмов: временная и емкостная сложность. Асимптотическая сложность, порядок сложности. Сложность в среднем и в худшем случае. Языки и задачи. Легко- и трудноразрешимые задачи, классы задач P и NP. NP-полные задачи. Недетерминированная машина Тьюринга. Разделы дисциплины и виды занятий и работ
Практические занятия ЛОГИКА ВЫСКАЗЫВАНИЙ Задание. Решение задач по теме: таблицы истинности формул алгебры высказываний, равносильные преобразования формул, логические функции, полные системы логических функций, представление функции в различных базисах, некоторые приложения алгебры высказываний. Время на выполнение задания – 6 часов Оснащение. Для проведения всех практических занятий целесообразно использовать Лихтарников Л.М., Сукачева Т.Г. Математическая логика. Курс лекций. Задачник-практикум и решения. – СПб.: Издательство «Лань», 1998, Игошин В.И. Задачник-практикум по математической логике. – М.: Просвещение, 1986, Гиндикин С.Г. Алгебра логики в задачах. – М.: Наука, 1972, сборники задач на усмотрение преподавателя. ЛОГИКА ПРЕДИКАТОВ Задание. Решение задач по теме: предикаты, их область определения и область истинности, операции дизъюнкции, конъюнкции, отрицания над предикатами, кванторные операции, равносильные формулы логики предикатов, предваренная нормальная форма. Время на выполнение задания – 3 часа ФОРМАЛЬНЫЕ (АКСИОМАТИЧЕСКИЕ) СИСТЕМЫ Задание. Решение задач по теме: доказуемые формулы исчисления высказываний, выводимость, производные правила вывода. Время на выполнение задания – 4 часа. ТЕОРИЯ АЛГОРИТМОВ Задание. Решение задач по теме: построение некоторых машин Тьюринга, доказательство принадлежности функции классу примитивно рекурсивных или частично рекурсивных функций. Время на выполнение задания – 4 часа. Практические занятия и их взаимосвязь с содержанием лекционного курса
Контроль знаний студентов 1. Входной контроль знаний студентовДля изучения дисциплины необходимо знание понятий и положений курсов «Математический анализ», «Алгебра», «Дискретная математика», «Информатика». 2. Текущий контроль знаний студентовКонтроль достижения целей обучения осуществляется с помощью проведения контрольной работы в течение семестра по темам курса. Главной целью проведения контрольной работы является установление уровня и характера усвоения студентами основных понятий, умений и навыков, формируемых в процессе изучения курса. Примерное содержание контрольной работы Контрольная работа содержит 5 задач по темам: равносильные преобразования формул алгебры высказываний, полнота систем логических функций, логические операции над предикатами, доказуемые и выводимые формулы исчисления высказываний, машины Тьюринга. 3.Выходной контроль знаний студентов Дисциплина завершается устным экзаменом. На экзамене проверяется степень усвоения студентами основных понятий дисциплины, понимание их взаимосвязи, умение доказывать основные теоремы, а также навыки в решении задач по каждому из разделов дисциплины. Экзаменационные вопросы
Учебно-методическое обеспечение дисциплиныОсновная литература.
Дополнительная литература
Методические рекомендации по организации изучения дисциплины Программа определяет общий объем знаний, а не порядок изучения предмета. Тем не менее, построение соответствующих математических курсов должно проводиться так, чтобы у студента сложилось целостное представление об основных этапах становления современной математики и ее структуре, об основных математических понятиях и методах, о роли и месте математической логики в различных сферах человеческой деятельности. Для того, чтобы студент воспринимал ценности математической логики как науки и свободно владел математическими методами в приложениях к техническим наукам, конкретная реализация программы должна иметь следующую структуру. Математические курсы, соответствующие данной программе, должны содержать лекции, практические занятия в аудитории, индивидуальные занятия студентов с преподавателем и самостоятельную работу студентов. Целью лекций является изложение теоретического материала и иллюстрация его примерами и задачами. Основным теоретическим результатам должны сопутствовать пояснения об их приложениях к другим разделам математики и к техническим наукам. Желательно также кратко излагать историю появления наиболее важных понятий и результатов. Курс лекций должен строиться на основе четких формулировок и доказательств основных теорем, так как лишь при таком подходе студенты приобретают математическую культуру, необходимую для дальнейшего изучения инженерных дисциплин. Недопустимо сводить чтение лекций только к разбору примеров и алгоритмов их решения. Целью практических занятий является закрепление теоретического материала лекций и выработка умения решать примеры и задачи для последующего применения математических методов в технических приложениях. Важнейшей частью математических курсов являются индивидуальные занятия с преподавателем. Поэтому изучаемый курс должен содержать контрольные работы в течение семестра. Организация самостоятельной работы предполагает, что:
Самостоятельная работа не расширяет существенно рамки программы, она призвана закрепить излагаемый на лекциях и практических занятиях материал, а также приучает студентов к самостоятельному овладению новым материалом. Знания, полученные при изучении дисциплины «Математическая логика и теория алгоритмов» применяются при изучении широкого спектра профильных, специальных предметов. Программа рассчитана на 85 часов. Программа составлена в соответствии с государственными образовательными стандартами высшего профессионального образования. Словарь терминов Алгоритм – точное предписание, определяющее детерминированный и результативный процесс решения множества задач определенного класса Вывод – непустая конечная последовательность утверждений, каждое из которых представляет собой либо аксиому, либо посылку, либо получено из предыдущих шагов по одному из правил вывода Дедукция – тип умозаключения, в котором между посылками и заключением существует отношение логического следования Дизъюнктивная нормальная форма – дизъюнкция различных конъюнкций, причем членами конъюнкций являются различные переменные или отрицания переменных Дизъюнкция двух высказываний x, y – новое высказывание, которое считается ложным, если оба высказывания x, y ложны, и истинным во всех остальных случаях Доказательство – вывод из пустого множества посылок Импликация двух высказываний x, y – новое высказывание, которое считается ложным, если высказывание x истинно, а y ложно, и истинным во всех остальных случаях Конъюнктивная нормальная форма – конъюнкция различных дизъюнкций, причем членами дизъюнкций являются различные переменные или отрицания переменных Конъюнкция двух высказываний x, y – новое высказывание, которое считается истинным, если оба высказывания x, y истинны, и ложным во всех остальных случаях Логическая функция n переменных – функция, у которой каждая переменная аргумента и само значение функции принимают только два значения 0 и 1, то есть ![]() Непротиворечивость формальной системы – свойство системы, при котором любое утверждение, доказуемое в ней, является истинным Область истинности предиката ![]() ![]() Область ложности предиката ![]() ![]() Отрицание высказывания x – новое высказывание, которое является истинным, если высказывание x ложно, и ложным, если x истинно Полнота формальной системы – свойство системы, при котором любое утверждение, истинное в ней, является доказуемым Предикат от n переменных – функция P, которая декартову произведению множеств ![]() Предикат от одной переменной – функция P, которая множество предметных переменных X отображает в множество {0,1}. Обозначается ![]() Противоречие – формула алгебры высказываний, которая принимает ложное значение при любых значениях, входящих в нее элементарных высказываний Равносильные формулы алгебры высказываний – формулы, которые принимают одинаковые значения на любом наборе значений, входящих в них элементарных высказываний Равносильные предикаты на множестве Х – предикаты, у которых есть общая область определения Х и которые принимают одинаковые значения при любых предметных переменных из этой области Совершенная дизъюнктивная нормальная форма – дизъюнктивная нормальная форма, у которой каждая переменная или ее отрицание входит в каждую конъюнкцию ровно один раз Совершенная конъюнктивная нормальная форма – конъюнктивная нормальная форма, у которой каждая переменная или ее отрицание входит в каждую дизъюнкцию ровно один раз Тавтология – формула алгебры высказываний, которая принимает истинное значение при любых значениях, входящих в нее элементарных высказываний Тождественно истинный предикат – предикат ![]() Тождественно ложный предикат – предикат ![]() Универсальное высказывание, соответствующее одноместному предикату ![]() ![]() Формальная система – совокупность четырех множеств, первое называют множеством символов, второе – множеством формул, то есть последовательностей символов записанных по определенному принципу, третье – множество аксиом, то есть некоторых избранных формул, четвертое – множество правил вывода, то есть некоторых отношений между формулами Формула алгебры высказываний – высказывание, полученное из элементарных высказываний с помощью операций конъюнкции, дизъюнкции, импликации, эквиваленции, отрицания Эквиваленция двух высказываний x, y – новое высказывание, которое считается истинным, когда оба высказывания x, y одновременно истинны или одновременно ложны, и ложным во всех остальных случаях Экзистенциальное высказывание, соответствующее одноместному предикату ![]() ![]() Элементарное высказывание – простое повествовательное предложение, о котором можно утверждать, что оно истинно или ложно, но оно не может быть одновременно истинным и ложным. |
![]() | Рабочая программа дисциплины Математическая логика и теория алгоритмов Направление Целями освоения дисциплины «Математическая логика и теория алгоритмов» являются получение теоретических знаний по основам математическая... | ![]() | Рабочая программа по дисциплине в 2-Математическая логика и теория алгоритмов Математическая логика и теория алгоритмов в соответствии требованиями фгос впо, утвержденного приказом Министра образования и науки... |
![]() | «Математическая логика и теория алгоритмов» Математическая логика и теория алгоритмов" является фундаментальное образование в области принципов построения эффективных и надежных... | ![]() | Программа дисциплины математическая логика и теория алгоритмов Рабочая программа дисциплины "Математическая логика и теория алгоритмов" предназначена для студентов 3 курса |
![]() | Учебно-методический комплекс по дисциплине математическая логика и теория алгоритмов Сперанский Д. В., доктор технических наук, профессор кафедры «Высшая и прикладная математика» | ![]() | Правительство Российской Федерации Государственное образовательное бюджетное учреждение высшего профессионального образования Изучение дисциплины базируется на знаниях, полученных студентами при освоении учебных дисциплин «Дискретная математика», «Информатика,... |
![]() | Аннотация рабочей программы «Математическая логика» В. од. 1 «Математическая логика» является вариативной частью Математического и естественнонаучного цикла подготовки студентов направления... | ![]() | Ульянов М. В., Шептунов М. В. Математическая логика и теория алгоритмов, часть 2: Теория алгоритмов Ульянов М. В., Шептунов М. В. Математическая логика и теория алгоритмов, часть 2: Теория алгоритмов. – М.: Мгапи, 2003. – 80 с |
![]() | Программа дисциплины «Теория межкультурной коммуникации» для направления 010400. 68 «Прикладная математика и информатика» Программа предназначена для преподавателей, ведущих данную дисциплину, и студентов направления подготовки 010400. 68 "Прикладная... | ![]() | Программа дисциплины «Математическая логика» для направления Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления подготовки 231300.... |