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

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Нет описания правки
 
(не показано 8 промежуточных версий этого же участника)
Строка 1: Строка 1:
== План лекций ==
== Новости и замечания ==
Для более быстрой связи лучше использовать v.folunin@gmail.com вместо v.folunin@ulstu.ru (со второго адреса пересылка выполняется не так оперативно).


[http://docs.google.com/document/d/1lvI-7gs7uyxnciw-NKvTITNgLA6qt83l1BNZYzW7d3o/edit?usp=sharing Конспект лекций, составляемый студентами]
== Ответы редакции на письма читателей ==
=== О компараторах ===
'''Вопрос:''' Когда для сортировки я использую компаратор вида <tt>return a.x < b.x;</tt>, всё работает, но стоит мне изменить компаратор на <tt>return a.x <= b.x;</tt>, как я получаю ошибку «invalid comparator». С чем это связано?


* Сложность алгоритмов. Сортировки (05.09.2016)
'''Ответ:''' Компаратор <tt>f(a, b)</tt> для функции <tt>sort()</tt> (а также для <tt>set</tt> и <tt>map</tt>) должен определять ''строгий частичный порядок'' (strict weak ordering) на элементах множества. Это означает, что должны выполняться следующие свойства:
* Антирефлексивность: всегда <tt>f(a, a) == false</tt> (ни один элемент не может идти до самого себя);
* Антисимметричность: если <tt>f(a, b) == true</tt>, то <tt>f(b, a) == false</tt> (если a идёт до b, то b не может идти до a);
* Транзитивность: если <tt>f(a, b) == true</tt> и <tt>f(b, c) == true</tt>, то <tt>f(a, c) == true</tt> (если a идёт до b, а b — до c, то a идёт до c).
 
Функция <tt>sort()</tt> использует компаратор так:
* Если <tt>f(a, b)</tt>, то a «меньше» b;
* Если <tt>!f(a, b)</tt> и <tt>f(b, a)</tt>, то a «больше» b;
* Если <tt>!f(a, b)</tt> и <tt>!f(b, a)</tt>, то a «равно» b.
Сортировка не сможет упорядочить элементы правильно, если одновременно будут истинны <tt>f(a, b)</tt> и <tt>f(b, a)</tt>. Если используется компаратор вида <tt>return a.x <= b.x;</tt>, то при одинаковых значениях <tt>x</tt> у разных элементов эти элементы не смогут быть упорядочены, так как получается, что каждый из них должен идти перед другим (не говоря уже о сравнении элемента с самим собой). Поэтому возникает исключение.
 
== Материалы по программированию на C++ ==
* [http://stepik.org/course/363/syllabus Курс «Введение в программирование на C++» от Яндекса и НИУ ВШЭ]
* [http://docs.google.com/document/d/1WtBaPGFmSQxc9QPgdD0zGvhsK4TGOLYff9pBBARWQlM/edit Краткая справка по указателям]
* [http://www.cplusplus.com/reference/ Исчерпывающее описание стандартной библиотеки]
 
== Лекции ==
=== Конспект ===
[http://docs.google.com/document/d/1lvI-7gs7uyxnciw-NKvTITNgLA6qt83l1BNZYzW7d3o/edit?usp=sharing Конспект лекций]
 
В 2016 г. составлялся студентами. В настоящее время неспешно переписывается преподавателем.
 
=== План ===
* Сложность алгоритмов. Сортировки
: Правила асимптотического анализа алгоритмов. Асимптотические обозначения. Основные классы сложности.
: Правила асимптотического анализа алгоритмов. Асимптотические обозначения. Основные классы сложности.
: Сортировки: выбором, вставками, слиянием, быстрая. &Omega;-оценка для сортировок сравнением.
: Сортировки: выбором, вставками, слиянием, быстрая. &Omega;-оценка для сортировок сравнением.
: Устойчивость сортировок. Сортировки за линейное время: подсчётом, поразрядная.
: Устойчивость сортировок. Сортировки за линейное время: подсчётом, поразрядная.


* Бинарный поиск (19.09.2016)
* Бинарный поиск
: Бинарный поиск элемента в отсортированном массиве. Поиск первого и последнего вхождения.
: Бинарный поиск элемента в отсортированном массиве. Поиск первого и последнего вхождения.
: Бинарный поиск по ответу.
: Бинарный поиск по ответу.
Строка 14: Строка 40:
: Тернарный поиск.
: Тернарный поиск.


* Динамическое программирование. Жадные алгоритмы (28.09.2016)
* Динамическое программирование. Жадные алгоритмы
: Решение задач комбинаторной оптимизации: полный перебор и методы его сокращения.
: Решение задач комбинаторной оптимизации: полный перебор и методы его сокращения.
: Жадные алгоритмы. Принцип жадного выбора. Задачи: непрерывный рюкзак, выбор заявок, размен монет, коды Хаффмана.
: Жадные алгоритмы. Принцип жадного выбора. Задачи: непрерывный рюкзак, выбор заявок, размен монет, коды Хаффмана.
: Динамическое программирование. Критерии применимости ДП. Ленивая рекурсия и просмотр вперёд. Восстановление решения.
: Динамическое программирование. Критерии применимости ДП. Ленивая рекурсия и просмотр вперёд. Восстановление решения.
: [[Динамическое программирование|Виды одномерной и двумерной динамики.]]
: [[Динамическое программирование|Виды одномерной и двумерной динамики.]]  
:: [http://www.youtube.com/watch?v=SFeCrCme4tk Видео: План решения задачи методом динамического программирования]
:: Краткие видео по динамическому программированию: [http://www.youtube.com/watch?v=SFeCrCme4tk 1] [http://www.youtube.com/watch?v=1h_3VYrpHFc 2] [http://www.youtube.com/watch?v=wuXC13OqcJ8 3] [http://www.youtube.com/watch?v=t2DpD9GnhfU 4] [http://www.youtube.com/watch?v=HtrgxH3feME 5] [http://www.youtube.com/watch?v=-yiKNcjcK0Y 6] [http://www.youtube.com/watch?v=r6LRslQvveQ 7]
:: [http://www.youtube.com/watch?v=1h_3VYrpHFc Видео: Одномерная динамика. Количество путей в полосе]
:: [http://www.youtube.com/watch?v=wuXC13OqcJ8 Видео: Одномерная динамика. Оптимальный путь в полосе]
:: [http://www.youtube.com/watch?v=t2DpD9GnhfU Видео: Одномерная динамика с привязкой. Наибольшая возрастающая подпоследовательность]
:: [http://www.youtube.com/watch?v=HtrgxH3feME Видео: Двумерная динамика. Задача о рюкзаке]
:: [http://www.youtube.com/watch?v=-yiKNcjcK0Y Видео: Двумерная динамика. Наибольшая общая подпоследовательность]
:: [http://www.youtube.com/watch?v=r6LRslQvveQ Видео: Двумерная динамика: Редакционное расстояние]


* Структуры данных. Расширяющийся массив. Список
* Структуры данных. Расширяющийся массив. Список
Строка 71: Строка 91:
:  Структура данных &laquo;Система непересекающихся множеств&raquo; и её эвристики.
:  Структура данных &laquo;Система непересекающихся множеств&raquo; и её эвристики.


== Таблицы успеваемости групп ==
== Практика ==
К каждой лекции прилагается комплект задач на [http://vtcloud9.ulstu.ru/ru/contestlist vtcloud9]. Задачи можно решать на C++ или Java.
 
<span style="color:red">Решения задач каждого комплекта засчитываются в течение одной недели после конца лекции.</span> Если вы не смогли решить комплект по уважительной причине, сообщите преподавателю.
 
== Курсовая работа ==
* [[Курсовые работы по дисциплине «Алгоритмы и структуры данных» ИВТ УлГТУ на оценку «отлично»|Задания на оценку «отлично»]]
* [[Курсовые работы по дисциплине «Алгоритмы и структуры данных» ИВТ УлГТУ на оценку «хорошо»|Задания на оценку «хорошо»]]
* [[Курсовые работы по дисциплине «Алгоритмы и структуры данных» ИВТ УлГТУ на оценку «удовлетворительно»|Задания на оценку «удовлетворительно»]]
 
== Экзамен ==
[https://docs.google.com/spreadsheets/d/1aidtXO34UQ-jA1z7VWgtMtvPc-e2ljX6rY0eZegOdJY/edit?usp=sharing Таблица результатов дисциплины]
 
==== О выставлении бонусных баллов за плагиат ====
По каждой задаче, кроме [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 и более) — оценка «Удовлетворительно»;


* [http://docs.google.com/spreadsheets/d/1ldfBn0aZdMcTqQEA9owTLMgZdG4f067rds5T11OOF50/edit?usp=sharing Успеваемость группы АП]
Оценка за курсовую работу учитывает выбранную сложность работы и выставляется по результатам защиты.
* [http://docs.google.com/spreadsheets/d/1sZLP0ffesarlhH_48v-9GQWBhMb0LyhceDs-T0SS4u0/edit?usp=sharing Успеваемость группы ВМ]


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


Текущий сервер дорешивания &mdash; [http://vtcloud9.ulstu.ru/ru/contestlist vtcloud9]
Максимальная оценка, которую можно получить на экзамене, рассчитывается как сумма оценок за практическую работу в семестре и за курсовую работу, делённая на 2 и округлённая вверх.


== Сайты, помогающие улучшить навык программирования ==
=== Примерный список экзаменационных вопросов ===


* [http://acmp.ru/asp/do/index.asp?main=course&id_course=1 Цикл задач &laquo;Язык программирования C++&raquo; на 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 Открытый курс &laquo;Введение в программирование&raquo; от Яндекса и Высшей школы экономики на stepik.org] (видеолекции и задачи по разным темам, от простых до сложных)
* Какое назначение у этого алгоритма (структуры данных)?
* Какая асимптотическая оценка у этого алгоритма (этой операции)?


== <span style="color: red;">Задания на курсовые работы</span> ==
Асимптотический анализ алгоритмов.
:* Отсортируйте оценки сложности от наиболее эффективных к наименее эффективным
:* Дайте O-оценку для следующего кода
:* Дайте оценки для следующего графика
:* Какую сложность должен иметь алгоритм, если размер входных данных равен <...>, а ограничение времени составляет около 1 с?


<span style="color: red;">Задания на курсовые работы и требования к выполнению описаны [[Курсовые работы по дисциплине «Алгоритмы и структуры данных» ИВТ УлГТУ — 2016|в отдельной статье]]</span>.
Квадратичные сортировки
:* Нарисуйте шаги сортировки выбором (вставками) для заданного массива
:* Напишите (псевдо)код и дайте оценки сортировки выбором (вставками)


<!--
Эффективные сортировки
:* Нарисуйте шаги сортировки слиянием (быстрой) для заданного массива
:* Нарисуйте шаги слияния двух заданных массивов
:* Напишите (псевдо)код процедуры слияния
:* Нарисуйте шаги разделения заданного массива по опорному элементу
:* Составьте контрпример к быстрой сортировке, если опорный элемент выбирается указанным образом
:* Напишите (псевдо)код сортировки подсчётом


== Примерный список экзаменационных вопросов ==
Бинарный поиск. Тернарный поиск.
:* Напишите (псевдо)код поиска первого (последнего) вхождения элемента в отсортированный массив
:* Решите с помощью бинарного поиска следующую задачу: <...>
:* Напишите (псевдо)код поиска минимума (максимума) функции с одним экстремумом
:* Решите с помощью тернарного поиска следующую задачу: <...>


# Правила асимптотического анализа алгоритмов. Асимптотические обозначения.
Жадные алгоритмы и динамическое программирование
# Сортировка выбором. Сортировка вставками.
:* Задача <...> решается следующим жадным алгоритмом: <...>. Составьте контртест
# Сортировка слиянием.
:* Решите с помощью динамического программирования следующую задачу: <...>. Нарисуйте таблицу мемоизации
# Быстрая сортировка.
:* Покажите, как по таблице мемоизации восстановить оптимальный ответ (например, оптимальный путь)
# Сортировка подсчётом. Поразрядная сортировка.
# Бинарный поиск. Бинарный поиск по ответу.
# Вещественный бинарный поиск. Тернарный поиск.
# Жадные алгоритмы. Примеры. Принцип жадного выбора.
# Динамическое программирование. Примеры. Критерии применимости ДП.
# Массивы и списки: сравнение. Расширяющийся массив.
# Стек. Очередь.
# Очередь с приоритетами. Куча.
# Сортировка кучей.
# Реализация ассоциативных массивов. Деревья, хеш-таблицы.
# Основные определения теории графов. Способы задания графов. Поиск в глубину.
# Поиск компонент связности. Поиск циклов.
# Топологическая сортировка. Поиск компонент сильной связности.
# Поиск мостов.
# Поиск в ширину.
# Алгоритм Дейкстры.
# Алгоритм Форда-Беллмана. Поиск отрицательных циклов.
# Поиск кратчайших путей в ациклических ориентированных графах.
# Алгоритм Флойда. Поиск отрицательных циклов.
# Минимальное остовное дерево. Алгоритм Прима.
# Минимальное остовное дерево. Алгоритм Краскала. Система непересекающихся множеств.
-->


== Решение проблем с локалью при вводе/выводе вещественных чисел ==
Массивы и списки. Стек. Очередь
:* Нарисуйте таблицу основных операций массивов и списков с оценками
:* Напишите (псевдо)код реализации расширяющегося массива
:* Напишите (псевдо)код реализации стека (очереди) на односвязном списке


На сервере по умолчанию используется русская локаль, что может порождать Runtime Error при чтении и Wrong Answer при выводе вещественных чисел на C# и Java (так как в качестве разделителя вместо точки ожидается запятая).
Очередь с приоритетами. Куча.
:* Нарисуйте таблицу основных операций очереди с приоритетами с оценками
:* Нарисуйте шаги добавления в кучу следующих ключей: <...>
:* Нарисуйте шаги извлечения из кучи трёх элементов
:* Напишите (псевдо)код операции up (down)


Для восстановления локали на 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);
:* Покажите, как восстановить оптимальный путь

Текущая версия от 03:42, 6 января 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(V2) и за O(ElogV).
Кратчайшие пути в ациклических орграфах.
Кратчайшие пути в графе с отрицательными весами. Алгоритм Форда-Беллмана.
Кратчайшие пути между всеми парами вершин. Алгоритм Флойда.
Проверка графа на наличие отрицательного цикла.
  • Минимальный остов. Система непересекающихся множеств
Алгоритм Прима.
Алгоритм Краскала.
Структура данных «Система непересекающихся множеств» и её эвристики.

Практика

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

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

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

Экзамен

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

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

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

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

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

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

Оценки

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

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

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

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

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

Примерный список экзаменационных вопросов

В любом билете может быть задан дополнительный вопрос вида:

  • Какое назначение у этого алгоритма (структуры данных)?
  • Какая асимптотическая оценка у этого алгоритма (этой операции)?

Асимптотический анализ алгоритмов.

  • Отсортируйте оценки сложности от наиболее эффективных к наименее эффективным
  • Дайте O-оценку для следующего кода
  • Дайте оценки для следующего графика
  • Какую сложность должен иметь алгоритм, если размер входных данных равен <...>, а ограничение времени составляет около 1 с?

Квадратичные сортировки

  • Нарисуйте шаги сортировки выбором (вставками) для заданного массива
  • Напишите (псевдо)код и дайте оценки сортировки выбором (вставками)

Эффективные сортировки

  • Нарисуйте шаги сортировки слиянием (быстрой) для заданного массива
  • Нарисуйте шаги слияния двух заданных массивов
  • Напишите (псевдо)код процедуры слияния
  • Нарисуйте шаги разделения заданного массива по опорному элементу
  • Составьте контрпример к быстрой сортировке, если опорный элемент выбирается указанным образом
  • Напишите (псевдо)код сортировки подсчётом

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

  • Напишите (псевдо)код поиска первого (последнего) вхождения элемента в отсортированный массив
  • Решите с помощью бинарного поиска следующую задачу: <...>
  • Напишите (псевдо)код поиска минимума (максимума) функции с одним экстремумом
  • Решите с помощью тернарного поиска следующую задачу: <...>

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

  • Задача <...> решается следующим жадным алгоритмом: <...>. Составьте контртест
  • Решите с помощью динамического программирования следующую задачу: <...>. Нарисуйте таблицу мемоизации
  • Покажите, как по таблице мемоизации восстановить оптимальный ответ (например, оптимальный путь)

Массивы и списки. Стек. Очередь

  • Нарисуйте таблицу основных операций массивов и списков с оценками
  • Напишите (псевдо)код реализации расширяющегося массива
  • Напишите (псевдо)код реализации стека (очереди) на односвязном списке

Очередь с приоритетами. Куча.

  • Нарисуйте таблицу основных операций очереди с приоритетами с оценками
  • Нарисуйте шаги добавления в кучу следующих ключей: <...>
  • Нарисуйте шаги извлечения из кучи трёх элементов
  • Напишите (псевдо)код операции up (down)

Реализация ассоциативных массивов. Деревья, хеш-таблицы.

  • Нарисуйте таблицу основных операций деревьев и хеш-таблиц с оценками для лучшего и худшего случаев
  • Нарисуйте шаги добавления в небалансирующееся двоичное дерево поиска следующих ключей: <...>
  • Нарисуйте шаги поиска в дереве следующих ключей: <...>
  • Нарисуйте шаги добавления в хеш-таблицу с указанной хеш-функцией следующих ключей: <...>
  • Нарисуйте шаги поиска в хеш-таблице следующих ключей: <...>
  • Покажите различные стратегии разрешения коллизий в хеш-таблицах

Основные определения теории графов. Способы задания графов

  • Составьте матрицу смежности, списки смежности и список рёбер для указанного графа
  • В задаче требуется производить с графом следующие операции: <...> Какой способ хранения графа следует выбрать?

Поиск в глубину и его приложения

  • Нарисуйте шаги поиска в глубину на указанном графе
  • Напишите (псевдо)код поиска в глубину для указанной задачи (подсчёта компонент связности, поиска циклов и т. п.)
  • Найдите топологическую сортировку указанного графа

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

  • Какой алгоритм следует применить для поиска кратчайших путей на указанном графе?
  • Нарисуйте шаги поиска в ширину на указанном графе
  • Напишите (псевдо)код поиска в ширину
  • Нарисуйте шаги алгоритма Дейкстры на указанном графе
  • Нарисуйте шаги алгоритма Форда-Беллмана на указанном графе
  • Покажите, как восстановить оптимальный путь
Источник — https://acm.khpnets.info/w39/index.php?title=Дисциплина_«Алгоритмы_и_структуры_данных»_ИВТ_УлГТУ&oldid=2287