М_РП1604 (1019131)
Текст из файла
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
МГАПИ
Кафедра “Управление и моделирование систем”
УТВЕРЖДАЮ
Проректор по учебной работе
_______________/ Соколов В.В./
«_____»____________2002г
РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ
Математическая логика и теория алгоритмов
ЕН.Ф.01.04
(1604)
Рекомендуется для направления подготовки
дипломированного специалиста
654600 - информатика и вычислительная техника
специальность - 22.04.00 –
Программное обеспечение вычислительной техники и автоматизированных систем
Москва 2004
-
Цели и задачи дисциплины
Целью преподавания дисциплины является ознакомление с математическим аппаратом дискретного анализа.
Задача дисциплины – получение базовых знаний в области математической логики, теории формальных систем и прикладной теории алгоритмов.
2. Требования к уровню освоения содержания дисциплины
Знания, приобретенные в результате освоения содержания дисциплины:
-
Основные логические функции одной и двух переменных.
-
Законы булевой алгебры.
-
Основные модели алгоритмов.
-
Меры сложности алгоритмов. Классы задач P и NP.
Умения и навыки, приобретенные в результате освоения дисциплины:
-
по разделу «Математической логики»:
Умение использовать функции алгебры логики в инженерной практике.
Умение использовать предикаты и кванторы.
Умение использовать принцип дедукции.
-
по разделу « Теория алгоритмов»:
Умение использовать рекурсивные функции.
Знать меры сложности алгоритмов.
Уметь различать классы задач P, NP и NP полные задачи.
-
Объем дисциплины и виды учебной нагрузки
Виды учебной нагрузки | Всего часов | Семестры | |
3 | 4 | ||
Общая трудоемкость дисциплины | 100 | 100 | |
Аудиторные занятия | 60 | 60 | |
Лекции | 34 | 34 | |
Практические занятия (ПЗ) | 8 | 8 | |
Семинары (С) | |||
Лабораторные занятия (ЛР) | 4 | 4 | |
и (или) другие виды аудиторных занятий | |||
Самостоятельная работа | 40 | 40 | |
Курсовой проект (работа) | |||
Расчетно-графические работы | |||
Реферат | |||
и (или) другие виды самостоятельных занятий | А,Д | А,Д | |
Дополнительные занятия | 14 | 14 | |
Вид итогового контроля | Экзамен | Экзамен |
4. Содержание дисциплины
В дисциплину должны входить следующие темы:
Логика высказываний; логика предикатов; исчисления; непротиворечивость; полнота; синтаксис и семантика языка логики предикатов. Клазуальная форма. Метод резолюций в логике предикатов. Принцип логического программирования. Темпоральные логики; нечеткая и модальные логики; нечеткая арифметика Ч. Хоара. Логика высказываний. Логическое следование, принцип дедукции. Метод резолюций. Аксиоматические системы, формальный вывод. Метатеория формальных систем. Понятие алгоритмической системы. Рекурсивные функции. Формализация понятия алгоритма; Машина Тьюринга. Тезис Черча; Алгоритмически неразрешимые проблемы. Меры сложности алгоритмов. Легко и трудноразрешимые задачи. Классы задач P и NP. NP- полные задачи. Понятие сложности вычислений; эффективные алгоритмы. Основы нечеткой логики. Элементы алгоритмической логики.
4.1. Разделы дисциплин и виды занятий (тематический план)
№ п/п | Раздел дисциплины | Лекции | ПЗ (или С) | ЛР |
1 | Введение в математическую логику. | 2 | ||
2 | Функции алгебры логики. Основные понятия и определения | 2 | ||
3 | Основные логические функции одной и двух переменных. | 2 | 2 | 2 |
4 | Основные законы булевой алгебры | 2 | 2 | 2 |
5 | Классификация логических функций | 2 | 2 | |
6 | Полнота и замкнутость логических функций. | 2 | 2 | |
7 | Аксиоматические системы, формальный вывод. | 2 | ||
8 | Исчисление высказываний | 2 | ||
9 | Синтаксис и семантика языка логики предикатов. | 2 | ||
10 | Метод резолюций в логике предикатов | 2 | ||
11 | Нечеткая и модальные логики | 2 | ||
12 | Понятие алгоритмической системы. | 2 | ||
13 | Формализация понятия алгоритма. Модели алгоритмов. | 2 | ||
14 | Рекурсивные функции. | 2 | ||
15 | Понятие о машине Тьюринга. Тезис Черча. | 2 | ||
16 | Меры сложности алгоритмов. Классы задач P и NP. | 2 | ||
17 | Понятие сложности вычислений |
-
1. Содержание разделов дисциплины.
№ лекции | № раздела | Содержание | Объем в часах | Семестр |
1 | 1 | Введение в математическую логику. | 2 | 4 |
2 | 1 | Логика высказываний. Основные понятия и определения. | 2 | 4 |
3 | 1 | Логические функции одной и двух переменных. | 2 | 4 |
4 | 1 | Основные законы булевой алгебры. | 2 | 4 |
5 | 1 | Классификация логических функций. | 2 | 4 |
6 | 1 | Полнота и замкнутость логических функций. | 2 | 4 |
7 | 1 | Введение в формальные системы. | 2 | 4 |
8 | 1 | Исчисление высказываний. | 2 | 4 |
9 | 1 | Синтаксис и семантика языка логики предикатов. | 2 | 4 |
10 | 1 | Метод резолюций в логике предикатов. | 2 | 4 |
11 | 1 | Неклассические логики. | 2 | 4 |
12 | 2 | Понятие алгоритмической системы. | 2 | 4 |
13 | 2 | Формализация понятия алгоритма. Модели алгоритмов. | 2 | 4 |
14 | 2 | Рекурсивные функции. | 2 | 4 |
15 | 2 | Понятие о машине Тьюринга. Тезис Черча. | 2 | 4 |
16 | 2 | Меры сложности алгоритмов. Классы задач P и NP. | 2 | 4 |
17 | 2 | Понятие сложности вычислений | 2 | 4 |
4.2.2 Содержание практических занятий
№ практич. занятия | № раздела | Содержание | Объем в часах | Семестр |
1 | 3 | Основные логические функции одной и двух переменных | 2 | 4 |
2 | 4 | Основные законы булевой алгебры | 2 | 4 |
3 | 5 | Классификация логических функций | 2 | 4 |
4 | 6 | Полнота и замкнутость логических функций | 2 | 4 |
4.2.3. Курсовая работа
Курсовая работа не предусмотрена.
Характеристики
Тип файла документ
Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.
Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.
Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.