Дисциплина «Алгоритмы и структуры данных» ИВТ УлГТУ: различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Строка 9: Строка 9:
 
: Устойчивость сортировок. Сортировки за линейное время: подсчётом, поразрядная.
 
: Устойчивость сортировок. Сортировки за линейное время: подсчётом, поразрядная.
  
* Бинарный поиск
+
* Бинарный поиск (19.09.2016)
 
: Бинарный поиск элемента в отсортированном массиве. Поиск первого и последнего вхождения.
 
: Бинарный поиск элемента в отсортированном массиве. Поиск первого и последнего вхождения.
 
: Бинарный поиск по ответу.
 
: Бинарный поиск по ответу.
Строка 29: Строка 29:
  
 
* Структуры данных. Расширяющийся массив. Список
 
* Структуры данных. Расширяющийся массив. Список
 +
:  Смежные и связные структуры данных. Работа с классами и динамической памятью.
 +
:  Понятие амортизированной сложности. Стратегии реализации динамического массива.
 +
:  Реализации списков.
 +
:  Сравнение быстродействия основных операций для массивов и списков.
  
 
* Стек. Очередь. Очередь с приоритетами
 
* Стек. Очередь. Очередь с приоритетами
 +
:  Стек LIFO: реализация на массиве и связном списке. Классические приложения стека.
 +
:  Очередь FIFO: реализация на циклическом массиве и связном списке. Классические приложения очереди. Дек.
 +
:  Интерфейс очереди с приоритетами. Двоичная куча.
  
 
* Деревья. Хеш-таблицы
 
* Деревья. Хеш-таблицы
 +
:  Интерфейс АТД "Множество" и "Словарь".
 +
:  Двоичные деревья поиска. Поиск, добавление и удаление элементов: рекурсивная и нерекурсивная реализация.
 +
:  Принципы функционирования хеш-таблиц. Разрешение коллизий: метод цепочек, открытая адресация.
  
 
* Балансирующиеся деревья
 
* Балансирующиеся деревья
 +
:  Недостатки наивной реализации двоичного дерева поиска.
 +
:  Обзор балансирующихся деревьев: 2-3-, красно-чёрные и AA-деревья
 +
:  Декартово дерево. Реализация интерфейса АТД "Множество" и "Словарь".
 +
:  Множественные операции в декартовом дереве.
  
 
* Графы. Поиск в глубину
 
* Графы. Поиск в глубину
Строка 53: Строка 67:
 
: Проверка графа на наличие отрицательного цикла.
 
: Проверка графа на наличие отрицательного цикла.
  
* Минимальный остов. Система непересекающихся множеств
+
* Кратчайшие пути
 +
:  Кратчайшие пути в невзвешенном графе. Поиск в ширину.
 +
:  Кратчайшие пути в графе с неотрицательными весами. Алгоритм Дейкстры за O(V^2) и за O(ElogV).
 +
:  Кратчайшие пути в ациклических орграфах.
 +
:  Кратчайшие пути в графе с отрицательными весами. Алгоритм Форда-Беллмана.
 +
:  Кратчайшие пути между всеми парами вершин. Алгоритм Флойда.
 +
:  Проверка графа на наличие отрицательного цикла.
  
* Другие задачи теории графов
+
* Минимальный остов. Система непересекающихся множеств
 +
:  Алгоритм Прима.
 +
:  Алгоритм Краскала.
 +
:  Структура данных "Система непересекающихся множеств" и её эвристики.
  
 
* Резерв
 
* Резерв
<!--
+
 
 
== Таблицы успеваемости групп ==
 
== Таблицы успеваемости групп ==
  
