Министерство образования и науки Российской Федерации
Федеральное государственное бюджетное образовательное учреждение
«Уральский государственный педагогический университет»
Институт математики, информатики и информационных технологий
Кафедра высшей математики
РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ
«Математическая логика и теория алгоритмов»
для ОПОП 44.03.05 «Педагогическое образование»
(с двумя профилями подготовки)
ИНФОРМАТИКА И МАТЕМАТИКА
Уровень бакалавриата
Екатеринбург 2016
Рабочая программа дисциплины «Математическая логика и теория алгоритмов»
Составитель: , доцент, к. ф.-м. н., доцент, кафедра высшей математики Института математики, информатики и информационных технологий УрГПУ
(подпись)
Рабочая программа дисциплины обсуждена на заседании кафедры высшей
математики УрГПУ
Протокол от 10.03.16 г. № 6.
Зав. кафедрой
(подпись)
Руководитель учебного подразделения
(подпись)
1. ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
1.1. Наименование дисциплины: «Математическая логика и теория алгоритмов».
1.2. Цели и задачи дисциплины.
Цели изучения дисциплины заключаются в формировании и развитии у студентов общепрофессиональных и профессиональных компетенций, регламентируемых профильным ФГОС, в частности, выпускник, освоивший программу бакалавриата, должен обладать
– способностью использовать естественнонаучные и математические знания для ориентирования в современном информационном пространстве (ОК-3);
– готовностью реализовывать образовательные программы по учебным предметам в соответствии с требованиями образовательных стандартов
(ПК-1).
Задачи изучения дисциплины:
- сформировать у студентов четкое представление о языке первого порядка, как о языке математики;
- научить студентов пользоваться языком логики высказываний и языком логики предикатов;
- научить применять операторы суперпозиции, примитивной рекурсии и минимизации для построения частично рекурсивных функций;
- сформировать у студентов начальные навыки работы на машинах Тьюринга;
- сформировать представление о важности теории алгоритмов для осуществления будущей профессиональной деятельности.
1.3. Место дисциплины в структуре ОПОП.
Дисциплина «Математическая логика и теория алгоритмов» относится к обязательным дисциплинам вариативной части ОПОП «44.03.05- Педагогическое образование (с двумя профилями подготовки информатика и математика). Она непосредственно связана с дисциплинами естественнонаучного и математического цикла («Алгебра», «Геометрия», «Математический анализ», «Дискретная математика», «Информатика») и опирается на освоенные при изучении данных дисциплин знания и умения.
1.4. Перечень планируемых результатов обучения по дисциплине (модулю), соотнесенных с планируемыми результатами освоениями образовательной программы:
Процесс изучения дисциплины направлен на формирование следующих компетенций студентов
Общекультурные компетенции
ОК-3 – способностью использовать естественнонаучные и математические знания для ориентирования в современном информационном пространстве.
Профессиональные компетенции
ПК-1 – Готовность реализовывать образовательные программы по учебному предмету в соответствии с требованиями образовательных стандартов.
1.5. Объем дисциплины (модуля) в зачетных единицах.
Согласно учебному плану курс «Математическая логика и теория алгоритмов» на очном отделении изучается бакалаврами на4 курсе, во втором семестре. Форма контроля – экзамен. На очном отделении на изучение курса отводится 144 учебных часа, в т. ч. 56 уч. ч. аудиторных занятий и 88 уч. ч. самостоятельной работы. Аудиторные занятия включают 28 уч. ч. лекций и 28 уч. ч. практических занятий.
Общая трудоемкость дисциплины составляет 4 зачетные единицы.
1.6. Особенности реализации дисциплины (модуля).
Дисциплина «Математическая логика и теория алгоритмов» реализуется на русском языке.
2. УЧЕБНО-ТЕМАТИЧЕСКОЕ ПЛАНИРОВАНИЕ
Учебно-тематический план очной формы обучения
8 семестр
№ п/п | Наименование раздела, темы | Всего тру- доем- кость | Аудиторные занятия | Самостоя- тель- ная работа | |||
Все- го | Лек- ции | Пра- кти- чес- кие | Ла- бора- тор- ные | ||||
1 | Алгебра высказываний. | 16 | 6 | 2 | 2 | 10 | |
2 | Нормальные формы. | 16 | 6 | 2 | 4 | 10 | |
3 | Предикаты и кванторы. | 16 | 4 | 2 | 2 | 12 | |
4 | Модели. Интерпретации. | 16 | 4 | 2 | 2 | 12 | |
5 | Алгоритмы в математике. Числовые функции и алгоритмы их вычисления. | 12 | 4 | 2 | 2 | 8 | |
6 | Частично рекурсивные функции. Тезис Черча. | 20 | 10 | 4 | 4 | 10 | |
7 | Машины Тьюринга. Тезис Тьюринга. | 16 | 6 | 4 | 4 | 10 | |
8 | Машины с неограниченными регистрами. | 18 | 8 | 2 | 4 | 8 | |
9 | Вербальные и нормальные алгорифмы. Принцип нормализации Маркова. | 14 | 6 | 4 | 4 | 8 | |
Итого | 144 | 56 | 28 | 28 | 88 |
3. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ
3.1. Структурированное содержание дисциплины
№ п/п | Наименование раздела (темы) | Содержание раздела |
1 | Алгебра высказываний. | Операции над высказываниями и их свойства. Формулы логики высказываний. Применение логики высказываний к переключательным схемам. |
2 | Булевы функции. Нормальные формы | Булевы функции. Совершенная дизъюнктивная нормальная форма. Совершенная конъюнктивная нормальная форма. |
3 | Предикаты и кванторы. | Понятие n-местного предиката. Область истинности предиката. Формулы логики предикатов. Применение логики предикатов к анализу рассуждений. |
4 | Модели. Интерпретации. | Понятие модели заданной сигнатуры. Интерпретация формулы в модели. Применение языка логики предикатов для записи математических предложений, определений. Построение отрицаний. |
5 | Алгоритмы в математике. Числовые функции и алгоритмы их вычисления. | Алгоритмы в математике. Основные черты алгоритмов. Числовые функции и алгоритмы их вычисления. |
6 | Частично рекурсивные функции. Тезис Черча. | Простейшие функции. Операторы суперпозиции и примитивной рекурсии. Примитивно рекурсивные функции. Оператор минимизации. Частично рекурсивные и вычислимые функции. Тезис Черча. |
7 | Машины Тьюринга. Тезис Тьюринга. | Описание машины Тьюринга. Команды и программы машины Тьюринга. Вычисление значений функций на машине Тьюринга. Различные варианты машин Тьюринга и машин Поста. Тезис Тьюринга. |
8 | Машины с неограниченными регистрами. | Описание МНР. Команды и программы МНР. Вычисление частично рекурсивных функций на МНР. |
9 | Вербальные и нормальные алгорифмы. Принцип нормализации Маркова. | Вербальные алгорифмы. Алфавит и схема нормального алгорифма. Работа нормального алгорифма. Примеры нормальных алгорифмов. Принцип нормализации Маркова. |
3.2. Перечень тем лекционных занятий
Лекция № 1. Высказывания. Операции над высказываниями. Формулы алгебры высказываний. Основные законы.
Лекция № 2. Нормальные формы. СДНФ. СКНФ.
Лекция № 3, 4. Предикаты. Действия над предикатами. Кванторы. Формулы логики предикатов. Основные законы логики предикатов.
Лекция № 5. Модель данной сигнатуры. Интерпретация формулы в модели.
Лекция № 6, 7.. Алгоритмы в математике. Числовые функции и алгоритмы их вычисления.
Лекция № 8. Примитивно рекурсивные функции.
Лекция № 9. Частично рекурсивные и вычислимые функции. Тезис Черча.
Лекция № 10,11. Машины Тьюринга. Тезис Тьюринга.
Лекция № 12, 13. Машины с неограниченными регистрами.
Лекция № 14. Вербальные и нормальные алгорифмы.
3.3. Перечень тем практических занятий
Занятие № 1. Алгебра высказываний. Таблицы истинности.
Занятие № 2. Формулы алгебры высказываний.
Занятие № 3. Нормальные формы.
Занятие № 4. Совершенные нормальные формы.
Занятие № 5. Предикаты и кванторы.
Занятие № 6. Модели. Интерпретации.
Занятие № 7. Примитивно рекурсивные функции.
Занятие № 8. Частично рекурсивные функции.
Занятие № 9. Машины Тьюринга.
Занятие № 10. Вычислимость функций на машинах Тьюринга.
Занятие № 11. Машины с неограниченными регистрами.
Занятие № 12. Вычислимость частично рекурсивных функций на МНР.
Занятие № 13. Вычислимость функций на МНР.
Занятие № 14. Вербальные и нормальные алгорифмы.
3.4. Вопросы для контроля и самоконтроля
1. Операции над высказываниями.
2. Определение формулы логики высказываний.
3. Понятие равносильных формул, тавтологий, противоречий, выполнимой формулы.
4. Основные законы логики высказываний.
5. Определение формул вида ДНФ, КНФ, СДНФ, СКНФ.
6. Определение булевой функции.
7. Способы задания булевой функции.
8. Определение n-местного предиката.
9. Определение области истинности n-местного предиката.
10. Определение формулы логики предикатов.
11. Определение связанной и свободной переменной в формуле логики предикатов.
12. Определение модели сигнатуры S.
13. Определение интерпретации формулы логики предикатов в модели.
14. Определение значения формулы логики предикатов в данной модели при данной интерпретации.
15. Определение выполнимой, логически общезначимой, логически противоречивой формулы логики предикатов.
16. Определение замкнутой формулы логики предикатов.
17. Основные законы логики предикатов.
18. Определение терма теории.
19. Определение формулы теории первого порядка.
20. Как строятся теории первого порядка?
21. Примеры теорий первого порядка.
22. Понятие алгоритма (неформальное определение).
23. Три случая протекания алгоритмического процесса.
24. Происхождение термина «алгоритм».
25. Дискретность алгоритма.
26. Детерминированность алгоритма.
27. Массовость алгоритма.
28. Абстракция потенциальной осуществимости.
29. Необходимость уточнения понятия алгоритма.
30. Конструктивные объекты.
31. Счетные множества и их свойства.
32. Алгоритмы и функции.
33. Частичные функции.
34. Вычислимые функции.
35. Простейшие функции и их вычислимость.
36. Оператор суперпозиции S.
37. Оператор примитивной рекурсии R.
38. Определение примитивно рекурсивной функции. Примеры.
39. Операция введения фиктивных переменных.
40. Оператор минимизации M.
41. Определение частично рекурсивной функции.
42. Вычислимость частично рекурсивной функции.
43. Тезис Черча.
44. Описание машины Тьюринга.
45. Программы машины Тьюринга.
46. Выполнение инструкции.
47. Вычисление значений функций на машине Тьюринга.
48. Тезис Тьюринга.
49. Другие варианты определения машины Тьюринга.
50. Конфигурация машины.
51. Применение машины Тьюринга к словам.
52. Описание машины с неограниченными регистрами.
53. Условие остановки МНР.
54. Вычисление функций на МНР.
55. Вычислимость простейших функций на МНР.
56. Стандартный вид программы.
57. Соединение программ.
58. Выделения регистров для подпрограммы.
59. Вставка подпрограммы.
60. Вычислимость частично рекурсивных функций на МНР, полученных с помощью оператора суперпозиции.
61. Вычислимость частично рекурсивных функций на МНР, полученных с помощью оператора примитивной рекурсии.
62. Вычислимость частично рекурсивных функций на МНР, полученных с помощью оператора минимизации.
63. Вербальные алгорифмы.
64. Алфавит и схема нормального алгорифма.
65. Работа нормального алгорифма.
66. Примеры нормальных алгорифмов.
67. Принцип нормализации.
3.5. Перечень тем занятий, реализуемых в активной и интерактивной формах
Занятие № 1. Алгебра высказываний. Таблицы истинности.
Занятие № 2. Формулы алгебры высказываний.
Занятие № 5. Предикаты и кванторы.
Занятие № 7. Примитивно рекурсивные функции.
Занятие № 8. Частично рекурсивные функции.
Занятие № 11. Машины с неограниченными ресурсами.
4. ПЕРЕЧЕНЬ УЧЕБНО-МЕТОДИЧЕСКОГО ОБЕСПЕЧЕНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ ОБУЧАЮЩИХСЯ ПО ДИСЦИПЛИНЕ (МОДУЛЮ)
4.1. Темы, вынесенные на самостоятельное изучение для студентов очной обучения
1. Булевы функции.
2. Различные варианты машин Тьюринга и машин Поста.
3. Вычисление частично рекурсивных функций на МНР.
4.2 Вопросы для подготовки к теоретической части экзамена
1. Операции над высказываниями. Определение формулы логики высказываний. Основные законы логики высказываний.
2. Понятие равносильных формул, тавтологий, противоречий, выполнимой формулы.
3. Определение формул вида ДНФ, КНФ, СДНФ, СКНФ.
4. Определение булевой функции. Способы задания булевой функции.
5. Определение n-местного предиката. Определение области истинности n-местного предиката.
6. Определение формулы логики предикатов. Определение выполнимой, логически общезначимой, логически противоречивой формулы логики предикатов.
7. Определение связанной и свободной переменной в формуле логики предикатов. Определение замкнутой формулы логики предикатов.
8. Определение модели сигнатуры S.
9. Определение интерпретации формулы логики предикатов в модели. Определение значения формулы логики предикатов в данной модели при данной интерпретации.
10. Основные законы логики предикатов.
11. Определение формулы теории первого порядка. Примеры теорий первого порядка.
12. Алгоритмы и функции. Частичные функции. Вычислимые функции.
13. Простейшие функции и их вычислимость.
14. Оператор суперпозиции S. Оператор примитивной рекурсии R.
15. Определение примитивно рекурсивной функции. Примеры.
16. Операция введения фиктивных переменных.
17. Оператор минимизации M.
18. Определение частично рекурсивной функции.
19. Вычислимость частично рекурсивной функции.
20. Тезис Черча.
21. Описание машины Тьюринга. Программы машины Тьюринга. Вычисление значений функций на машине Тьюринга.
22. Тезис Тьюринга.
23. Описание машины с неограниченными регистрами. Условие остановки МНР. Вычисление функций на МНР.
24. Вычислимость частично рекурсивных функций на МНР
25. Алфавит и схема нормального алгорифма. Принцип нормализации.
5. ФОНД ОЦЕНОЧНЫХ СРЕДСТВ ДЛЯ ПРОВЕДЕНИЯ ПРОМЕЖУТОЧНОЙ АТТЕСТАЦИИ ПО ДИСЦИПЛИНЕ (МОДУЛЮ)
Смотри Приложение 1.
6. УЧЕБНО-МЕТОДИЧЕСКОЕ И ИНФОРМАЦИОННОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ
6.1. Рекомендуемая литература
Основная
1. Ершов, Юрий Леонидович. Математическая логика : Учеб. пособие / , . — 4-е изд., стер. — СПб. : Лань, 2005. — 336с. — (Учебники для вузов. Специальная литература). — ISBN 5-8114-0533. [25 экз.]
2. Игошин, Владимир Иванович. Математическая логика и теория алгоритмов [Текст] : учеб. пособие для студентов вузов по спец. "Математика" / . — / 2-е изд., стер. — М. : Академия, 2008. — 448 с. : ил. — (Высшее профессиональное образование). — Библиогр.: с. 435-442. — Допущено М-вом образования РФ. — ISBN 978-5-7695-45931 [50 экз.]
3. Игошин, Владимир Иванович. Задачник-практикум по математической логике : Учеб. пособие для студентов-заочников физ.-мат. фак. пед. ин-тов / . — Подольск : Академия, 2005. — 156с. : ил. [99 экз.]
4. Ильиных, Анатолий Петрович. Математическая логика : Учеб. пособие / Урал. гос. пед. ун-т. – Екатеринбург : Б. и., 2002. – 71с.–[192 экз.]
5. Ильиных, Анатолий Петрович. Теория алгоритмов [Текст] : учеб. пособие / ; Урал. гос. пед. ун-т. –Екатеринбург : [б. и.], 2006. – 148 с. [188 экз.]
6. Судоплатов, логика и теория алгоритмов. Учебник [Электронный ресурс] / ; — Новосибирск : НГТУ, 2012. — 254 с. — (Учебники НГТУ). — ISBN 978-5-7782-1838-3. — <URL: http://biblioclub. ru/index. php? page=book&id=135676>.
Дополнительная
1. Лавров, Игорь Андреевич. Задачи по теории множеств, математической логике и теории алгоритмов / , . – 5-е изд., испр. – М.: Физ-матлит, 2004. – 256с. – Библиогр.: с.248-249. – ISBN 5-9221-0026- [3 экз.]
2. Матрос, Дмитрий Шаевич. Теория алгоритмов [Текст] : учеб. для студентов вузов по спец. 050202.65(030100) - информатика / , . — М. : БИНОМ. Лаб. знаний, 2008. – 202 с. – (Педагогическое образование). – Библиогр. : с. 196-197. – Рек. Учеб.-метод. об-нием. – ISBN 978-5-94774-226-8 (3 экз.).
3. Балюкевич, логика и теория алгоритмов. Учебно-практическое пособие [Электронный ресурс] / ; — Москва : Евразийский открытый институт, 2009. — 189 с. — ISBN 978-5-374-00220-1. — <URL: http://biblioclub. ru/index. php? page=book&id=93166>.
4. Тихомирова, алгоритмов. Учебное пособие [Электронный ресурс] / — Москва : МИФИ, 2008. — 176 с. — ISBN 978-5-7262-1078-0. — <URL: http://biblioclub. ru/index. php? page=book&id=231616>.
6.2 Информационное обеспечение дисциплины
1. Эмулятор Машины Тьюринга. 2015, электрон. опт. диск (CD-ROM).
2. Эмулятор МНР. 2015, электрон. опт. диск (CD-ROM).
7. МАТЕРИАЛЬНО-ТЕХНИЧЕСКОЕ И ДИДАКТИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ
При изучении дисциплины рекомендуется использовать технические средства обучения (персональные компьютеры, медиа проектор).
8. СВЕДЕНИЯ ОБ АВТОРЕ ПРОГРАММЫ
Фамилия Имя Отчество |
|
ученая степень | к. ф.-м. н. |
ученое звание | доцент |
должность и место работы | доцент, каф. высшей математики |
рабочий телефон | (343) 371-29-10 |
Приложение 1
Материалы ФОС
для промежуточной аттестации (экзамена) по дисциплине «Б1.В. ОД.2.6. – Математическая логика и теория алгоритмов»
для ОПОП направления подготовки 44.03.05 Педагогическое образование
(с двумя профилями подготовки) «Информатика и математика»
Промежуточная аттестация (экзамен) по дисциплине проводятся письменно и с последующим индивидуальным собеседованием со студентом по результатам его письменного ответа.
1°. Перечень компетенций формируемых в процессе освоения дисциплины, заявленных в РУПД:
Общекультурные компетенции
ОК-3 – способность использовать естественнонаучные и математические знания для ориентирования в современном информационном пространстве.
Профессиональные компетенции
ПК-1 – Готовность реализовывать образовательные программы по учебному предмету в соответствии с требованиями образовательных стандартов.
