- •Рецензенты:
- •Содержание
- •1.4. Тематические планы изучения учебной дисциплины
- •2. Учебно-методическое обеспечение дисциплины.
- •2.1. Методические указания и задания для контрольных работ студентам специальности 230102 заочной формы обучения.
- •Предисловие
- •2. Примеры решения типовых задач
- •Контрольная работа
- •С помощью диаграмм Эйлера-Вена показать результаты следующих операций:
- •Множество r определяет отношение на множестве . Найдите все упорядоченные пары ему принадлежащие:
- •Запишите с помощью кванторов и предикатов следующие утверждения:
- •Вопросы для самопроверки
- •Тесты проверки знаний студентов
- •Тест II
- •Тест III
- •Тест IV
- •Рекомендуемая литература
- •2.3. Основная:
- •2.4. Дополнительная:
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕХНОЛОГИЙ И УПРАВЛЕНИЯ
КАФЕДРА
«Высшая математика»
РАБОЧАЯ УЧЕБНАЯ ПРОГРАММА
ПО УЧЕБНОЙ ДИСЦИПЛИНЕ
«Математическая логика и теория алгоритмов»
Специальность: 230100.62 «Информатика и вычислительная техника»
Москва
2010
УДК
К-72
Обсуждена и одобрена на заседании кафедры «Высшая математика» Московского государственного университета технологий и управления (протокол № 4 от 23 декабря 2009 г.).
Одобрена и рекомендована к изданию учебно-методическим советом Московского государственного университета технологий и управления (протокол № ___ от «____» 200 г.)
Одобрена и рекомендована к утверждению на заседании ученого совета института «Системной автоматизации и инноватики» Московского государственного университета технологий и управления (протокол № 8 от 24 декабря 2009г.).
Составитель:
Садыкова Альбина Рифовна – к.п.н., доцент, кафедра «Высшая математика» МГУТУ
Рецензенты:
Копанева Анна Александровна – к.ф-м.н., доцент кафедры «Высшая математика»
Садыкова А.Р.
Математическая логика и теория алгоритмов: рабочая учебная программа. М.: МГУТУ, 2010. – 25 с.
Рабочая учебная программа учебной дисциплины «Математическая логика и теория алгоритмов» цикла ОПД составлена в соответствии с Государственным образовательным стандартом высшего профессионального образования по специальности 230100 «Информатика и вычислительная техника». Предназначена для студентов всех форм обучения.
© Московский Государственный университет
технологий и управления, 2010.
109004, Москва, Земляной вал, 73
© Садыкова А.Р.
Содержание
1. Организационно-методический раздел 4
1.1. Цели и задачи изучения дисциплины 4 1.2. Содержание дисциплины 4 1.3. Объем часов по видам учебной нагрузки 4 1.4. Тематические планы изучения учебной дисциплины 7
2. Учебно-методическое обеспечение дисциплины 13
2.1. Методические указания по выполнению курсовых, контрольных работ 13 2.2. Задания для самостоятельной работы студентов 20 (вопросы для самоконтроля знаний студентов, тестовые задания, вопросы для подготовки к экзамену и (или) зачету) 2.3. Основная литература 24 2.4. Дополнительная литература 25
|
1. Организационно-методический раздел
1.1. Цели и задачи изучения дисциплины
Целью курса является приобретение навыков работы с дискретными структурами, умения подсчитывать число комбинаторных объектов различной природы, а также получение представления о принципах помехоустойчивого и криптографического кодирования.
1.2. Содержание дисциплины
-
Канторова теория множеств.
-
Логика высказываний и логика предикатов, булевы функции.
-
Машина Тьюринга и понятие алгоритма.
-
Графы и алгоритмы на графах: паросочетание, кратчайший путь, минимальное основное дерево, задача коммивояжера.
-
Матроиды, жадный алгоритм.
-
Алгоритмы полиномиальной и экспоненциальной сложности. Классы P и NP, NP – полные задачи.
1.3. Объем часов по видам учебной нагрузки
Специальность 2202 |
Объем в часах по плану |
Количество |
||||
всего |
лекции |
практика |
Экз. |
Зач. |
Контр. работа |
|
Очная полная |
72 |
36 |
36 |
- |
1 |
- |
Очная сокращенная |
52 |
24 |
28 |
- |
1 |
- |
Очно-заочная полная |
56 |
24 |
32 |
- |
1 |
- |
Очно-заочная сокращенная |
40 |
16 |
24 |
- |
1 |
- |
Заочная полная |
32 |
20 |
12 |
- |
1 |
- |
Заочная соращкнная |
20 |
12 |
8 |
- |
1 |
1 |
Самостоятельная работа студентов по курсу «Математическая логика и теория алгоритмов».
Наименование дисциплины |
Форма обучения
|
Виды самостоятельной работы |
СФО, час |
ПФО, час |
|||
СФО
|
ПФО |
||||||
Курс |
Кол-во часов |
Курс |
Кол-во часов |
||||
ДФО |
I |
48 |
II |
28 |
1. Освоение теоретических основ дисциплины. |
18 |
6 |
2. Решение задач. |
5 |
5 |
|||||
3. Подготовка к выполнению контрольных работ. |
5 |
5 |
|||||
4. Выполнение контрольной работы. |
5 |
5 |
|||||
5. Подготовка к зачету. |
15 |
7 |
|||||
ВФО |
I |
60 |
II |
44 |
1. Освоение теоретических основ дисциплины. |
20 |
16 |
2. Решение задач. |
5 |
5 |
|||||
3. Подготовка к выполнению контрольных работ. |
10 |
5 |
|||||
4. Выполнение контрольной работы. |
5 |
5 |
|||||
5. Подготовка к зачету. |
20 |
13 |
|||||
ЗФО |
I |
80 |
I |
68 |
1. Освоение теоретических основ дисциплины. |
20 |
13 |
2. Решение задач. |
15 |
15 |
|||||
3. Подготовка к выполнению контрольных работ. |
15 |
10 |
|||||
4. Выполнение контрольной работы. |
20 |
20 |
|||||
5. Подготовка к зачету. |
10 |
10 |