Дисциплина «Алгоритмы и структуры данных» ИВТ УлГТУ: различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) Нет описания правки |
Ctrlalt (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
== [http://vk.com/op_ulstu?w=wall-87545945_125%2Fall Курс по алгоритмам от университета ИТМО] == | |||
== План лекций == | == План лекций == | ||
| Строка 80: | Строка 82: | ||
Текущий сервер дорешивания — [http://vtcloud9.ulstu.ru/ru/contestlist vtcloud9] | Текущий сервер дорешивания — [http://vtcloud9.ulstu.ru/ru/contestlist vtcloud9] | ||
== Сайты, помогающие улучшить навык программирования == | |||
* [http://acmp.ru/asp/do/index.asp?main=course&id_course=1 Цикл задач «Язык программирования C++» на acmp.ru] (множество простых задач, решение каждой из которых можно уточнить у Владимира Александровича) | |||
* [http://stepik.org/course/%D0%92%D0%B2%D0%B5%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5-%D0%B2-%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5-(C%2B%2B)-363 Открытый курс «Введение в программирование» от Яндекса и Высшей школы экономики на stepik.org] (видеолекции и задачи по разным темам, от простых до сложных) | |||
<!-- | <!-- | ||
== <span style="color: red;">Задания на курсовые работы</span> == | == <span style="color: red;">Задания на курсовые работы</span> == | ||
Версия от 13:54, 25 сентября 2016
Курс по алгоритмам от университета ИТМО
План лекций
Конспект лекций, составляемый студентами
- Сложность алгоритмов. Сортировки (05.09.2016)
- Правила асимптотического анализа алгоритмов. Асимптотические обозначения. Основные классы сложности.
- Сортировки: выбором, вставками, слиянием, быстрая. Ω-оценка для сортировок сравнением.
- Устойчивость сортировок. Сортировки за линейное время: подсчётом, поразрядная.
- Бинарный поиск (19.09.2016)
- Бинарный поиск элемента в отсортированном массиве. Поиск первого и последнего вхождения.
- Бинарный поиск по ответу.
- Вещественный бинарный поиск.
- Тернарный поиск.
- Динамическое программирование. Жадные алгоритмы
- Решение задач комбинаторной оптимизации: полный перебор и методы его сокращения.
- Жадные алгоритмы. Принцип жадного выбора. Задачи: непрерывный рюкзак, выбор заявок, размен монет, коды Хаффмана.
- Динамическое программирование. Критерии применимости ДП. Ленивая рекурсия и просмотр вперёд. Восстановление решения.
- Виды одномерной и двумерной динамики.
- Видео: План решения задачи методом динамического программирования
- Видео: Одномерная динамика. Количество путей в полосе
- Видео: Одномерная динамика. Оптимальный путь в полосе
- Видео: Одномерная динамика с привязкой. Наибольшая возрастающая подпоследовательность
- Видео: Двумерная динамика. Задача о рюкзаке
- Видео: Двумерная динамика. Наибольшая общая подпоследовательность
- Видео: Двумерная динамика: Редакционное расстояние
- Структуры данных. Расширяющийся массив. Список
- Смежные и связные структуры данных. Работа с классами и динамической памятью.
- Понятие амортизированной сложности. Стратегии реализации динамического массива.
- Реализации списков.
- Сравнение быстродействия основных операций для массивов и списков.
- Стек. Очередь. Очередь с приоритетами
- Стек LIFO: реализация на массиве и связном списке. Классические приложения стека.
- Очередь FIFO: реализация на циклическом массиве и связном списке. Классические приложения очереди. Дек.
- Интерфейс очереди с приоритетами. Двоичная куча.
- Деревья. Хеш-таблицы
- Интерфейс АТД «Множество» и «Словарь».
- Двоичные деревья поиска. Поиск, добавление и удаление элементов: рекурсивная и нерекурсивная реализация.
- Принципы функционирования хеш-таблиц. Разрешение коллизий: метод цепочек, открытая адресация.
- Балансирующиеся деревья
- Недостатки наивной реализации двоичного дерева поиска.
- Обзор балансирующихся деревьев: 2-3-, красно-чёрные и AA-деревья.
- Декартово дерево. Реализация интерфейса АТД «Множество» и «Словарь».
- Множественные операции в декартовом дереве.
- Графы. Поиск в глубину
- Представление графа. Матрица смежности, списки смежности, список рёбер.
- Поиск в глубину.
- Компоненты связности.
- Поиск циклов.
- Топологическая сортировка.
- Компоненты сильной связности.
- Поиск мостов.
- Кратчайшие пути
- Кратчайшие пути в невзвешенном графе. Поиск в ширину.
- Кратчайшие пути в графе с неотрицательными весами. Алгоритм Дейкстры за O(V2) и за O(ElogV).
- Кратчайшие пути в ациклических орграфах.
- Кратчайшие пути в графе с отрицательными весами. Алгоритм Форда-Беллмана.
- Кратчайшие пути между всеми парами вершин. Алгоритм Флойда.
- Проверка графа на наличие отрицательного цикла.
- Минимальный остов. Система непересекающихся множеств
- Алгоритм Прима.
- Алгоритм Краскала.
- Структура данных «Система непересекающихся множеств» и её эвристики.
Таблицы успеваемости групп
Таблицы обновляются после практических занятий.
Текущий сервер дорешивания — vtcloud9
Сайты, помогающие улучшить навык программирования
- Цикл задач «Язык программирования C++» на acmp.ru (множество простых задач, решение каждой из которых можно уточнить у Владимира Александровича)
- Открытый курс «Введение в программирование» от Яндекса и Высшей школы экономики на stepik.org (видеолекции и задачи по разным темам, от простых до сложных)
Решение проблем с локалью при вводе/выводе вещественных чисел
На сервере по умолчанию используется русская локаль, что может порождать 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);