#АиСД

Программа

1. Понятие алгоритма. RAM-модель. O-символика.

Приводим пример алгоритма вычисления чисел Фибоначчи. Сравниваем время работы рекурсивной и итеративной версии. Считаем количество операций. Лемма о количестве операций $\geq 2^{n/2}$. Пример сортировки массива методом вставки. Считаем количество операций в наихудшем случае. Квадратичная сортировка. Оценка количества операций сверху. O-символика. Модель памяти. RAM-модель.

Выбираем язык программирования. C++ или Python.

2. Сортировки массивов. Сортировка слиянием.

Квадратичные сортировки. Сортировка вставкой, пузырьком и сортировка обменом. Пример сортировки n log(n). Сортировка слиянием. Рекурсивные алгоритмы. Оценка быстродействия. Анализ рекуррентных соотношений. Теорема об основном методе. Реализация на C++. Стратегия разделяй и властвуй.

3. Сортировки массивов. Сортировка кучей. 

Структура данных куча. Реализация кучи на массиве. Операции вставки и взятия наименьшего элемента. Сортировка кучей. Оценка быстродействия. Теорема о нижней границе быстродействия алгоритмов сравнения. -Цифровая сортировка.

4. Сортировки массивов. Быстрая сортировка.

Быстрая сортировка. Оценка быстродействия - худший случай. Подсчет быстродействия рандомизированного алгоритма. Порядковая статистика. Алгоритм Хоара. Реализация на C++.

5. Динамические структуры данных. Списки.

Алгоритм Хоара для нахождения k-ой порядковой статистики. Динамические структуры. Однонаправленный и двунаправленный список. Реализация на C++.

6. Структуры данных: стеки очередь.

Структуры данных стек и и очередь. Реализация стека на массиве и списке. Динамическое выделение памяти. Амортизированное время работы. Реализация стека и очереди в C++ (библиотека STL) и Python. Мало материала

7. Хеш-функции.

Хеш функции, хеш значения, коллизии, обработка коллизий. Свойства хорошей хеш функции, способы построения хеш функций, примеры. Фильтр Блума. Поиск элементов. Хеш таблицы в стандартной библиотеке C++. Шаблонный класс std::unordered_map.

8. Жадные стратегии

Жадные стратегии. Примеры (stepik). Код Хафмана.

9. Динамическое программирование.

Динамическое программирование. Вычисление чисел Фибоначчи - реализация, использующая идею динамического программирования. Задача о кузнечике. Наибольшая возрастающая последовательность. Редакторское расстояние (расстояние Левенштейна).

1. Вместо исходной задачи решаем множество перекрывающихся (зависимых) задач. Ответы для подзадач сохраняются в таблице.
2. Задача может решаться рекурсивно (программирование сверху вниз) или итеративно (снизу вверх)
3. Часто можно уменьшить размер памяти для хранения таблицы.

10. Строки. КМП - алгоритм

Алгоритмы работы со строками. Поиск подстроки. Алгоритм Рабина-Карпа. Алгоритм Кнута — Морриса — Пратта.

11. Динамические структуры данных. Графы. Алгоритмы обхода графов

Основные определения теории графов. Приложения, использующие графы как структуры данных. Представление графов в ЭВМ. Алгоритмы обхода графов: поиск в глубину и поиск в ширину. Эйлеров и гамильтонов пути. Поиск компонент связности и бикомпонентов.

12. Графы. Оптимизационные задачи на графах.

Алгоритмы поиска кратчайших путей: алгоритм Флойда и алгоритм Дейкстры. Построение кратчайших остовов: алгоритм Краскала

13. Графы. Сбалансированные деревья и деревья поиска

14. Параллельное программирование. Обзор-1

Проблематика распараллеливания. Работа на системах с общей памятью (openMP). Пример задачи Дирихле.

15. Параллельное программирование. Обзор-2

Работа на системах с распределенной памятью (MPI). Пример задачи Дирихле. Видеокарты. MapReduce.

16. Введение в теорию сложности вычислений. Основные сложностные классы задач

Исторический очерк теории сложности вычислений. Сложностные классы задач. Определение и взаимосвязь классов P и NP. Определение и примеры NP-полных задач.

17. Резерв.

• Элементарные структуры данных и С++

  Стек (stack), очередь (queue), "дек" (очередь с двумя концами / Deque) и операции над ними. Списки (односвязный, двусвязный), голова и хвост списка. Приоритетная очередь. Поиск в списке, добавление и удаление элементов. Особенности реализации указанных структур данных. Объектно-ориентированное программирование и С++. Классы, шаблоны. Стек как пример контейнера, Динамически выделяемая память, указатели. Выделение и освобождение памяти. Стандартная библиотека шаблонов (STL) – введение. Контейнер std::vector (модель динамического массива). Шаблонные классы std::array, std::list и std::forward_list. Шаблонный класс std::deque и адаптер std::stack.

---

alg-course

материалы к курсу по алгоритмам и структурам данных

wiki - https://github.com/nasrutdinov/alg-course/wiki/%D0%9F%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0-%D0%BA%D1%83%D1%80%D1%81%D0%B0

Задачи для зачета *-минимальный набор, [] - необязательная часть

*Реализовать вычисление чисел Фибоначчи рекурсивным и итеративным способом. [Сравнить время работы, построить график работы в зависимости от номера числа]

*Реализовать "наивное" и быстрое возведение в степень. . [Сравнить время работы, построить график работы в зависимости от степени, в качестве числа взять "большое" целое число]

*Реализовать квадратичные сортировки (вставками, выбора, пузырьком). [Сравнить время работы, построить график работы в зависимости от размера массива, срвнить на упорядоченных в обратную сторону].

Реализовать быструю сортировку.

Реализовать кодирование Хаффмана.

*Реализовать подсчет частоты встречаемости символов в строке.

Реализовать кучу с помощью массива.

Реализовать кучу через библиотечные классы.

Реализовать кодирование Хаффмана.

*Реализовать нахождение наибольшей возрастающей последовательности .

Задан англо-русский словарь в виде текстового файла: английское слово {пробел} перевод. Сделать русско-английский словарь. Слова отсортировать по алфавиту.

По словарю перевести текст с русского на английский.

Подготовка к ФЭПО https://fepo.i-exam.ru/fgos_pim_struct