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

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Нет описания правки
Строка 1: Строка 1:
== План лекций ==
== Материалы по программированию на 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 Конспект лекций, составляемый студентами]
== Лекции ==
=== Конспект ===
[http://docs.google.com/document/d/1lvI-7gs7uyxnciw-NKvTITNgLA6qt83l1BNZYzW7d3o/edit?usp=sharing Конспект лекций]


* Сложность алгоритмов. Сортировки (05.09.2016)
В 2016 г. составлялся студентами. В настоящее время неспешно переписывается преподавателем.
 
=== План ===
* Сложность алгоритмов. Сортировки
: Правила асимптотического анализа алгоритмов. Асимптотические обозначения. Основные классы сложности.
: Правила асимптотического анализа алгоритмов. Асимптотические обозначения. Основные классы сложности.
: Сортировки: выбором, вставками, слиянием, быстрая. Ω-оценка для сортировок сравнением.
: Сортировки: выбором, вставками, слиянием, быстрая. Ω-оценка для сортировок сравнением.
: Устойчивость сортировок. Сортировки за линейное время: подсчётом, поразрядная.
: Устойчивость сортировок. Сортировки за линейное время: подсчётом, поразрядная.


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


* Динамическое программирование. Жадные алгоритмы (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: Строка 73:
:  Структура данных «Система непересекающихся множеств» и её эвристики.
:  Структура данных «Система непересекающихся множеств» и её эвристики.


== Таблицы успеваемости групп ==
== Практика ==
 
К каждой лекции прилагается комплект задач на [http://vtcloud9.ulstu.ru/ru/contestlist vtcloud9]. Задачи можно решать на C++ или Java.
* [http://docs.google.com/spreadsheets/d/1ldfBn0aZdMcTqQEA9owTLMgZdG4f067rds5T11OOF50/edit?usp=sharing Успеваемость группы АП]
* [http://docs.google.com/spreadsheets/d/1sZLP0ffesarlhH_48v-9GQWBhMb0LyhceDs-T0SS4u0/edit?usp=sharing Успеваемость группы ВМ]
 
Таблицы обновляются после практических занятий.


Текущий сервер дорешивания — [http://vtcloud9.ulstu.ru/ru/contestlist vtcloud9]
<span style="color:red">Решения задач каждого комплекта засчитываются в течение одной недели после конца лекции.</span> Если вы не смогли решить комплект по уважительной причине, сообщите преподавателю.


== Сайты, помогающие улучшить навык программирования ==
== Курсовая работа ==
(будет добавлено позднее)


* [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> ==
== <span style="color: red;">Задания на курсовые работы</span> ==


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

Версия от 19:59, 3 сентября 2017

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

Лекции

Конспект

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

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

План

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

Практика

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

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

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

(будет добавлено позднее)

Экзамен

(будет добавлено позднее)


Источник — https://acm.khpnets.info/w39/index.php?title=Дисциплина_«Алгоритмы_и_структуры_данных»_ИВТ_УлГТУ&oldid=2252