Введение в алгоритмы - Камский институт гуманитарных и

Негосударственное образовательное учреждение
высшего профессионального образования
«Камский институт гуманитарных и инженерных технологий»
Факультет инженерных технологий
Кафедра «Автоматизированные системы проектирования и программное обеспечение»
УТВЕРЖДАЮ
РЕКТОР НОУ ВПО «КИГИТ»
____________В.А.НИКУЛИН
_________________ 2014 Г.
РЕШЕНИЕ УМС
ПРОТОКОЛ № 1ОТ 12.09 .2014 Г.
УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС
дисциплины «Введение в алгоритмы»
направление подготовки
231000.62 «Программная инженерия»
профиль подготовки
«Разработка программно-информационных систем»
Квалификация (степень) выпускника: бакалавр
Форма обучения очная
Ижевск – 2014
Рассмотрена и утверждена на заседании кафедры «Автоматизированные
системы проектирования и программное обеспечение»
Протокол № 1от «25» 09.2014 г.
Зав. кафедрой - М.А.Сенилов
СОГЛАСОВАНО
Начальник УМУ
_________________ Н.Г.Русинова
Составитель: д.т.н., профессор -Сенилов М.А.
Рецензент: д.т.н., профессор кафедры ПО ИжГТУ - Мурынов А.И.
Учебно-методический комплекс по дисциплине «Введение в алгоритмы»
разработан в соответствии с требованиями Федерального государственного
образовательного стандарта высшего профессионального образования и
основной образовательной программы по направлению подготовки 231000.62
«Программная инженерия» для профиля подготовки «Разработка программноинформационных систем».
Программа предназначена для преподавателей и студентов.
© Сенилов М.А. 2014
© НОУ ВПО «Камский институт гуманитарных и инженерных технологий», 2014
2
СОДЕРЖАНИЕ
НОРМАЛЬНЫЕ АЛГОРИТМЫ МАРКОВА........................................................................................14
ПЕРЕХОД К ВРЕМЕННЫМ ОЦЕНКАМ............................................................................................14
НОРМАЛЬНЫЕ АЛГОРИТМЫ МАРКОВА........................................................................................18
ПЕРЕХОД К ВРЕМЕННЫМ ОЦЕНКАМ............................................................................................18
3
РАБОЧАЯ ПРОГРАММА
ЦЕЛИ И ЗАДАЧИ ДИСЦИПЛИНЫ
Целью освоения дисциплины является ознакомление студентов с теоретическими и
алгоритмическими основами базовых разделов теории алгоритмов.
Задачами изучения данной дисциплины являются:
- обучение студентов теоретическим основам теории алгоритмов;
- развитие у студентов алгоритмического мышления;
- освоение студентами приемов исследования и решения математически
формализованных задач;
- выработка умения применять полученные знания для разработки алгоритмов и их
анализа при формализации и решении прикладных задач на ЭВМ.
2. МЕСТО ДИСЦИПЛИНЫ В СТРУКТУРЕ ООП
Дисциплина «Введение в алгоритмы» принадлежит к дисциплинам по выбору
вариативной части профессионального цикла.
Изучение дисциплины базируется на знаниях, полученных при изучении дисциплин:
«Математический анализ», «Дискретная математика», «Теоретическая информатика»,
«Основы программирования».
Данная дисциплина является предшествующей для дисциплин: «Конструирование
программного обеспечения», «Системы искусственного интеллекта».
3. КОМПЕТЕНЦИИ ОБУЧАЮЩЕГОСЯ, ФОРМИРУЕМЫЕ В РЕЗУЛЬТАТЕ
ОСВОЕНИЯ ДИСЦИПЛИНЫ
Процесс изучения дисциплины «Введение в алгоритмы» направлен на
формирование следующих профессиональных (ПК) компетенций:
- понимание основных концепций, принципов, теорий и фактов,
связанных с информатикой (ПК-1);
- способность к формализации в своей предметной области с учетом
ограничений используемых методов исследования (ПК-2);
- готовность к использованию методов и инструментальных средств
исследования объектов профессиональной деятельности (ПК-3);
- умение применять основы информатики и программирования к
проектированию, конструированию и тестированию программных продуктов
(ПК-10).
В результате изучения дисциплины студент должен
знать:
- основные понятия теории алгоритмов: интуитивная концепция алгоритма,
уточнения понятия алгоритма (машины Тьюринга и нормальные алгоритмы
Маркова), понятия вычислимости, разрешимости;
- основные неразрешимые массовые проблемы;
- временные и емкостные оценки алгоритмов;
4
уметь:
- строить алгоритмы для решения прикладных задач на ЭВМ;
- составлять программы машин Тьюринга и схемы нормальных алгоритмов
для решения простых вычислительных задач;
- проводить анализ алгоритмов;
владеть:
- основными приемами разработки алгоритмов и их программирования с
применением современных инструментальных средств.
4. ОБЪЕМ ДИСЦИПЛИНЫ И ВИДЫ УЧЕБНОЙ РАБОТЫ
Общая трудоемкость дисциплины составляет 2 зачётные единицы - 72
часа.
Вид учебной работы
Аудиторные занятия (всего)
в том числе:
Лекции
Практические занятия (ПЗ)
Лабораторные работы (ЛР)
КСР
Самостоятельная работа (всего)
В том числе:
Курсовая работа
Расчетно-графические работы
Реферат
Другие виды самостоятельной работы
коллоквиум
Виды промежуточной аттестации (зачёт, экзамен)
Общая трудоемкость, час/зач. ед.
5
Всего
часов
56
18
28
8
2
16
-
Семестр
4
56
16
16
-
Зачет
72/2
72/2
18
28
8
2
16
-
5. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ
5.1. Содержание разделов дисциплины
Введение.
Организация учебного процесса. Рекомендуемая литература. Цели и
задачи курса, связь с другими дисциплинами.
1. Алгоритмы и вычислимость
1.1. Задачи и алгоритмы.
Массовая проблема и индивидуальная задача. Неформальное определение
алгоритма. свойства алгоритма. различные подходы к формализации понятия
алгоритма.
1.2. Машина Тьюринга.
Неформальное описание машины Тьюринга. Внешний алфавит, алфавит
состояний, функциональная схема, принцип работы. Вычислимые по
Тьюрингу функции, основная гипотеза теории алгоритмов.
1.3. Рекурсивные функции.
Описание класса рекурсивных функций: базисные функции (нульфункция, функция следования и функция-проектор), операторы суперпозиции,
примитивной рекурсии и минимизации. примитивно-рекурсивные и частичнорекурсивные функции. Тезис Черча.
1.4. Нормальные алгоритмы Маркова.
Алфавит, слова, простые и заключительные формулы. Подстановки и
нормальные алгоритмы Маркова. нормально вычислимые функции, принцип
нормализации Маркова. совпадение классов частично рекурсивных,
нормально вычислимых и вычислимых по Тьюрингу функций.
1.5. Сравнительный анализ основных моделей представления
алгоритмов.
Абстрактные алгоритмические модели. Классы алгоритмических задач.
Вычислимая функция и разрешимое множество. Эквивалентность
абстрактных алгоритмических моделей.
1.6. Алгоритмически неразрешимые проблемы.
Алгоритмически неразрешимые проблемы. Нумерация алгоритмов,
машин Тьюринга. Проблемы распознавания самоприменимости и
применимости. проблема остановки. 10-я проблема Гильберта. Проблема
определения общерекурсивности алгоритма. проблема эквивалентности
алгоритмов.
1.7. Построение эффективных алгоритмов. Метод декомпозиции.
Метод декомпозиции.
2. Анализ алгоритмов
2.1. Сравнительные оценки алгоритмов.
Временная и емкостная сложность. Трудоемкость алгоритма, функции
оценки трудоемкости алгоритма: лучший, худший и средний случай.
2.2. Классификация алгоритмов по виду функции трудоёмкости.
Классификация алгоритмов по виду функции трудоемкости:
6
количественно-зависимые по трудоемкости алгоритмы, параметрическизависимые, количественно-параметрические, порядково-зависимые.
2.3. Трудоемкость основных алгоритмических конструкций.
Элементарные операции. Трудоемкость основных алгоритмических
конструкций: следования, ветвления и цикла.
2.4. Переход к временным оценкам.
Методики перехода к временным оценкам: пооперационный анализ, метод
гиббсона, метод прямого определения среднего времени.
2.5. Сложностные классы задач.
Теоретический предел трудоемкости задачи. Сложностные классы задач:
класс p (задачи с полиномиальной сложностью), класс np (полиномиально
проверяемые задачи), класс NPC (NP – полные задачи).
зачетн. ед. Всего час./
5.2. Содержание модулей дисциплины
Наименование модулей
№
п
/п
Виды учебной работы, включая
самостоятельную работу студентов и
трудоемкость (в часах)
Л
ПЗ
ЛЗ
2
2
-
КСР
СРС
МОДУЛЬ 1. АЛГОРИТМЫ И ВЫЧИСЛИМОСТЬ
1.1
ЗАДАЧИ И АЛГОРИТМЫ
5
1.2
-
1
МАШИНА ТЬЮРИНГА
12
2
4
4
-
2
6
2
3
-
-
1
5
2
2
-
-
1
7
2
3
-
-
2
8
2
2
2
-
2
4
1
2
-
-
1
4
4
1
1
2
2
-
-
1
1
1.3 РЕКУРСИВНЫЕ ФУНКЦИИ
1.4 НОРМАЛЬНЫЕ АЛГОРИТМЫ МАРКОВА
1.5 СРАВНИТЕЛЬНЫЙ АНАЛИЗ ОСНОВНЫХ
МОДЕЛЕЙ ПРЕДСТАВЛЕНИЯ АЛГОРИТМОВ
1.6 АЛГОРИТМИЧЕСКИ
НЕРАЗРЕШИМЫЕ
ПРОБЛЕМЫ
1.7 ПОСТРОЕНИЕ ЭФФЕКТИВНЫХ
АЛГОРИТМОВ. МЕТОД ДЕКОМПОЗИЦИИ
МОДУЛЬ 2. АНАЛИЗ АЛГОРИТМОВ
2.1 СРАВНИТЕЛЬНЫЕ ОЦЕНКИ АЛГОРИТМОВ
2.2 КЛАССИФИКАЦИЯ АЛГОРИТМОВ ПО ВИДУ
7
ФУНКЦИИ ТРУДОЁМКОСТИ
-
2.3 ТРУДОЕМКОСТЬ
ОСНОВНЫХ
АЛГОРИТМИЧЕСКИХ КОНСТРУКЦИЙ
7
1
2
2
-
2
4
1
2
-
-
1
6
1
2
-
2
1
72/2
18/0,5
28/0,78
8/0,22
2.4 ПЕРЕХОД К ВРЕМЕННЫМ ОЦЕНКАМ
2.5 СЛОЖНОСТНЫЕ КЛАССЫ ЗАДАЧ
Зачет
ИТОГО (час./ЗЕ)
5.3. Разделы дисциплины и
(последующими) дисциплинами
междисциплинарные
связи
с
2/0,06
16/0,44
обеспечиваемыми
№ п/п Наименование обеспечивае-№№ тем данной дисциплины, необходимых для изучемых (последующих) дисци-ния обеспечиваемых (последующих) дисциплин
плин
1.1
1.2
1.3
1.4
1.5
1.6
1.7
1 Конструирование
+
+
+
+
программного обеспечения
2
Системы
интеллекта
искусственного
+
+
+
+
+
+
+
№ п/п Наименование обеспечивае-№№ тем данной дисциплины, необходимых для изучемых (последующих) дисци-ния обеспечиваемых (последующих) дисциплин
плин
2.1
2.2
2.3
2.4
2.5
1 Конструирование
+
+
программного обеспечения
2
Системы
интеллекта
искусственного
+
+
8
+
+
+
6. ЛАБОРАТОРНЫЙ ПРАКТИКУМ
№ п/п
№ раздела
дисциплины
1
2
3
ИТОГО
1.2
1.4
2.1
Трудоемкость,
час./ЗЕ
4
2
2
8/0,22
Наименование лабораторных работ
КОНСТРУИРОВАНИЕ МАШИН ТЬЮРИНГА
НОРМАЛЬНО ВЫЧИСЛИМЫЕ ФУНКЦИИ
ОЦЕНКА СЛОЖНОСТИ АЛГОРИТМОВ
7. ПРАКТИЧЕСКИЕ ЗАНЯТИЯ
№ п/п
1
№ раздела
дисциплины
1.1
ТрудоемТематика практических занятий (семинаров)
МАССОВАЯ
ПРОБЛЕМА
НЕФОРМАЛЬНОЕ
АЛГОРИТМА.
И
ИНДИВИДУАЛЬНАЯ
ОПРЕДЕЛЕНИЕ АЛГОРИТМА.
РАЗЛИЧНЫЕ
ЗАДАЧА.
кость,
час./ЗЕ
2
СВОЙСТВА
ПОДХОДЫ К ФОРМАЛИЗАЦИИ
ПОНЯТИЯ АЛГОРИТМА.
2
1.2
НЕФОРМАЛЬНОЕ ОПИСАНИЕ МАШИНЫ ТЬЮРИНГА.
ВНЕШНИЙ
АЛФАВИТ,
АЛФАВИТ
СОСТОЯНИЙ,
ФУНКЦИОНАЛЬНАЯ
СХЕМА,
ПРИНЦИП
РАБОТЫ.
ВЫЧИСЛИМЫЕ ПО ТЬЮРИНГУ ФУНКЦИИ, ОСНОВНАЯ
ГИПОТЕЗА ТЕОРИИ АЛГОРИТМОВ.
4
3
1.3
ОПИСАНИЕ
КЛАССА РЕКУРСИВНЫХ ФУНКЦИЙ: БАЗИСНЫЕ
ФУНКЦИИ (НУЛЬ-ФУНКЦИЯ, ФУНКЦИЯ СЛЕДОВАНИЯ И
ФУНКЦИЯ-ПРОЕКТОР),
ОПЕРАТОРЫ
СУПЕРПОЗИЦИИ,
ПРИМИТИВНОЙ
РЕКУРСИИ
И
МИНИМИЗАЦИИ.
ПРИМИТИВНО-РЕКУРСИВНЫЕ И ЧАСТИЧНО-РЕКУРСИВНЫЕ
ФУНКЦИИ. ТЕЗИС ЧЕРЧА.
3
4
1.4
АЛФАВИТ, СЛОВА, ПРОСТЫЕ И ЗАКЛЮЧИТЕЛЬНЫЕ
ФОРМУЛЫ. ПОДСТАНОВКИ И НОРМАЛЬНЫЕ АЛГОРИТМЫ
МАРКОВА.
НОРМАЛЬНО
ВЫЧИСЛИМЫЕ
ФУНКЦИИ,
ПРИНЦИП
НОРМАЛИЗАЦИИ
МАРКОВА. СОВПАДЕНИЕ
КЛАССОВ
ЧАСТИЧНО
РЕКУРСИВНЫХ,
НОРМАЛЬНО
ВЫЧИСЛИМЫХ И ВЫЧИСЛИМЫХ ПО ТЬЮРИНГУ ФУНКЦИЙ.
2
5
1.5
АБСТРАКТНЫЕ
3
АЛГОРИТМИЧЕСКИЕ МОДЕЛИ. КЛАССЫ
АЛГОРИТМИЧЕСКИХ ЗАДАЧ. ВЫЧИСЛИМАЯ ФУНКЦИЯ И
РАЗРЕШИМОЕ
МНОЖЕСТВО.
ЭКВИВАЛЕНТНОСТЬ
АБСТРАКТНЫХ АЛГОРИТМИЧЕСКИХ МОДЕЛЕЙ.
9
6
1.6
АЛГОРИТМИЧЕСКИ
НЕРАЗРЕШИМЫЕ
ПРОБЛЕМЫ.
НУМЕРАЦИЯ
АЛГОРИТМОВ,
МАШИН
ТЬЮРИНГА.
ПРОБЛЕМЫ РАСПОЗНАВАНИЯ САМОПРИМЕНИМОСТИ И
ПРИМЕНИМОСТИ. ПРОБЛЕМА ОСТАНОВКИ. 10-Я ПРОБЛЕМА
ГИЛЬБЕРТА.
ПРОБЛЕМА
ОПРЕДЕЛЕНИЯ
ОБЩЕРЕКУРСИВНОСТИ
АЛГОРИТМА.
ПРОБЛЕМА
ЭКВИВАЛЕНТНОСТИ АЛГОРИТМОВ.
2
7
1.7
ПОСТРОЕНИЕ
МЕТОД
2
8
2.1
СРАВНИТЕЛЬНЫЕ ОЦЕНКИ АЛГОРИТМОВ.
ВРЕМЕННАЯ И ЕМКОСТНАЯ СЛОЖНОСТЬ. ТРУДОЕМКОСТЬ
АЛГОРИТМА,
ФУНКЦИИ
ОЦЕНКИ
ТРУДОЕМКОСТИ
АЛГОРИТМА: ЛУЧШИЙ, ХУДШИЙ И СРЕДНИЙ СЛУЧАЙ.
2
9
2.2
КЛАССИФИКАЦИЯ
ТРУДОЕМКОСТИ:
АЛГОРИТМОВ ПО ВИДУ ФУНКЦИИ
КОЛИЧЕСТВЕННО-ЗАВИСИМЫЕ
ПО
ТРУДОЕМКОСТИ
АЛГОРИТМЫ,
ПАРАМЕТРИЧЕСКИЗАВИСИМЫЕ,
КОЛИЧЕСТВЕННО-ПАРАМЕТРИЧЕСКИЕ,
ПОРЯДКОВО-ЗАВИСИМЫЕ.
2
10
2.3
ЭЛЕМЕНТАРНЫЕ
ОПЕРАЦИИ. ТРУДОЕМКОСТЬ ОСНОВНЫХ
АЛГОРИТМИЧЕСКИХ
КОНСТРУКЦИЙ:
СЛЕДОВАНИЯ,
ВЕТВЛЕНИЯ И ЦИКЛА.
2
11
2.4
МЕТОДИКИ
ПЕРЕХОДА
К
ВРЕМЕННЫМ
ОЦЕНКАМ:
ПООПЕРАЦИОННЫЙ АНАЛИЗ, МЕТОД ГИББСОНА, МЕТОД
ПРЯМОГО ОПРЕДЕЛЕНИЯ СРЕДНЕГО ВРЕМЕНИ.
2
12
2.5
ТЕОРЕТИЧЕСКИЙ
СЛОЖНОСТНЫЕ
2
ЭФФЕКТИВНЫХ
ДЕКОМПОЗИЦИИ.
АЛГОРИТМОВ.
ПРЕДЕЛ
ТРУДОЕМКОСТИ
ЗАДАЧИ.
КЛАССЫ ЗАДАЧ: КЛАСС P (ЗАДАЧИ С
ПОЛИНОМИАЛЬНОЙ
СЛОЖНОСТЬЮ),
КЛАСС
NP
(ПОЛИНОМИАЛЬНО ПРОВЕРЯЕМЫЕ ЗАДАЧИ), КЛАСС NPC
(NP – ПОЛНЫЕ ЗАДАЧИ).
ИТОГО
28/0,78
10
8. РЕКОМЕНДУЕМЫЕ ОБРАЗОВАТЕЛЬНЫЕ ТЕХНОЛОГИИ
Для проработки и закрепления лекционного материала по дисциплине «Введение в
алгоритмы» применяются:
Вид занятия
(Л, ПЗ, ЛЗ)
Семестр
4
Используемые интерактивные
образовательные технологии
Количество
часов/ЗЕ
Л
Дискуссии
4/0,11
ПЗ
Разбор конкретных ситуаций
8/0,22
ЛЗ
Компьютерные симуляции
6/0,17
ИТОГО
18/0,5
9. ПРОГРАММА САМОСТОЯТЕЛЬНОЙ РАБОТЫ СТУДЕНТА
Структура СРС
Код
формируемой
компетенции
Тема
Вид
Объем
УчебноФорма учебной
методические
отчетности работы
материалы
(часов)
Подготовка к
коллоквиуму
ПК-1,
ПК-3,
ПК-10
ПК-2
ЗАДАЧИ И АЛГОРИТМЫ
МАШИНА ТЬЮРИНГА
Подготовка к
ЛЗ
ПК-3
РЕКУРСИВНЫЕ ФУНКЦИИ
РЕШЕНИЕ ЗАДАЧ
Ответы
Основная и
дополнительная
литература
1
Отчет
2
ТЕКСТЫ
ЗАДАЧ
1
ПК-3
ПК-3,
ПК-10
ПК-3
Подготовка к
АЛГОРИТМЫ коллоквиуму
НОРМАЛЬНЫЕ
МАРКОВА
СРАВНИТЕЛЬНЫЙ АНАЛИЗ
1
РЕШЕНИЕ ЗАДАЧ
НЕРАЗРЕШИМЫЕ ПРОБЛЕМЫ
ТЕКСТЫ
ЗАДАЧ
ОСНОВНЫХ МОДЕЛЕЙ
ПРЕДСТАВЛЕНИЯ АЛГОРИТМОВ
АЛГОРИТМИЧЕСКИ
Ответы
Подготовка к
ЛЗ
11
Отчет
2
2
Основная и
дополнительная
литература,
Методические
указания к
выполнению
лабораторных
работ
Основная и
дополнительная
литература,
Методические
указания к
практическим
занятиям
Основная и
дополнительная
литература
Основная и
дополнительная
литература,
Методические
указания к
практическим
занятиям
Основная и
дополнительная
ПК-3,
ПК-10
ПОСТРОЕНИЕ ЭФФЕКТИВНЫХ
АЛГОРИТМОВ. МЕТОД
РЕШЕНИЕ ЗАДАЧ
ТЕКСТЫ
ЗАДАЧ
ДЕКОМПОЗИЦИИ
1
ПК-1,
ПК-3,
ПК-10
ПК-2,
ПК-3
ПК-3
Подготовка к
коллоквиуму
Ответы
АЛГОРИТМОВ Подготовка к
ФУНКЦИИ коллоквиуму
Ответы
ОСНОВНЫХПодготовка к
ЛЗ
Отчет
СРАВНИТЕЛЬНЫЕ ОЦЕНКИ
АЛГОРИТМОВ
1
КЛАССИФИКАЦИЯ
ПО
ВИДУ
ТРУДОЁМКОСТИ
ТРУДОЕМКОСТЬ
АЛГОРИТМИЧЕСКИХ
КОНСТРУКЦИЙ
1
2
РЕШЕНИЕ ЗАДАЧ
ПК-3
ПЕРЕХОД
К
ТЕКСТЫ
ЗАДАЧ
ВРЕМЕННЫМ
ОЦЕНКАМ
1
ПК-3,
ПК-10
СЛОЖНОСТНЫЕ КЛАССЫ ЗАДАЧ
Подготовка к
коллоквиуму
ИТОГО
12
Ответы
1
16
литература,
Методические
указания к
выполнению
лабораторных
работ
Основная и
дополнительная
литература,
Методические
указания к
практическим
занятиям
Основная и
дополнительная
литература
Основная и
дополнительная
литература
Основная и
дополнительная
литература,
Методические
указания к
выполнению
лабораторных
работ
Основная и
дополнительная
литература,
Методические
указания к
практическим
занятиям
Основная и
дополнительная
литература
График СРС
4 семестр
недели
1
2-3
4-5
6
7
8
9
10-11
12
ВК
К
К
РЗ
ЛР
РЗ
РК
РЗ
ЛР
форма
отчетности
Устная,
письменная
недели
1
форма
3
1
4-15
1
6
7
1
8
отчетност
и
Устная,
письменна
Р
З
К
Р
Р
З
П
З
я
ВК – входной контроль
РК – рубежный контроль
К – коллоквиум
РЗ – решение задач
ЛР – подготовка к лабораторной работе
ПЗ – подготовка к зачету
13
УЧЕБНАЯ КАРТА
самостоятельной работы студента____________________________________
________2___курса ____________гр. _________очной формы обучения
Дисциплина «Введение в алгоритмы»
Преподаватель___________________________________________________________
Мо
дуль
1
1
2
2
2
2
Недели
самостоятельной работы
Форма
отчетности
Фактиче
ские сроки
выполнения
1
1
Вид
Подготовка к
коллоквиуму
Подготовка к
выполнению
практических заданий
Подготовка к
лабораторной работе
Подготовка к РК
Подготовка к
выполнению
практических заданий
Подготовка к
лабораторной работе
Подготовка к
коллоквиуму
Подготовка к зачету
2, 4
Ответы на
вопросы
Тексты заданий
6, 8
7
9
Отчет по
лабораторной работе
Ведомость
10-11, 13, 17
Тексты заданий
12, 16
14-15
Отчет по
лабораторной работе
Ответы на вопросы
18
Ведомость
Подпись преподавателя:
Подпись студента:
дата
Сумма баллов по СРС, включаемая в итоговую оценку по дисциплине:
Подпись преподавателя:
дата
14
11. МАТЕРИАЛЬНО-ТЕХНИЧЕСКОЕ ОБЕСПЕЧЕНИЕ
ДИСЦИПЛИНЫ
Лекционные занятия
- комплект электронных презентаций/слайдов;
- аудитория, оснащенная презентационной техникой (проектор, экран, компьютер/
ноутбук).
Практические занятия
- презентационная техника (проектор, экран, компьютер/ноутбук);
- интерактивная доска.
Лабораторные занятия
- специализированная компьютерная аудитория, включающая 12 персональных
компьютеров с доступом в сеть Интернет.
12. УЧЕБНО-МЕТОДИЧЕСКОЕ И ИНФОРМАЦИОННОЕ ОБЕСПЕЧЕНИЕ
ДИСЦИПЛИНЫ
а) Основная литература
1. Гринченков Д.В., Потоцкий С.И. Математическая логика и теория алгоритмов для
программистов: учебное пособие. – М.: КНОРУС, 2010. – 208 с.
2. Игошин В.И. Математическая логика и теория алгоритмов. – М.: Академия, 2010.
б) Дополнительная литература
1. Глухов М.М., Шишков А.Б. Математическая логика. Дискретные функции. Теория
алгоритмов: Учебное пособие. – СПб.: Изд-во «Лань», 2012. – 416 с.
2. Игошин В.И. Задачи и упражнения по математической логике и теории алгоритмов. – М.:
Академия, 2007.
3. АЛЯБЬЕВА В.Г., ПАСТУХОВА Г.В., ТЕОРИЯ АЛГОРИТМОВ. УЧЕБНОЕ ПОСОБИЕ. ПЕРМЬ: ПГПУ,
2011.
в) Программное обеспечение и Интернет-ресурсы:
МАШИНА ТЬЮРИНГА 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.
http://amd.stu.neva.ru/education/prog71.htm
www.twirpx.com/files/special/protection/
rrc.dgu.ru/res/intsys.msu.ru/staff/vnosov/theoralg.htm
www.proklondike.com/contentview.php?content
HTTP://LPCS.MATH.MSU.SU/~PENTUS/PROBLEMS.HTM
15