Одним из главных принципов уникальной «системы Физтеха», заложенной в основу образования в МФТИ, является тщательный отбор одаренных и склонных к творческой работе представителей молодежи. Абитуриентами Физтеха становятся самые талантливые и высокообразованные выпускники школ всей России и десятков стран мира.

Студенческая жизнь в МФТИ насыщенна и разнообразна. Студенты активно совмещают учебную деятельность с занятиями спортом, участием в культурно-массовых мероприятиях, а также их организации. Администрация института всячески поддерживает инициативу и заботится о благополучии студентов. Так, ведется непрерывная работа по расширению студенческого городка и улучшению быта студентов.

Адрес e-mail:

Аннотация примерной программы дисциплины «Алгоритмы и структуры данных»

Цель дисциплины:


В данном курсе студенты закрепляют навыки программирования на С++, изучая и реализуя сложные современные алгоритмы. В их число входят алгоритмы на графах (построение остовного дерева, топологическая сортировка, поиск кратчайших путей) и связанные с ними структуры данных, такие как система непересекающихся множеств, биномиальная и фибоначчиева кучи. Другой блок задач связан с работой со строками и построением индексов текста — алгоритмы Рабина-Карпа, Кнута-Морриса-Пратта, Укконена для построения суффиксного дерева, суффиксного массива.


Учебные задачи дисциплины:

  • получение практики разработки сложных программ;
  • получение практики командной разработки;
  • изучение основных алгоритмов для работы с графами и текстами.

 В результате освоения дисциплины «Алгоритмы и структуры данных» обучающийся должен:


знать:

  • что такое граф, какие виды графов бывают;
  • алгоритмы обхода графа;
  • что такое минимальное остовное дерево;
  • алгоритмы Прима и Крускала построения минимального остовного дерева;
  • алгоритм топологической сортировки;
  • алгоритмы Флойда и Дейкстры поиска кратчайших путей на графе;
  • алгоритмы построения суффиксного дерева;
  • алгоритмы построения суффиксного массива;
  • алгоритмы Рабина-Карпа и Кнута-Морриса-Пратта для поиска подстрок в тексте;
  • алгоритм построения дерева отрезков.

уметь:

  • реализовывать перечисленные выше алгоритмы и структуры данных;
  • сводить задачи к использованию перечисленных алгоритмов;
  • находить наибольшую подстроку двух текстов;
  • находить подстроки в очень большом тексте;
  • тестировать написанные классы (элементы юнит-тестирования);
  • строить индекс текста;
  • применять суффиксные деревья и массивы для решения практических задач;
  • применять динамическое программирование и дерево отрезков для нахождения минимума на отрезке;
  • сводить задачу нахождения минимума на отрезке к задаче наименьшего общего предка, и наоборот;
  • решать задачу выдачи подсказок при поиске (suggest);
  • использовать разные виды куч(пирамид) для очереди с приоритетами;
  • использовать отложенные вычисления в декартовом дереве.

владеть:

  • средствами анализа производительности языка C++;
  • начальными навыками тестирования программ;
  • средствами автоматического тестирования модулей.

Если вы заметили в тексте ошибку, выделите её и нажмите Ctrl+Enter.

© 2001-2016 Московский физико-технический институт
(государственный университет)

Техподдержка сайта

МФТИ в социальных сетях

soc-vk soc-fb soc-tw soc-li soc-li
Яндекс.Метрика