Geum.ru

Учебно-методический комплекс дисциплины математическая логика и теория алгоритмов 050100 Педагогическое образование

Вид материалаУчебно-методический комплекс
1. Сайт профессора кафедры математической логики и теории алгоритмов МГУ им. Ломоносова Пентуса М.Р.
9.3. Содержание и формы промежуточной аттестации
Подобный материал:
1   2   3

1. Сайт профессора кафедры математической логики и теории алгоритмов МГУ им. Ломоносова Пентуса М.Р.:


.msu.su/~pentus/problems.php

2. Сайт кафедры «Прикладной математики» Физико-механического фа­культета Санкт-Петербургского государственного технического универ­ситета: eva.ru/education/prog71.php

3. Сайт УГАТУ (рефераты и лекции):

www.twirpx.com/files/special/protection/  

4. Электронный вариант книги Носова В.А. «Алгоритмы и оценки их сложности»:

rrc.dgu.ru/res/intsys.msu.ru/staff/vnosov/theoralg.php

5. Электронный вариант книги Мальцева А.И. «Алгоритмы и рекурсив­ные функ­ции»:

ссылка скрыта


9. Содержание и порядок проведения входного и текущего контроля, промежуточной аттестации

9.1. Содержание и формы проведения входного контроля
    1. Содержание и формы текущего контроля знаний




№
Пороговый

СК -1
Знает: смысл основных понятий алгебры высказываний (АВ) и логики предикатов (ЛП), теории алгоритмов (ТА): высказывание, операции над высказываниями, таблица истинности, формула АВ, равносильные формулы, ДНФ, КНФ, предикат, кванторы, нормальная форма, алгоритм, машина Тьюринга, рекурсивная функция, вычислимая функция (описание).
Умеет: составлять таблицы истинности, применять основные равносильности, диагностировать формулу АВ (тождественно истинная, тождественно ложная, выполнимая), показывать выводимость из гипотез, записывать на языке предикатов математические объекты (определения, теоремы), показывать рекурсивность функций, строить машины Тьюринга;
Владеет: методом решения логических задач с помощью АВ; методами доказательства выводимости в построенном исчислении формул (теорем); способами уточнения понятия алгоритма в виде машин Тьюринга.

Продвинутый

Знает: смысл основных понятий АВ и ЛП, исчисления высказываний (ИВ) и предикатов (ИП), ТА: высказывания, действия над высказываниями (конъюнкция, дизъюнкция, импликация, эквивалентность), таблицы истинности, формулы АВ, равносильных формул, ДНФ, СДНФ, КНФ, СКНФ; аксиомы и их свойств (полнота, независимость) исчисления, правила вывода из аксиом, теорема дедукции, выводимой формулы, связь АВ и ИВ, свойства ИВ (непротиворечивость, полнота); предиката, квантора, нормальных форм и формул; формул ИП, аксиомы и их свойства ИП, выводимые формулы, теорема дедукции, свойства ИП (непротиворечивость, полнота; алгоритма, вычислимой функции, машины Тьюринга, действии над машинами, тезис Черча, тезис Тьюринга, рекурсивной функции (частично рекурсивной и примитивно рекурсивной));

Умеет: составлять таблицы истинности, применять основные равносильности, диагностировать формулу АВ (тождественно истинная, тождественно ложная, выполнимая), составлять СКНФ и СДНФ произвольной формулы, показывать выводимость из гипотез, записывать на языке предикатов математические объекты (определения, теоремы), проверять истинность формул методом резолюций, применять основные операции (рекурсии, суперпозиции, минимизации) к основным функциям (следования, ноль-функция, выбор аргумента), показывать рекурсивность функций, строить машины Тьюринга и производить действия с ними;

Владеет: методом решения логических задач и анализом РКС (релейно-контактных схем) с помощью АВ; методами доказательства выводимости в построенном исчислении формул (теорем) двумя различными способами; способами уточнения понятия алгоритма в виде машин Тьюринга и рекурсивных функций,

СК-2
Пороговый

Знает: способы построения аксиоматическим методом ИВ, уточнение определения алгоритма через машины Тьюринга, характеристики систем (полнота, противоречивость, разрешимость).
Умеет: приводить примеры полных систем, разрешимых и непротиворечивых, распознавать структуру системы (аксиомы, правила вывода и язык), строить МТ.
Владеет: методами построения МТ и рекурсивных функций.

Продвинутый

Знает: способы построения аксиоматическим методом ИВ и ИП, связь данных систем с АВ и ЛП, уточнение определения алгоритма через машины Тьюринга и рекурсивные функции, связь между тезисами Тьюринга и Черча, характеристики систем (полнота, противоречивость, разрешимость), примеры алгоритмически неразрешимых проблем.
Умеет: строить примеры полных систем, разрешимых и непротиворечивых, конструировать произвольные системы по заданным характеристикам (аксиомы, правила вывода и язык), строить произвольные МТ и рекурсивные функции, проводить аналогии между различными уточнениями алгоритма, показывать алгоритмическую неразрешимость некоторой задачи.
Владеет: методами построения МТ и рекурсивных функций, методами построения аксиоматических теории с заданными характеристиками.

СК-3
Пороговый

Знает: этапы формирования понятия алгоритма и аксиоматических систем.
Умеет: применить язык логики предикатов к анализу текстов.
Владеет: методикой построения необходимых и достаточных условий заданной задачи, навыком преобразований высказываний для анализа релейно-контактных схем и решения текстовых задач.

