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

Версия от 00:34, 3 января 2018

Новости и замечания

Для более быстрой связи лучше использовать v.folunin@gmail.com вместо v.folunin@ulstu.ru (со второго адреса пересылка выполняется не так оперативно).

Ответы редакции на письма читателей

О компараторах

Вопрос: Когда для сортировки я использую компаратор вида return a.x < b.x;, всё работает, но стоит мне изменить компаратор на return a.x <= b.x;, как я получаю ошибку «invalid comparator». С чем это связано?

Ответ: Компаратор f(a, b) для функции sort() (а также для set и map) должен определять строгий частичный порядок (strict weak ordering) на элементах множества. Это означает, что должны выполняться следующие свойства:

Антирефлексивность: всегда f(a, a) == false (ни один элемент не может идти до самого себя);
Антисимметричность: если f(a, b) == true, то f(b, a) == false (если a идёт до b, то b не может идти до a);
Транзитивность: если f(a, b) == true и f(b, c) == true, то f(a, c) == true (если a идёт до b, а b — до c, то a идёт до c).

Функция sort() использует компаратор так:

Если f(a, b), то a «меньше» b;
Если !f(a, b) и f(b, a), то a «больше» b;
Если !f(a, b) и !f(b, a), то a «равно» b.

Сортировка не сможет упорядочить элементы правильно, если одновременно будут истинны f(a, b) и f(b, a). Если используется компаратор вида return a.x <= b.x;, то при одинаковых значениях x у разных элементов эти элементы не смогут быть упорядочены, так как получается, что каждый из них должен идти перед другим (не говоря уже о сравнении элемента с самим собой). Поэтому возникает исключение.

Материалы по программированию на C++

Лекции

Конспект

Конспект лекций

В 2016 г. составлялся студентами. В настоящее время неспешно переписывается преподавателем.

План

Сложность алгоритмов. Сортировки

Правила асимптотического анализа алгоритмов. Асимптотические обозначения. Основные классы сложности.

Сортировки: выбором, вставками, слиянием, быстрая. Ω-оценка для сортировок сравнением.

Устойчивость сортировок. Сортировки за линейное время: подсчётом, поразрядная.

Бинарный поиск

Бинарный поиск элемента в отсортированном массиве. Поиск первого и последнего вхождения.

Бинарный поиск по ответу.

Вещественный бинарный поиск.

Тернарный поиск.

Динамическое программирование. Жадные алгоритмы

Решение задач комбинаторной оптимизации: полный перебор и методы его сокращения.

Жадные алгоритмы. Принцип жадного выбора. Задачи: непрерывный рюкзак, выбор заявок, размен монет, коды Хаффмана.

Динамическое программирование. Критерии применимости ДП. Ленивая рекурсия и просмотр вперёд. Восстановление решения.

Виды одномерной и двумерной динамики.

Краткие видео по динамическому программированию: 1 2 3 4 5 6 7

Структуры данных. Расширяющийся массив. Список

Смежные и связные структуры данных. Работа с классами и динамической памятью.

Понятие амортизированной сложности. Стратегии реализации динамического массива.

Реализации списков.

Сравнение быстродействия основных операций для массивов и списков.

Стек. Очередь. Очередь с приоритетами

Стек LIFO: реализация на массиве и связном списке. Классические приложения стека.

Очередь FIFO: реализация на циклическом массиве и связном списке. Классические приложения очереди. Дек.

Интерфейс очереди с приоритетами. Двоичная куча.

Деревья. Хеш-таблицы

Интерфейс АТД «Множество» и «Словарь».

Двоичные деревья поиска. Поиск, добавление и удаление элементов: рекурсивная и нерекурсивная реализация.

Принципы функционирования хеш-таблиц. Разрешение коллизий: метод цепочек, открытая адресация.

Балансирующиеся деревья

Недостатки наивной реализации двоичного дерева поиска.

Обзор балансирующихся деревьев: 2-3-, красно-чёрные и AA-деревья.

Декартово дерево. Реализация интерфейса АТД «Множество» и «Словарь».

Множественные операции в декартовом дереве.

Графы. Поиск в глубину

Представление графа. Матрица смежности, списки смежности, список рёбер.

Поиск в глубину.

Компоненты связности.

Поиск циклов.

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

Компоненты сильной связности.

Поиск мостов.

Кратчайшие пути

Кратчайшие пути в невзвешенном графе. Поиск в ширину.

Кратчайшие пути в графе с неотрицательными весами. Алгоритм Дейкстры за O(V²) и за O(ElogV).

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

Кратчайшие пути в графе с отрицательными весами. Алгоритм Форда-Беллмана.

Кратчайшие пути между всеми парами вершин. Алгоритм Флойда.

Проверка графа на наличие отрицательного цикла.

