СИЛЛАБУС
______________________________________________________________
(шифр и наименование модуля)
по дисциплине ___ Теория алгоритмов
(код и полное наименование дисциплины по рабочему учебному плану)
для студентов специальности (ей) _ 050704 -
«Вычислительная техника и программное обеспечение»
(шифр и наименование специальности/специализации)
Астана
Силлабус
по дисциплине «Теория алгоритмов»
для студентов специальности 050704– «Вычислительная техника и программное обеспечение»
Евразийский национальный университет им. Л.Н.Гумилева
1)Бекенов Махсут Искандерович, доцент кафедры Вычислительной техники ЕНУ им. Л.Н.Гумилева.
Контактный телефон: 37-74-23 вн. (3021);
E-mail: bekenov@enu.kz
Научные интересы: Компьютерная логика, Теория алгоритмов, Теория моделей.
Дополнительная информация:
2) «Теория алгоритмов»
Код: ТА, Количество кредитов – 3.
3) Время и место проведения: 2 семестр; согласно расписанию.
4) Пререквизиты учебной дисциплины: Дискретная математика, Алгебра и геометрия
Постреквизиты: Компьютерная логика, С истемы искусственного интеллекта, Высокоскоростные вычисления и суперкомпьютеры.
5) Характеристика дисциплины
5.1 Назначение учебной дисциплины. Учебная дисциплина как базовый курс должен обеспечить целенаправленную подготовку будущего специалиста, его умение формулировать и исследовать на должном уровне общие теоретические проблемы изучаемой специальности, умение развить и реализовать свои знания в области инженерной практики.
5.2 Цель: Основная цель учебной дисциплины: формирование знаний у будущих специалистов по теории алгоритмов. А также ознакомить студентов с современными проблемами и перспективами развития формальных алгоритмических систем, исследования алгоритмической неразрешимости ряда задач, получения явных функций трудоемкости в целях сравнительного анализа сложности алгоритмов, разработки критериев сравнительной оценки качества алгоритмов.
5.3 Задачи курса. Основными задачами данной дисциплины являются:
- научить теоретическим и практическим основам теории алгоритмов как области знаний и человеческой деятельности;
- освоить технические и прикладные методы и средства теории алгоритмов;
- изучить основные направления исследований в теории алгоритмов.
5.4 Содержание учебной дисциплины
Курс посвящён формализации понятия «алгоритм». Обсуждаются три способа формального описания алгоритма –с помощью нормальных алгоритмов Маркова и через машины Тьюринга и рекурсивных функций. Приводятся меры сложности алгоритмов, определяются легко и трудноразрешимые задачи, классы задач P и NP, алгоритмически неразрешимые проблемы.
5.5 План изучения дисциплины
| № недели | Название темы | Формы обучения, кол-во часов | Задания для СРС |
| 1 | 2 | 3 | |
| 1. | Введение в теорию алгоритмов. Исторический обзор. Цели и задачи. Практическое применение результатов теории алгоритмов. | Лекция (2 часа), СРС (2 часа) | Практическое применение результатов теории алгоритмов. |
| 2. | Формализация понятия алгоритма. Понятие алгоритма и его основные черты. Интуитивное понятие алгоритма. Происхождение слова алгоритм. Понятия, связанные с понятием алгоритма. Варианты протекания алгоритмического процесса. Основные черты алгоритма. Абстракция потенциальной осуществимости. | Лекция (2 часа), СРС (2 часа) | Понятия, связанные с понятием алгоритма. |
| 3. | Необходимость уточнения понятия алгоритм Десятая проблема Гильберта Направления формализации понятия алгоритм | Лекция (2 часа), СРС (2 часа) | Десятая проблема Гильберта. |
| 4. | Машина Тьюринга Основная гипотеза теории алгоритмов.Тезис Тьюринга. Универсальная машина Тьюринга | Лекция (2 часа), СРС (2 часа) | Примеры доказательства функций вычислимых с помощью машины Тьюринга. |
| 5. | Нормальный алгорифм Маркова Тезис Маркова. Равносильность тезисов. | Лекция (2 часа), СРС (2 часа) | Примеры доказательства функций вычислимых с помощью алгоритма Маркова. |
| 6. | Рекурсивные функции.Простейшие функции Операция суперпозиции Интуитивное понятие вычислимой функции. Тезис Черча. | Лекция (2 часа), СРС (2 часа) | Примеры доказательства примитивной рекурсивности функции |
| 7. | Меpы сложности алгоpитмов. Оценка алгоритма. | Лекция (2 часа), СРС (2 часа) | Оценка сложности алгоритма. |
| 8. | Алгоритмически неразрешимые проблемы. | Лекция (1 часа), СРС (2 часа) | Алгоритмически неразрешимые проблемы. |
| Всего | Лекций 15 часов, СРС 30 часов |
Лабораторные занятия, их наименование и объем в часах (30 часов)
| № работы | Наименование работ | Кол-во часов | Срок сдачи |
| 1. | Лабораторно-практическая работа №1. «Блок схемы программ известных алгоритмов» | 1-2 недели семестра | |
| 2. | Лабораторно-практическая работа №2. «Программы известных алгоритмов» | 3-4 недели семестра | |
| 3. | Лабораторно-практическая работа №3. «Программы машины Тьюринга вычислимости определенной функции» | 5-6 недели семестра | |
| 4. | Лабораторно-практическая работа №4 «Программы алгоритма Маркова вычислимости определенной функции» | 7-8 недели семестра | |
| 5. | Лабораторно-практическая работа №5 «Примитивная рекурсивность некоторых функций» | 9-10 недели семестра | |
| 6. | Лабораторно-практическая работа №6 «Оценка сложности алгоритмов» | 11-12 недели семестра | |
| 7. | Лабораторно-практическая работа №7. «Оценка сложности алгоритмов» | 13-14 недели семестра | |
| 8. | Лабораторно-практическая работа №8 «Разрешимость некоторых классов задач» | 15недели семестра | |
| Всего: |
