На этой странице можно скачать этот файл совершенно бесплатно и без регистрации и без отправки смс, а также без различного рода ограничений.
Скачивайте и учитесь, надеемся, наш сайт помог вам "погрызть гранит науки"
Лекции по алгоритмам
Алгоритмы и алгоритмические языки. 59 листов. Лекция 1. Представление чисел в ЭВМ. Целые. Вещественные. Ошибки вычислений. Лекция 2. Алгоритмы. Сведение алгоритмов. Нижние и верхние оценки. Сортировки. Постановка задачи. Сортировка пузырьком. Сортировка слиянием с рекурсией. Сортировка слиянием без рекурсии. Лекция 3. Алгоритмы. Сведение алгоритмов. Сортировки и связанные с ними задачи. QuickSort. Доказательство корректности работы алгоритма. Оценки времени работы алгоритма. Некоторые задачи, сводящиеся к сортировке. Лекция 4. Алгоритмы. Сведение алгоритмов. Сортировки и связанные с ними задачи. HeapSort или сортировка с помощью пирамиды. Алгоритмы сортировки за время O(N). Сортировка подсчетом. Цифровая сортировка. Сортировка вычерпыванием. Лекция 5. Алгоритмы. Сведение алгоритмов. Порядковые статистики. Поиск порядковой статистики за время Q(N) в среднем. Поиск порядковой статистики за время Q(N) в худшем случае. Язык программирования C. Переменные. Структуры данных. Вектор. Стек. Лекция 6. Структуры данных ( + в языке С: массивы, структуры, оператор typedef). Стек. Стек. Реализация 1 (на основе массива). Стек. Реализация 2 (на основе массива с использованием общей структуры). Стек. Реализация 3 (на основе указателей). Стек. Реализация 4 (на основе массива из двух указателей). Стек. Реализация 5 (на основе указателя на указатель). Очередь. Дек. Списки. Стандартная ссылочная реализация списков. Ссылочная реализация списков с фиктивным элементом. Реализация L2-списка на основе двух стеков. Реализация L2-списка с обеспечением выделения/освобождения памяти. Лекция 7. Структуры данных. Графы. Графы. Поиск пути в графе с наименьшим количеством промежуточных вершин. Представление графа в памяти ЭВМ. Лекция 8. Структуры данных. Графы. Поиск кратчайшего пути в графе. Лекция 9. Бинарные деревья поиска. Поиск элемента в дереве. Добавление элемента в дерево. Поиск минимального и максимального элемента в дереве. Удаление элемента из дерева. Поиск следующего/предыдущего элемента в дереве. Слияние двух деревьев. Разбиение дерева по разбивающему элементу. Сбалансированные и идеально сбалансированные бинарные деревья поиска. Операции с идеально сбалансированным деревом. Операции со сбалансированным деревом. Поиск элемента в дереве. Добавление элемента в дерево. Удаление элемента из дерева. Поиск минимального и максимального элемента в дереве. Поиск следующего/предыдущего элемента в дереве. Слияние двух деревьев. Разбиение дерева по разбивающему элементу. Лекция 10. Красно-черные деревья. Отступление на тему языка С. Поля структур. Отступление на тему языка С. Бинарные операции. Высота красно-черного дерева. Добавление элемента в красно-черное дерево. Однопроходное добавление элемента в красно-черное дерево. Удаление элемента из красно-черного дерева. Лекция 11. Лекция 1. B-деревья. Высота B-дерева. Поиск вершины в B-дереве. Отступление на тему языка С. Быстрый поиск и сортировка в языке С. Добавление вершины в B-дерево. Удаление вершины из B-дерева. Лекция 12. Хеширование. Метод многих списков. Метод линейных проб. Метод цепочек. Хэш-функции. Хэш-функции на основе деления. Хэш-функции на основе умножения. CRC-алгоритмы обнаружения ошибок. Лекция 14. Поиск строк. Отступление на тему языка С. Ввод-вывод строк из файла. Алгоритм поиска подстроки с использованием хеш-функции (Алгоритм Рабина-Карпа). Конечные автоматы. Отступление на тему языка С. Работа со строками. Алгоритм поиска подстроки, основанный на конечных автоматах. Лекция 15. Алгоритм поиска подстроки Кнута-Морриса-Пратта (на основе префикс-функции). Алгоритм поиска подстроки Бойера-Мура (на основе стоп-символов/безопасных суффиксов). Эвристика стоп-символа. Эвристика безопасного суффикса.
