Основы Computer Science

(алгоритмы и деревья решений)

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

    1. Время работы алгоритма, O-сложность.

    2. Анализ роста функций:

  1. логарифм

  2. полином

  3. экспонента

  1. Варианты поиска чисел Фибоначчи:

  1. рекурсивный экспоненциальный алгоритм

  2. полиномиальный алгоритм

  1. Рекуррентные алгоритмы.

    1. Метод "разделяй и властвуй".

    2. Произведение -битовых чисел:

      1. классический рекурсивный алгоритм

      2. модифицированный рекурсивный алгоритм.

    3. Основная теорема о рекуррентых соотношениях.

    4. Алгоритмы двоичного поиска

  2. Алгоритмы сортировки.

    1. Сортировка слиянием: с рекурсией и без.

    2. Сортировка с помощью кучи.

    3. Нижняя оценка для сортировки.

  3. Быстрая сортировка:

    1. Вычисление среднего времени работы

    2. Вычисление глубины рекурсии

    3. Элиминация хвостовой рекурсии

    4. Порядковые статистики

  4. Элементарные структуры данных.

    1. Абстрактные типы данных, интерфейс и реализация.

    2. Массивы переменного размера:

  1. аддитивная схемы реаллокации.

  2. мультипликативная схемы реаллокации.

  1. Анализ учётных стоимостей операций:

  1. функция потенциала

  2. истинные стоимости

  3. учётные стоимости.

  1. Стек, очередь, дек.

    1. Реализация на основе массива переменного размера

    2. Реализация на основе связанного списка.

    3. Моделирование очереди с помощью двух стеков.

  2. Корневое дерево:

    1. бинарное дерево

    2. дерево с произвольным ветвлением

    3. представление "левый ребёнок - правый сосед"

  3. Динамическое программирование.

    1. Предварительные сведения: ациклические ориентированные графы.

  1. Общие принципы динамического программирования, часто используемые подзадачи.

  2. Кратчайшие пути в ациклических ориентированных графах.

  1. Наибольшая возрастающая подпоследовательность:

  1. подзадачи, порядок на подзадачах

  2. граф подзадач

  3. сравнение с рекурсивным алгоритмом;

  4. нахождение не только длины, но и самой подпоследовательности.

  1. Стоимость редактирования:

  1. граф на подзадачах

  2. нахождение кратчайшего пути в данном графе.

  1. Динамическое программирование 2.

    1. Задача о рюкзаке:

  1. рюкзак с повторениями и без

  2. ленивые вычисления.

  1. Перемножение последовательности матриц:

  1. представление порядка перемножения в виде дерева

  2. оценка на количество порядков.

    1. Независимые множества в деревьях.

    2. О времени и памяти алгоритмов, основанных на методе динамического программирования

  1. Двоичные деревья поиска

    1. Внутренние и внешние узлы

    2. Глубина узла

    3. Обход и симметричный обход дерева

    4. Добавление и удаление узлов

  2. Дерево поиска:

    1. поиск, вставка, удаление, поиск следующего и предыдущего элемента за время, пропорциональное высоте.

    2. АВЛ-дерево (или какое-нибудь другое сбалансированное дерево): верхняя оценка на высоту, малое и большое вращение.

  3. Декартовы деревья.

    1. Декартовы деревья, операции split и merge, реализация стандартных операций деревьев поиска через split и merge.

    2. Верхняя оценка на среднюю стоимость операций.

  4. Декомпозиция графов.

    1. Графы и способы их представления, способы использования графов.

    2. Поиск в глубину в неориентированных графах

    3. Выделение компонент связности

  5. Топология графов

    1. Поиск в глубину в ориентированных графах:

    2. Ориентированные ациклические графы

    3. Топологическая сортировка вершин

    4. Наличие стока и истока в ациклическом графе

    5. Выделение компонент сильной связности.

  6. Пути в графах.

    1. Расстояния в графе.

    2. Поиск в ширину: обход, дерево кратчайших путей, сравнение с поиском в глубину.

  7. Алгоритм Дейкстры:

    1. адаптация поиска в ширину введением дополнительных вершин;

    2. установка будильников;

    3. алгоритм Дейкстры;

    4. альтернативный взгляд на алгоритм:

  1. последовательное расширение множества вершин, до которых расстояние уже посчитано;

  2. время работы алгоритма при различных реализациях очереди с приоритетами

 

КурсПродолжительностьСтоимостьСтоимость с рассрочкой
JD1.1 Основы Computer Science64 у. ч.----

РАСПИСАНИЕ

Нет групп