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

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
м (Ctrlalt переименовал страницу Дисциплина «Алгоритмы и структуры данных» ИВТ УлГТУ — 2015 в [[Дисциплина «Алгоритмы и структуры данных» ИВТ …)
Строка 2: Строка 2:
 
== План лекций ==
 
== План лекций ==
  
* Сложность алгоритмов. Сортировки (02.09.2015)
+
[http://docs.google.com/document/d/1lvI-7gs7uyxnciw-NKvTITNgLA6qt83l1BNZYzW7d3o/edit?usp=sharing Конспект лекций, составляемый студентами]
 +
 
 +
* Сложность алгоритмов. Сортировки (05.09.2016)
 
: Правила асимптотического анализа алгоритмов. Асимптотические обозначения. Основные классы сложности.
 
: Правила асимптотического анализа алгоритмов. Асимптотические обозначения. Основные классы сложности.
 
: Сортировки: выбором, вставками, слиянием, быстрая. Ω-оценка для сортировок сравнением.
 
: Сортировки: выбором, вставками, слиянием, быстрая. Ω-оценка для сортировок сравнением.
 
: Устойчивость сортировок. Сортировки за линейное время: подсчётом, поразрядная.
 
: Устойчивость сортировок. Сортировки за линейное время: подсчётом, поразрядная.
  
* Бинарный поиск (07.09.2015)
+
* Бинарный поиск
 
: Бинарный поиск элемента в отсортированном массиве. Поиск первого и последнего вхождения.
 
: Бинарный поиск элемента в отсортированном массиве. Поиск первого и последнего вхождения.
 
: Бинарный поиск по ответу.
 
: Бинарный поиск по ответу.
Строка 13: Строка 15:
 
: Тернарный поиск.
 
: Тернарный поиск.
  
* Динамическое программирование. Жадные алгоритмы (16.09.2015)
+
* Динамическое программирование. Жадные алгоритмы
 
: Решение задач комбинаторной оптимизации: полный перебор и методы его сокращения.
 
: Решение задач комбинаторной оптимизации: полный перебор и методы его сокращения.
 
: Жадные алгоритмы. Принцип жадного выбора. Задачи: непрерывный рюкзак, выбор заявок, размен монет, коды Хаффмана.
 
: Жадные алгоритмы. Принцип жадного выбора. Задачи: непрерывный рюкзак, выбор заявок, размен монет, коды Хаффмана.
Строка 34: Строка 36:
 
* Балансирующиеся деревья
 
* Балансирующиеся деревья
  
* Графы. Поиск в глубину (21.10.2015)
+
* Графы. Поиск в глубину
 
: Представление графа. Матрица смежности, списки смежности, список рёбер.
 
: Представление графа. Матрица смежности, списки смежности, список рёбер.
 
: [[Поиск в глубину]].
 
: [[Поиск в глубину]].
Строка 43: Строка 45:
 
: [[Мосты. Компоненты рёберной двусвязности|Поиск мостов]].
 
: [[Мосты. Компоненты рёберной двусвязности|Поиск мостов]].
  
* Кратчайшие пути (11.11.2015)
+
* Кратчайшие пути
 
: Кратчайшие пути в невзвешенном графе. [[Поиск в ширину]].
 
: Кратчайшие пути в невзвешенном графе. [[Поиск в ширину]].
 
: Кратчайшие пути в графе с неотрицательными весами. [[Алгоритм Дейкстры]] за O(V<sup>2</sup>) и за O(ElogV).
 
: Кратчайшие пути в графе с неотрицательными весами. [[Алгоритм Дейкстры]] за O(V<sup>2</sup>) и за O(ElogV).
Строка 56: Строка 58:
  
 
* Резерв
 
* Резерв
 
+
<!--
 
== Таблицы успеваемости групп ==
 
== Таблицы успеваемости групп ==
  
Строка 98: Строка 100:
 
# Минимальное остовное дерево. Алгоритм Прима.
 
# Минимальное остовное дерево. Алгоритм Прима.
 
# Минимальное остовное дерево. Алгоритм Краскала. Система непересекающихся множеств.
 
# Минимальное остовное дерево. Алгоритм Краскала. Система непересекающихся множеств.
 +
-->
  
 
== Решение проблем с локалью при вводе/выводе вещественных чисел ==
 
== Решение проблем с локалью при вводе/выводе вещественных чисел ==

Версия 19:48, 5 сентября 2016

План лекций

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

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

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

На сервере по умолчанию используется русская локаль, что может порождать 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);