Лабораторные занятия, их наименование и объем в часах (30 часов)

СИЛЛАБУС

______________________________________________________________

(шифр и наименование модуля)

по дисциплине ___Теория алгоритмов

(код и полное наименование дисциплины по рабочему учебному плану)

для студентов специальности (ей) _ 050704 -

«Вычислительная техника и программное обеспечение»

(шифр и наименование специальности/специализации)

Астана

Силлабус

по дисциплине «Теория алгоритмов»

для студентов специальности 050704– «Вычислительная техника и программное обеспечение»

Евразийский национальный университет им. Л.Н.Гумилева

1)Бекенов Махсут Искандерович, доцент кафедры Вычислительной техники ЕНУ им. Л.Н.Гумилева.

Контактный телефон: 37-74-23 вн. (3021);

E-mail: [email protected]

Научные интересы:Компьютерная логика, Теория алгоритмов, Теория моделей.

Дополнительная информация:

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 часов)

Наши рекомендации