Учебно-методический комплекс дисциплины математическая логика и теория алгоритмов 050100 Педагогическое образование
| Вид материала | Учебно-методический комплекс |
- Рабочей программы учебной дисциплины дв2 Математическая логика и теория алгоритмов, 50.1kb.
- Учебно-методический комплекс по дисциплине математическая логика и теория алгоритмов, 144.09kb.
- Рабочая программа по дисциплине в 2-Математическая логика и теория алгоритмов шифр, 316.78kb.
- Рабочая учебная программа по дисциплине «Математическая логика и теория алгоритмов», 69.99kb.
- Учебно-методический комплекс дисциплины «Математическая логика и теория алгоритмов», 376.44kb.
- Рабочая программа учебно-педагогической практики (летние лагерные сборы) на 2010-2011, 438.34kb.
- Рабочая программа дисциплины «Математическая логика и теория алгоритмов», 143.48kb.
- Рабочая программа учебно-исследовательской практики на 2011-2012 учебный год Направление, 225.84kb.
- Рабочая программа учебно-полевой практики по зоологии 2010-2011 учебный год, 254.69kb.
- Программа вступительного экзамена в магистратуру по направлению подготовки: 050100., 85.55kb.
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ
РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ
УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«Пермский государственный педагогический университет»
Математический факультет
Кафедра высшей математики
Пастухова Г.В.
Учебно-методический комплекс дисциплины
МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ
050100 – Педагогическое образование
Профиль подготовки – Информатика и ИКТ
Квалификаций (степень) выпускника
Бакалавр педагогического образования
Форма обучения очная
Пермь, 2012
- Цель дисциплины.
В дисциплину «Математическая логика и теория алгоритмов» вошли и одна из древнейших математических наук – логика (первое дошедшее до нас сочинение «Аналитики» Аристотеля (382-322 гг. до н.э.) принадлежит позднегреческой эпохе) и совсем юная по меркам истории – теория алгоритмов, которая не насчитывает и ста лет. Обе эти науки, не смотря на столь значительную разницу в возрасте, имеют много общего – они обосновывают саму математику, ее строение и особенности формализаций различных математических систем.
Программа дисциплины отражает цель курса – знакомство с формализацией математического языка, которая рассматривается в данном курсе значительно глубже, чем в курсах алгебры, геометрии и математического анализа, и охватывает также логические средства. В рамках этого курса изучается, прежде всего, язык логики, освещаются современные подходы к формализации и аксиоматизации различных математических дисциплин, в частности затрагиваются такие фундаментальные понятия, как понятие непротиворечивости и полноты математической теории, независимости системы аксиом.
Дисциплина включает в себя два основных раздела: «Математическая логика» и «Теория алгоритмов». В вводном разделе программы рассматриваются основные этапы становления математической логики как особой математической дисциплины, освещается ее роль в решении проблем обоснования математики, в развитии современной вычислительной техники.
Раздел «Математическая логика» в свою очередь состоит из подразделов «Алгебра высказываний», которая изучает высказывания, формулы, их истинностные значения, тождественно ложные, истинны и выполнимые формулы, равносильность формул, приведение формул с помощью равносильных преобразований к нормальным формам. Овладение техникой алгебры высказываний позволить студентам решать алгебраическим методом логические задачи, в частности проверять правильность некоторых рассуждений, а также составлять и упрощать релейно-контактные схемы с заданными условиями работы.
Пример формальной аксиоматической системы рассматривается в разделе «Исчисление высказываний». Особое внимание в этом разделе следует уделить доказательству выводимости в построенном исчислении формул (теорем).
Далее вводится понятие предиката, определяются операции навешивания кванторов общности и существования, обобщаются понятия формулы и ее интерпретации. Возможности языка алгебры предикатов иллюстрируются разнообразными примерами при рассмотрении арифметической и геометрической моделей.
Формализованное исчисление предикатов рассматривается как расширение исчисления высказываний.
Все вышеуказанные подразделы (алгебры и исчисления высказываний и предикатов) являются примерами построения той или иной формализованной системы. Принципы построения и характеристики (полнота, разрешимость, противоречивость) составляющие метатеорию формальных систем подытоживают данный раздел. Также даются примеры и понятия неклассических видов логики как нечеткая и алгоритмическая и принципы логического программирования.
Второй раздел «Теория алгоритмов» является теоретической основой программирования и посвящен формализации понятия «алгоритма» в виде машин Тьюринга и рекурсивных функций. Начинается раздел с изучения возникшей потребности в строгом определении «алгоритма». Далее рассматривается интуитивное понятия «алгоритма», приводятся примеры.
Подраздел «Рекурсивные функции» посвящен базовым функциям и операциям, формируется понятие и примеры частично-рекурсивных, рекурсивных и общерекурсивных функций, доказывается рекурсивность основных арифметических функций, формулируется тезис Черча. Также даются понятия алгоритмически неразрешимых, легкоразрешимых и трудноразрешимых задач и оценки (меры) сложности алгоритмов.
Аналогично строится формализация понятия алгоритма в виде машин Тьюринга, рассматривается ее устройство, действия над машинами, связь с рекурсивными функциями, финалом является тезис Тьюринга, проводиться аналогия с тезисом Черча.
- Место дисциплины в структуре ООП:
Дисциплина «Математическая логика и теория алгоритмов» относится к вариативной части профессионального цикла.
Для освоения дисциплины «Математическая логика и теория алгоритмов» используются знания, умения и виды деятельности, сформированные в ходе изучения дисциплин: «Алгебра», «Геометрия», «Математический анализ», «Теория функций действительного переменного», «Теория чисел», «Информатика».
Дисциплина «Математическая логика и теория алгоритмов» является логической основой понимания сущности доказательств и их логического строения, изучения аксиоматических математических теорий из разных областей математики, а также теоретическим обоснованием логической составляющей обучения математике. Алгоритмический подход позволяет изучать математические теории в целом.
3. Требования к результатам освоения этой дисциплины
Процесс изучения дисциплины направлен на формирование следующих специальных компетенций СК-1, СК-2, СК-3.
| № | Общая формулировка | Детализация |
| СК-1 | Овладение содержанием фундаментальных математических дисциплин (овладение основными понятиями, идеями и принципами, освоение методов фундаментальных математических теорий) | - владеет основными понятиями алгебры высказываний (АВ) и предикатов, исчисления высказываний (ИВ) и предикатов (ИП) (высказывания, действия над высказываниями (конъюнкция, дизъюнкция, импликация, эквивалентность), таблицы истинности, формулы АВ, равносильных формул, ДНФ, СДНФ, КНФ, СКНФ; аксиомы и их свойств (полнота, независимость) исчисления, правила вывода из аксиом, теорема дедукции, выводимой формулы, связь АВ и ИВ, свойства ИВ (непротиворечивость, полнота); предиката, квантора, нормальных форм и формул; формул ИП, аксиомы и их свойства ИП, выводимые формулы, теорема дедукции, свойства ИП (непротиворечивость, полнота; алгоритма, вычислимой функции, машины Тьюринга, действии над машинами, тезис Черча, тезис Тьюринга, рекурсивной функции (частично рекурсивной и примитивно рекурсивной)); - имеет навык равносильных преобразований формул АВ, применения АВ для решения текстовых задач и анализа РКС, доказательства выводимости в построенном исчислении формул (теорем); -способен уточнить понятие «алгоритма» с помощью рекурсивных функций и машин Тьюринга; -имеет навык построения машин Тьюринга для решения задач и действиями над ними; - умет доказывать рекурсивность основных функций. |
| СК-2 | Овладение методом математического моделирования (способность к построению математических моделей, выбору и применению соответствующему модели математического метода решения задачи и интерпретации результатов) | - владеет аксиоматическим методом построения математических дисциплин на примерах ИВ и ИП; - готов исследовать различные системы на такие характеристики как полнота, непротиворечивость, разрешимость; - способен показать алгоритмическую неразрешимость проблемы останова, самоприменимости и др. |
| СК-3 | Понимание методологической и историко-культурной функций математики | - способен применить аксиоматический метод к анализу произвольной математической теории; - имеет навык применения языка логики предикатов к анализу математических текстов (запись определения, предложения, теоремы) и построения противоположных. обратных утверждений данному и применять доказательство от противного; - знает методику формулирования необходимых и достаточных условий; - владеет навыком преобразований высказываний для анализа релейно-контактных схем и решения текстовых задач. |
В результате изучения дисциплины студент должен
знать:
- этапы становления математической логики как особой математической дисциплины, начиная с логики Аристотеля; ее роль в развитии современной вычислительной техники;
- способы формализации систем и понятия «алгоритма»
- законы логической равносильности;
- компоненты (аксиомы и правила вывода) и характеристики (свойства) исчисления высказываний и исчисления предикатов;
- методы математической логики для изучения математических доказательств и теорий;
- различные определения понятия алгоритма;
- формулировку алгоритмически неразрешимых проблем;
- знать аксиоматический метод построения класса вычислимых функций;
уметь:
- распознавать тождественно истинные формулы алгебры высказываний и логики предикатов;
- применять средства языка логики предикатов для записи и анализа математических предложений;
- строить простейшие выводы в исчислении высказываний и исчислении предикатов, использовать эти модели для объяснений строения математических доказательств;
- строить машины Тьюринга для решения простых алгоритмических задач;
- доказывать вычислимость простейших функций в теории алгоритмов;
владеть:
- техникой равносильных преобразований логических формул;
- методами распознавания тождественно истинных и равносильных формул;
- дедуктивным аппаратом изучаемых логических исчислений;
- алгоритмом нумерации кортежей;
- алгоритмом разложения вычислимых функций в простейшие;
- способами получения из основных рекурсивных функций доказательств рекурсивности (примитивной, общерекурсивной и частичной) функций.
приобрести навыки:
- находить совершенные формы; проверять правильность рассуждений;
- выполнять упрощения формул алгебры высказываний с помощью основных равносильностей и построения таблиц истинности;
- составлять и упрощать комбинационные схемы с заданными условиями работы;
- доказывать выводимость формул исчисления высказываний;
- записывать в виде формул логики предикатов содержательные математические предложения;
- проверять формулы на общезначимость и выполнимость;
- доказывать рекурсивность той или иной функции, уметь строит из функций с помощью операций минимизации, постановки и рекурсии иные функции.
3.2. Матрица соотнесения разделов учебной дисциплины и формируемых компетенций
| № | Разделы | Компетенции |
| 1. | Дедуктивный характер математики. Предмет и методы математической логики. Этапы развития математики. | СК-1 |
| 2. | Алгебра высказываний. Формулы алгебры высказываний. Основные равносильности алгебры высказываний. Нормальные и совершенные формы. Логическое следование формул. Применение алгебры высказываний к анализу рассуждений, описанию и преобразованию переключательных схем. | СК-1 СК-2 |
| 3. | Исчисление высказываний. Аксиомы и правила вывода. Выводимость из гипотез. Свойства выводимости из гипотез. Теорема дедукции. Производные правила вывода. Выводимость формул исчисления высказываний. Доказуемость формулы и её тождественная истинность. Теорема о полноте исчисления высказываний. Непротиворечивость, полнота и разрешимость исчисления высказываний. | СК-1 СК-3 |
| 4. | Логика предикатов. Предикаты. Логические операции над предикатами. Кванторные операции над предикатами. Формулы логики предикатов. Классификация формул логики предикатов. Интерпретация формул. Предваренная нормальная форма. Логическое следование. Запись математических предложений на языке логики предикатов. Методы рассуждений. | СК-1 СК-2 |
| 5. | Исчисление предикатов. Аксиоматическое построение исчисления предикатов: аксиомы и правила вывода. Теорема дедукции. Теоремы исчисления предикатов. Выводимость и общезначимость формул исчисления предикатов. Непротиворечивость, неразрешимость исчисления предикатов. Теорема Гёделя о неполноте исчисления предикатов. | СК-1 СК-3 |
| 6. | Неклассические логики. Многозначная логика Лукасевича. Нечёткие множества и нечёткая логика. Операции над нечёткими множествами. Нечёткие отношения. Нечёткие правила вывода | СК-1 СК-3 |
| 7. | Теория алгоритмов Машины Тьюринга. Алгоритмически неразрешимые задачи. Частично рекурсивные функции. Нумерация кортежей. | СК-1 СК-3 |
4. Объем дисциплины
4.1. Объем дисциплины и виды учебной работы
| Вид учебной работы | Количество часов по формам обучения | |
| Очная | ||
| Номера семестров: | 2 | |
| Аудиторные занятия (всего): В том числе: | 62 | |
| | Лекции (Л) | 26 |
| Практические занятия (ПЗ) | 36 | |
| Самостоятельная работа (СРС) (всего) В том числе: | 82 | |
| | Реферат | 15 |
| Конспект в рабочей тетради | 22 | |
| Аналитическая таблица | 15 | |
| Исследовательский проект | 30 | |
| Общая трудоемкость: часы/ зачетные единицы | 180 (5 ед.) | |
| Входной контроль (вид, № семестра) | тест | |
| Форма итоговой аттестации - № семестров | экзамен | |
- Распределение часов по темам и видам учебной работы
| Названия разделов и тем | Всего часов по учебному плану | Виды учебных занятий | ||||
| Аудиторные занятия, в том числе: | самостоя-тельная работа | |||||
| лекции (в том числе интерактивные) | практ. занятия | |||||
| Раздел 1. Алгебра высказываний | ||||||
| 1. Понятие о логике как науке. Этапы развития логики. Предмет математической логики. Роль математической логики в системе научного знания. | 7 | 1 | 2 | 4 | ||
| | ||||||
| 9 | 1 | 4 | 4 | ||
| 7 | 1 | 2 | 4 | ||
| 7 | 1 | 2 | 4 | ||
| Раздел 2. Исчисление высказываний | ||||||
| 6 | 1 | 1 | 4 | ||
| 7 | 1 | 2 | 4 | ||
| 6 | 1 | 1 | 4 | ||
| Раздел 3. Логика предикатов | ||||||
| 11 | 2 | 3 | 6 | ||
| 6 | 1 | 1 | 4 | ||
| 6 | 1 | 1 | 4 | ||
| Раздел 4. Исчисление предикатов | ||||||
| 10 | 1 | 3 | 6 | ||
| 12.Метатеория формальных систем. Характеристики систем (полнота, противоречивость, разрешимость). Теорема Геделя о неполноте теорий первого порядка включая формальную арифметику. | 12 | 2 | 2 | 8 | ||
| Раздел 5.Рекурсивные функции. | ||||||
| 13. Интуитивное понятие алгоритма. Свойства алгоритмов. Различные подходы к уточнению понятия алгоритма. | 11 | 2 | 3 | 6 | ||
| 14. Понятие частично-рекурсивных, рекурсивных и общерекурсивных функций. Базовые функции и базовые операции. Рекурсивность основных функции арифметики. Тезис Черча. | 11 | 2 | 3 | 6 | ||
| Раздел 6. Машины Тьюринга | ||||||
| 15. Машина Тьюринга, ее устройство. Действия над машинами Тьюринга. Функции, вычислимые и невычислимые на машине Тьюринга. | 16 | 5 | 4 | 7 | ||
| Раздел 7. Общие вопросы теории алгоритмов. | ||||||
| 16. Алгоритмически неразрешимые проблемы. Нумерации (Кантора, Геделя). | 10 | 2 | 2 | 6 | ||
| ИТОГО: | 180(36+ 144) | 26 | 36 | 82 | ||