Реферат: Рабочей программы учебной дисциплины дв2 Математическая логика и теория алгоритмов Уровень основной образовательной программы

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Государственное образовательное учреждение высшего профессионального образования

«Воронежский государственный педагогический университет»




















АННОТАЦИЯ


РАБОЧЕЙ ПРОГРАММЫ УЧЕБНОЙ ДИСЦИПЛИНЫ


Б3.ДВ2 Математическая логика и теория алгоритмов


^ Уровень основной образовательной программы: бакалавриат


Направлениеподготовки: 23700 Прикладная информатика

Профиль: 10 Прикладная информатика в образовании


Форма обучения: очная


Кафедра: информатики и методики преподавания математики

^ ФИО разработчиков Вахитов Р.Х., Потапов А.С.


Трудоемкость дисциплины 6 зачетных единиц

Количество часов 216

В.т.ч. аудиторных 90; внеаудиторных 90

Формаы отчетности зачет (4 семестр), экзамен (5 семестр)


г. Воронеж – 2011 г.



^ ЦЕЛИ ОСВОЕНИЯ ДИСЦИПЛИНЫ


Цель дисциплины «Математическая логика и теория алгоритмов» – формирование систематизированных знаний в области математической логики и теории алгоритмов, являющейся фундаментальным основанием, как материальной части компьютера, так и его программного обеспечения.

В процессе освоения данной дисциплины студент формирует и демонстрирует следующие компетенции:

способен при решении профессиональных задач анализировать социально-экономические проблемы и процессы в области образования с применением методов системного анализа и математического моделирования (ПК-2);

способен применять методы анализа прикладной области (образовательные системыя) на концептуальном, логическом, математическом и алгоритмическом уровнях (ПК-17);

способен применять системный подход и математические методы в формализации решения прикладных задач в области образования (ПК-21);



^ 2. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ



№ п/п

Наименование раздела учебной дисциплины

Содержание раздела

в дидактических единицах

1

Логика высказываний

Алгебра высказываний. Совершенные дизъюнктивные нормальные формы. Применения булевых законов к релейно-контактным схемам. Исчисление высказываний (ИВ). Свойства ИВ: непротиворечивость, полнота, независимость

2

Логика предикатов

Формулы логики предикатов и перевод математических предложений на язык формул. Языки и теории первого порядка. Интерпретации и модели. Общезначимые и истинные в теории формулы. Теоремы в теориях первого порядка. Свойства теорий первого порядка: непротиворечивость, полнота, категоричность

3

Алгоритмы и рекурсивные функции

Интуитивное понятие алгоритма и вычислимой функции. Разрешимые и перечислимые предикаты (отношения) . Частично и примитивно рекурсивные функции. Машины Тьюринга. Функции, вычислимые по Тьюрингу. Другие уточнения алгоритма: нормальные алгорифмы Маркова, регистровые машины

4

Теория вычислимости. Сложность алгоритмов

Нумерации. Универсальные функции. s-m-n-теорема. Невычислимые функции. Неразрешимые проблемы. Теорема о неподвижной точке. Меры сложности алгоритмов. Классы P и NP


^ 3. Образовательные технологии


Лекции: вводная лекция, лекция-информация, проблемная лекция, тематический зачет.


Лабораторные работы: ситуация-упражнение, технология проблемного обучения, технология учебного исследования.


^ 4. УЧЕБНО-МЕТОДИЧЕСКОЕ И ИНФОРМАЦИОННОЕ ОБЕСПЕЧЕНИЕ УЧЕБНОЙ ДИСЦИПЛИНЫ


4.1. Основная литература


1. Мендельсон Э. Введение в математическую логику. – М.: Либроком, 2010.

2. Ершов Ю.Л., Палютин Е.А. Математическая логика. - СПб.: Лань, 2004.

^ 3. Игошин В.И. Математическая логика и теория алгоритмов. - М.: Академия, 2008.

4. Игошин В.И. Задачи и упражнения по математической логике и теории алгоритмов. - М.: Академия, 2007.

^ 5. Судоплатов С.В., Овчинникова Е.В. Математическая логика и теория алгоритмов. - М.: Инфра-М, 2008.


4.2. Дополнительная литература


1. Мальцев А.И. Алгоритмы и рекурсивные функции. - М. Наука, 1986.

2. Новиков П.С. Элементы математической логики. - М.: Наука, 1973.

^ 3. Шенфилд Дж. Математическая логика. - М.: Наука, 1975.

4. Катленд Н. Вычислимость. Введение в теорию рекурсивных функций. - М.: Мир, 1983.

5. Мирзоев В.Н. Теория алгоритмов (теория вычислимых функций). - Воронеж, 2004.


4.3. Программное обеспечение и Интернет-ресурсы:


ПО для лабораторных работ: компьютерная система Mathematica.


Лаборатория математической логики: http://logic.pdmi.ras.ru/

Математическая логика в курсе информатики: http://infologos.narod.ru/

Машина Тьюринга 1.1 (симулятор машины Тьюринга): http://www.loonies.narod.ru/tmr.htm/

Электронные библиотеки по математике: www.4tivo.com/education/; www.matburo.ru/literat.php; www.plib.ru; http://nehudlit.ru; www.gaudeamus.omskcity.com; www.alleng.ru; www.symplex.ru; www.math.ru.