Введение в программирование и алгоритмы

Цели и задачи дисциплины
Целями дисциплины являются первичное ознакомление студентов с основными принципами проектирования и анализа алгоритмов и структур данных, обучение навыкам обоснования корректности алгоритмов, их практической реализации, теоретической и экспериментальной оценки их временной сложности. Задачи дисциплины - научить формулировать задачи в терминах изученных теорий, выбирать подходящий алгоритм для поставленной задачи; - научить разрабатывать комбинации алгоритмов для решения поставленных задач, оценивать сложности алгоритмов, выбирать подходящие структуры данных для поставленных задач, реализовывать алгоритмы на языке программирования C++.
Краткое содержание дисциплины
В начале вводятся общие математические обозначения, позволяющие работать с асимптотиками и оценивать сложность работы алгоритмов. Дисциплина посвящена изучению структур данных, необходимых для разнообразных более сложных алгоритмов. Простейшие структуры стек, очередь, вектор анализируются на предмет эффективности и времени выполнения. Вводятся кучи (двоичная, биномиальная и фибоначчиева), описываются границы их применимости. Изучаются деревья поиска (splay, AVL, декартово, B-дерево) вместе с подробными доказательствами корректности и асимптотики, а также с описанием прикладных преимуществ каждой структуры. Рассматриваются наиболее универсальные техники обработки запросов: хэш-таблицы, деревья отрезков, деревья Фенвика (в том числе многомерные), разреженные таблицы. В рамках рассматриваемых тем оттачиваются различные техники оценки временной сложности алгоритмов: метод потенциалов и метод амортизационного анализа. Дисциплина в целом рассчитана на изучение базовых структур, реализация которых требуется во множестве более продвинутых алгоритмов. Дисциплина включает подробное освещение теоретической стороны алгоритмов, разбор и тренировка решений практических задач, а также предполагает самостоятельное изучение студентами материала предмета через решение домашних теоретических и практических задач.
Компетенции обучающегося, формируемые в результате освоения дисциплины
Выпускник должен обладать:
  • ПК-3 Способен ориентироваться в современных алгоритмах компьютерной математики; обладать способностями к эффективному применению и реализации математически сложных алгоритмов в современных программных комплексах
Вы нашли ошибку в тексте:
Просто нажмите кнопку «Сообщить об ошибке» — этого достаточно. Также вы можете добавить комментарий.