Минимальный остов. Система непересекающихся множеств

Алгоритм Прима.

Алгоритм Краскала.

Структура данных «Система непересекающихся множеств» и её эвристики.

Практика

К каждой лекции прилагается комплект задач на vtcloud9. Задачи можно решать на C++ или Java.

Решения задач каждого комплекта засчитываются в течение одной недели после конца лекции. Если вы не смогли решить комплект по уважительной причине, сообщите преподавателю.

Курсовая работа

Экзамен

Таблица результатов дисциплины

О выставлении бонусных баллов за плагиат

По каждой задаче, кроме 8E, автоматически формируется сводка данных об идентичности решений (пример).

Если два автора имеют по некоторой задаче два решения, совпадающие на 80% или более, то каждый из авторов получает по этой задаче 1 бонусный балл.

Каждый бонусный балл сокращает итоговую оценку за практическую работу в семестре на 2 (другими словами, нивелирует 2 сданные задачи).

Важно: преподаватель намеренно воздержался от того, чтобы самостоятельно анализировать подозрительные случаи. Получить 1-2 бонусных балла — это нормально, и ожидается, что сдавшие большую часть задач не пострадают, даже если антиплагиат ошибётся. Если у вас есть претензии к результатам, готовьтесь обсуждать их на консультации.

Оценки

Оценка за практическую работу в семестре рассчитывается по количеству сданных задач (с учётом баллов антиплагиата). Всего в семестре было предложено 64 задачи.

70% сданных задач (45 и более) — оценка «Отлично»;
50% сданных задач (32 и более) — оценка «Хорошо»;
30% сданных задач (19 и более) — оценка «Удовлетворительно»;

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

Для допуска к экзамену необходимо иметь оценки не ниже «Удовлетворительно» за практическую работу в семестре и за курсовую работу.

Максимальная оценка, которую можно получить на экзамене, рассчитывается как сумма оценок за практическую работу в семестре и за курсовую работу, делённая на 2 и округлённая вверх.

@@ Строка 102: / Строка 102: @@
 == Экзамен ==
-(будет добавлено позднее)
+[https://docs.google.com/spreadsheets/d/1aidtXO34UQ-jA1z7VWgtMtvPc-e2ljX6rY0eZegOdJY/edit?usp=sharing Таблица результатов дисциплины]
-<!--
+==== О выставлении бонусных баллов за плагиат ====
-== <span style="color: red;">Задания на курсовые работы</span> ==
+По каждой задаче, кроме [http://vtcloud9.ulstu.ru/ru/problem-pid-c61b?ps=1&smt=a&smpwid=0 8E], автоматически формируется сводка данных об идентичности решений ([http://moss.stanford.edu/results/631595772/ пример]).
+Если два автора имеют по некоторой задаче два решения, совпадающие на 80% или более, то каждый из авторов получает по этой задаче 1 бонусный балл.
+Каждый бонусный балл сокращает итоговую оценку за практическую работу в семестре на 2 (другими словами, нивелирует 2 сданные задачи).
+<span style="color: red">Важно: преподаватель намеренно воздержался от того, чтобы самостоятельно анализировать подозрительные случаи. Получить 1-2 бонусных балла — это нормально, и ожидается, что сдавшие большую часть задач не пострадают, даже если антиплагиат ошибётся. Если у вас есть претензии к результатам, готовьтесь обсуждать их на консультации.</span>
+==== Оценки ====
+Оценка за практическую работу в семестре рассчитывается по количеству сданных задач (с учётом баллов антиплагиата). Всего в семестре было предложено 64 задачи.
+* 70% сданных задач (45 и более) — оценка «Отлично»;
+* 50% сданных задач (32 и более) — оценка «Хорошо»;
+* 30% сданных задач (19 и более) — оценка «Удовлетворительно»;
-<span style="color: red;">Задания на курсовые работы и требования к выполнению описаны [[Курсовые работы по дисциплине «Алгоритмы и структуры данных» ИВТ УлГТУ — 2016|в отдельной статье]]</span>.
+Оценка за курсовую работу учитывает выбранную сложность работы и выставляется по результатам защиты.
+Для допуска к экзамену необходимо иметь оценки не ниже «Удовлетворительно» за практическую работу в семестре и за курсовую работу.
+Максимальная оценка, которую можно получить на экзамене, рассчитывается как сумма оценок за практическую работу в семестре и за курсовую работу, делённая на 2 и округлённая вверх.
+<!--
 == Примерный список экзаменационных вопросов ==
@@ Строка 136: / Строка 151: @@
 # Алгоритм Флойда.
-== Решение проблем с локалью при вводе/выводе вещественных чисел ==
-На сервере по умолчанию используется русская локаль, что может порождать 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);
 -->