Алгоритмы и анализ их сложности

ТРУДОЕМКОСТЬ ДИСЦИПЛИНЫ
Общая трудоемкость дисциплины составляет 6 ЗЕТ (216 час.).

ЦЕЛИ И ЗАДАЧИ ДИСЦИПЛИНЫ
Целью дисциплины «Алгоритмы и анализ их сложности» является изучение основных методов разработки алгоритмов обработки данных и анализ этих алгоритмов, взаимосвязь алгоритмов и структур данных. Основной задачей изучения дисциплины является приобретение студентами прочных знаний и практических навыков в области, определяемой основной целью курса.

МЕСТО ДИСЦИПЛИНЫ В СТРУКТУРЕ ООП
Дисциплина «Алгоритмы и анализ их сложности» относится к вариативной части профессионального цикла ООП. Успешное овладение дисциплиной предполагает предварительные знания математического анализа, вычислительных методов, дискретной математики в объеме, предусмотренном бакалавриатом «Прикладная математика и информатика», а также навыки программирования на языках высокого уровня.

ТРЕБОВАНИЯ К УРОВНЮ ОСВОЕНИЯ ДИСЦИПЛИНЫ
Процесс изучения дисциплины «Алгоритмы и анализ их сложности» направлен на формирование следующих общекультурных (ОК) и профессиональных компетенций (ПК):

  1. способностью использовать углубленные теоретические и практические знания в области прикладной математики и информатики (ОК-3);
  2. способность самостоятельно приобретать с помощью информационных технологий и использовать в практической деятельности новые знания и умения, в том числе, в новых областях знаний, непосредственно не связанных со сферой деятельности, расширять и углублять свое научное мировоззрение (ОК-4);
  3. способностью порождать новые идеи и демонстрировать навыки самостоятельной научно-исследовательской работы и работы в научном коллективе (ОК-5);
  4. способностью проводить научные исследования и получать новые научные и прикладные результаты (ПК-1);
  5. способностью разрабатывать концептуальные и теоретические модели решаемых научных проблем и задач (ПК-2);
  6. способностью углубленного анализа проблем, постановки и обоснования задач научной и проектно-технологической деятельности (ПК-3).
В результате изучения дисциплины студент должен:

Знать:
  1. основные методы разработки машинных алгоритмов;
  2. методы оценки вычислительных алгоритмов;
  3. основные алгоритмы решения классических задач информатики.
Уметь:
  1. разрабатывать алгоритмы, используя изложенные в курсе общие схемы, методы и приемы построения алгоритмов;
  2. выбирать подходящие структуры данных для представления информационных структур;
  3. определять вычислительную сложность алгоритмов.
Владеть: методами разработки и анализа машинных алгоритмов решения задач.

СОДЕРЖАНИЕ ДИСЦИПЛИНЫ. ОСНОВНЫЕ РАЗДЕЛЫ
Алгоритмы и их сложность. NP-полные и труднорешаемые задачи. Методы разработки алгоритмов. Поиск подстрок. Алгоритмы на графах. Кратчайшие пути в графе. Задачи о потоках. Двудольные графы. Алгоритмы с возвратом.

ВИДЫ УЧЕБНОЙ РАБОТЫ
Лекции, практические занятия, лабораторные работы.

ФОРМА АТТЕСТАЦИИ ПО ДИСЦИПЛИНЕ
Изучение дисциплины заканчивается экзаменом.

Методические материалы:

  1. Горитов А.Н. Алгоритмы и анализ их сложности: методические указания к выполнению лабораторных работ студентов всех форм обучения для направления 01.04.02 "Прикладная математика и информатика" / А.Н. Горитов. – Томск: ТУСУР, 2015. – 10 с.
  2. Горитов А.Н. Алгоритмы и анализ их сложности: методические указания к практическим занятиям студентов всех форм обучения по направлению 01.04.02 "Прикладная математика и информатика" / А.Н. Горитов. – Томск: ТУСУР, 2015. – 8 с.
  3. Горитов А.Н. Алгоритмы и анализ их сложности: методические указания по самостоятельной и индивидуальной работе студентов всех форм обучения по направлению 01.04.02 "Прикладная математика и информатика" / А.Н. Горитов. – Томск: ТУСУР, 2015. – 8 с.