Продвинутый

Знает: этапы и методы формирования понятия алгоритма и аксиоматических систем.
Умеет: применить язык логики предикатов к анализу математических текстов (запись определения, предложения, теоремы) и построения противоположных. обратных утверждений данному и применять доказательство от противного.
Владеет: аксиоматическим методом анализу произвольной математической теории, методикой построения необходимых и достаточных условий произвольной задачи, навыком преобразований высказываний для анализа релейно-контактных схем и решения текстовых задач.


9.3. Содержание и формы промежуточной аттестации

Формы аттестации по дисциплине: экзамен.

Вопросы к экзамену:
  1. Высказывания. Логические операции над высказываниями.
  2. Понятие булевой функции. Число булевых функций от n переменных. Булевы функции от двух переменных. Связь между ними.
  3. Основные равносильности алгебры высказываний. ДНФ, ее нахождение, СДНФ.
  4. Понятие о полноте системы булевых функций. Примеры полных и неполных систем.
  5. Применение алгебры высказываний к переключательным схемам. Элементы «И», «ИЛИ», «НЕ». Понятие комбинаторной схемы.
  6. Применение алгебры высказываний к анализу рассуждений.
  7. Построение исчисления высказываний: алфавит, формула, аксиомы, правила вывода исчисления высказываний. Понятие доказательства (вывода) формулы в ИВ. Примеры выводимых формул.
  8. Вывод формулы из гипотез в исчислении высказываний. Его свойства. Примеры.
  9. Теорема дедукции в исчислении высказываний.
  10. Правила введения и удаления конъюнкции в исчислении высказываний.
  11. Правила введения и удаления дизъюнкции в исчислении высказываний.
  12. Правила введения и удаления двойного отрицания в исчислении высказываний.
  13. Законы прямой и обратной контрапозиции в исчислении высказываний.
  14. Интерпретация исчисления высказываний. Непротиворечивость исчисления высказываний.
  15. Лемма о полноте исчисления высказываний.
  16. Полнота исчисления высказываний. Теорема о полноте исчисления высказываний. Независимость системы аксиом.
  17. Понятие предиката. Способы задания предикатов. Примеры предикатов. Сигнатура. Определение формулы ЛП данной сигнатуры. Свободные и связанные переменные.
  18. Понятие модели данной сигнатуры и истинности формулы на модели. Примеры записи математических предложений формулами ЛП.
  19. Проблемы выполнимости, общезначимости и тождественной ложности формул логики предикатов. Связь между этими проблемами. Теорема Черча (без доказательства).
  20. Метод Генцена для решения проблемы выполнимости формул логики предикатов.
  21. Основные равносильности логики предикатов, их доказательство.
  22. Предваренная нормальная форма, ее нахождение.
  23. Построение исчисления предикатов: алфавит, формула, аксиомы. Правила вывода, определение вывода формулы и вывода из гипотез в ИП. Теоремы ЛП. Непротиворечивость ИП.

24. Интуитивное опре­де­ле­ние по­ня­тия «ал­го­ритм». Свой­ст­ва ал­го­рит­ма.

25. Про­стей­шие фун­кции. Опе­ра­ция под­ста­но­вки. Свой­ст­ва опе­ра­ции под­ста­но­вки. Опе­ра­ция при­ми­тив­ной ре­кур­сии. Свой­ст­ва опе­ра­ции при­ми­тив­ной ре­кур­сии. При­ми­тив­но-ре­кур­сивное опи­са­ние фун­кции.

26. При­ми­тив­но-ре­кур­сив­ная фун­кция. Свой­ст­ва при­ми­тив­но-ре­кур­сив­ных фун­кций. При­ме­ры при­ми­тив­но-ре­кур­сив­ных фун­кций. От­но­си­те­ль­ная при­ми­тив­ная ре­кур­сив­ность. Свой­ст­ва от­но­си­те­ль­ной при­ми­тив­ной ре­кур­сив­но­сти.

27. m-опе­ра­ция (опе­ра­ция ми­ни­ми­за­ции). Час­тич­но ре­кур­сив­ное опи­са­ние фун­к­ции. Час­тич­но ре­кур­сив­ная фун­кция. При­ме­ры час­тич­но ре­кур­сив­ных фун­кций. Об­ще­ре­кур­сив­ная фун­кция. При­ме­ры об­ще­ре­кур­сив­ных фун­кций.

28. Ма­ши­на Тью­рин­га. Опе­ра­ции над ма­ши­на­ми Тью­рин­га (опе­ра­ция ком­по­зи­ции, опе­ра­ция вет­вле­ния, опе­ра­ция за­цик­ли­ва­ния). Гё­де­ле­ва ну­ме­ра­ция ма­шин Тью­рин­га.

29. Фун­кция, вы­чис­ли­мая по Тью­рин­гу. До­ка­за­те­ль­ст­во су­ще­ст­во­ва­ния фун­к­ций, не­вы­чис­ли­мых по Тью­рин­гу. При­мер не­вы­чис­ли­мой по Тью­рин­гу фун­кции.

30. При­ме­ры ал­го­рит­ми­че­с­ки не­раз­ре­ши­мых проблем (про­бле­ма рас­по­зна­ва­ния са­мо­при­ме­ни­мо­сти, про­бле­ма при­ме­ни­мо­сти).