* [https://docs.google.com/spreadsheets/d/1OhKsZuAIYtJUA_9fsmaxh0KF0MnLJe9Li7jtxSouex8/edit?usp=sharing Успеваемость группы АП]
+
* [http://docs.google.com/spreadsheets/d/1ldfBn0aZdMcTqQEA9owTLMgZdG4f067rds5T11OOF50/edit?usp=sharing Успеваемость группы АП]
* [https://docs.google.com/spreadsheets/d/1deCDFIlq-rIsPzdqUHJ08pXqRfD4gcVCYgNhEi_qEMI/edit?usp=sharing Успеваемость группы ВМ]
+
* [http://docs.google.com/spreadsheets/d/1sZLP0ffesarlhH_48v-9GQWBhMb0LyhceDs-T0SS4u0/edit?usp=sharing Успеваемость группы ВМ]
  
 
Таблицы обновляются после практических занятий.
 
Таблицы обновляются после практических занятий.
  
 
Текущий сервер дорешивания &mdash; [http://vtcloud9.ulstu.ru/ru/contestlist vtcloud9]
 
Текущий сервер дорешивания &mdash; [http://vtcloud9.ulstu.ru/ru/contestlist vtcloud9]
 
+
<!--
 
== <span style="color: red;">Задания на курсовые работы</span> ==
 
== <span style="color: red;">Задания на курсовые работы</span> ==
  

Версия 00:45, 22 сентября 2016

План лекций

Конспект лекций, составляемый студентами

  • Сложность алгоритмов. Сортировки (05.09.2016)
Правила асимптотического анализа алгоритмов. Асимптотические обозначения. Основные классы сложности.
Сортировки: выбором, вставками, слиянием, быстрая. Ω-оценка для сортировок сравнением.
Устойчивость сортировок. Сортировки за линейное время: подсчётом, поразрядная.
  • Бинарный поиск (19.09.2016)
Бинарный поиск элемента в отсортированном массиве. Поиск первого и последнего вхождения.
Бинарный поиск по ответу.
Вещественный бинарный поиск.
Тернарный поиск.
  • Динамическое программирование. Жадные алгоритмы
Решение задач комбинаторной оптимизации: полный перебор и методы его сокращения.
Жадные алгоритмы. Принцип жадного выбора. Задачи: непрерывный рюкзак, выбор заявок, размен монет, коды Хаффмана.
Динамическое программирование. Критерии применимости ДП. Ленивая рекурсия и просмотр вперёд. Восстановление решения.
Виды одномерной и двумерной динамики.
Видео: План решения задачи методом динамического программирования
Видео: Одномерная динамика. Количество путей в полосе
Видео: Одномерная динамика. Оптимальный путь в полосе
Видео: Одномерная динамика с привязкой. Наибольшая возрастающая подпоследовательность
Видео: Двумерная динамика. Задача о рюкзаке
Видео: Двумерная динамика. Наибольшая общая подпоследовательность
Видео: Двумерная динамика: Редакционное расстояние
  • Структуры данных. Расширяющийся массив. Список
Смежные и связные структуры данных. Работа с классами и динамической памятью.
Понятие амортизированной сложности. Стратегии реализации динамического массива.
Реализации списков.
Сравнение быстродействия основных операций для массивов и списков.
  • Стек. Очередь. Очередь с приоритетами
Стек LIFO: реализация на массиве и связном списке. Классические приложения стека.
Очередь FIFO: реализация на циклическом массиве и связном списке. Классические приложения очереди. Дек.
Интерфейс очереди с приоритетами. Двоичная куча.
  • Деревья. Хеш-таблицы
Интерфейс АТД "Множество" и "Словарь".
Двоичные деревья поиска. Поиск, добавление и удаление элементов: рекурсивная и нерекурсивная реализация.
Принципы функционирования хеш-таблиц. Разрешение коллизий: метод цепочек, открытая адресация.
  • Балансирующиеся деревья
Недостатки наивной реализации двоичного дерева поиска.
Обзор балансирующихся деревьев: 2-3-, красно-чёрные и AA-деревья
Декартово дерево. Реализация интерфейса АТД "Множество" и "Словарь".
Множественные операции в декартовом дереве.
  • Графы. Поиск в глубину
Представление графа. Матрица смежности, списки смежности, список рёбер.
Поиск в глубину.
Компоненты связности.
Поиск циклов.
Топологическая сортировка.
Компоненты сильной связности.
Поиск мостов.
  • Кратчайшие пути
Кратчайшие пути в невзвешенном графе. Поиск в ширину.
Кратчайшие пути в графе с неотрицательными весами. Алгоритм Дейкстры за O(V2) и за O(ElogV).
Кратчайшие пути в ациклических орграфах.
Кратчайшие пути в графе с отрицательными весами. Алгоритм Форда-Беллмана.
Кратчайшие пути между всеми парами вершин. Алгоритм Флойда.
Проверка графа на наличие отрицательного цикла.
  • Кратчайшие пути
Кратчайшие пути в невзвешенном графе. Поиск в ширину.
Кратчайшие пути в графе с неотрицательными весами. Алгоритм Дейкстры за O(V^2) и за O(ElogV).
Кратчайшие пути в ациклических орграфах.
Кратчайшие пути в графе с отрицательными весами. Алгоритм Форда-Беллмана.
Кратчайшие пути между всеми парами вершин. Алгоритм Флойда.
Проверка графа на наличие отрицательного цикла.
  • Минимальный остов. Система непересекающихся множеств
Алгоритм Прима.
Алгоритм Краскала.
Структура данных "Система непересекающихся множеств" и её эвристики.
  • Резерв

Таблицы успеваемости групп

Таблицы обновляются после практических занятий.

Текущий сервер дорешивания — vtcloud9

Решение проблем с локалью при вводе/выводе вещественных чисел

На сервере по умолчанию используется русская локаль, что может порождать Runtime Error при чтении и Wrong Answer при выводе вещественных чисел на C# и Java (так как в качестве разделителя вместо точки ожидается запятая).

Для восстановления локали на C# следует использовать следующий код:

/* добавить в начало файла: */
using System.Threading;
using System.Globalization;

/* добавить в основной функции: */
Thread.CurrentThread.CurrentCulture = CultureInfo.InvariantCulture;

Для восстановления локали на Java следует использовать следующий код:

/* пример ввода: */
Scanner in = new Scanner(System.in);
in.useLocale(new Locale("US"));
double x = in.nextDouble();

/* пример вывода: */
System.out.printf(Locale.US, "%.4f", x);