|
所在平台: Coursera |
课程主页: https://www.coursera.org/learn/algorithms-part1-ru
课程评论：没有评论
课程名称：算法，第一部分 概述：本课程涵盖了每位专业程序员必备的算法和数据结构的关键知识，重点关注实际应用领域和算法在Java中的效率分析。第一部分讨论了基本数据结构以及排序和搜索算法。第二部分将探讨图和字符串的处理算法。所有课程内容均为免费提供，完成后不颁发任何证书。 课程大纲： 1. 课程简介：讲解算法的基本概念，第一部分的内容。 2. 不相交集合系统：通过动态连通性问题展示算法的开发和分析方法，介绍不相交集合数据类型及其几种实现方式，并应用于物理化学中的渗流问题。 3. 算法分析：运用科学方法来分析算法的效率，通过计算实验测量程序运行时间，建立数学模型来解释算法行为，并讨论Java程序的内存使用。 4. 栈和队列：探讨存储对象集合的两种基本数据类型，栈和队列的实现方法及其多种实际应用。 5. 基本排序方法：介绍排序问题及Java的Comparable接口，学习选择排序、插入排序及希尔排序等基本排序算法。 6. 合并排序：学习合并排序算法及其在排序中的应用，分析其效率，并讨论排序算法的比较和稳定性。 7. 快速排序：实现随机化快速排序算法，分析其效率，探讨随机化快速选择算法及其变体。 8. 优先队列：介绍优先队列数据类型及其二叉堆实现，讨论其在模拟物体运动中的应用。 9. 符号表基础：定义符号表API，介绍基于有序数组和无序链表的两种实现方式，以及二叉搜索树的数据结构。 10. 平衡搜索树：创建符号表以保证对搜索和插入操作的对数效率，学习2-3树和红黑树的实现方式，以及B树的应用。 11. 几何中的BDP应用：探讨一维和二维范围查询以及k维树的应用，讨论区间交叉问题。 12. 哈希表：描述哈希函数的理想特性及其Java实现，讨论哈希表的两种实现策略及其效率。 13. 符号表的应用：探讨符号表在实践中的多种应用场景，包括集合、字典客户端、索引客户端等。
Name:Введение в курс
Description:Введение в алгоритмы, часть I.
Name:Система непересекающихся множеств
Description:Мы демонстрируем наш базовый подход к разработке и анализу алгоритмов через рассмотрение проблемы динамической связности. Мы представляем тип данных непересекающихся множеств и рассматриваем несколько вариантов его реализации (быстрый поиск, быстрое объединение, взвешенное быстрое объединение и взвешенное быстрое объединение со сжатием пути). Наконец, мы применяем тип данных непересекающихся множеств для решения проблемы перколяции из физической химии.
Name:Анализ алгоритмов
Description:В основе нашего подхода к анализу эффективности алгоритмов лежит научный метод. Начнем с вычислительных экспериментов для измерения времени выполнения наших программ. Мы применяем эти измерения для формирования гипотез об эффективности. Затем мы составляем математические модели, объясняющие поведение алгоритмов. Наконец, мы рассмотрим анализ использования памяти нашими программами на Java.
Name:Стеки и очереди
Description:Мы рассмотрим два фундаментальных типа данных для хранения коллекций объектов: стек и очередь. Каждый из них реализуется с помощью односвязного списка или массива изменяющегося размера. Мы представим две продвинутые функции Java, упрощающие клиентский код: обобщенные коллекции и итераторы. Наконец, будут рассмотрены различные применения стеков и очередей, начиная от разбора арифметических выражений и заканчивая моделированием систем массового обслуживания.
Name:Элементарные методы сортировки
Description:Мы познакомим вас с проблемой сортировки и интерфейсом Comparable Java. Мы изучим два элементарных метода сортировки (сортировку выбором и сортировку вставкой), а также разновидность одного из них — сортировку методом Шелла. Также мы рассмотрим два алгоритма для равномерного перемешивания массива. В завершение мы продемонстрируем применение сортировки на практике для вычисления выпуклой оболочки множества точек с помощью алгоритма сканирования Грэма.
Name:Сортировка с объединением
Description:Мы изучим алгоритм сортировки с объединением и покажем, что он позволяет отсортировать любой массив из n элементов с максимальным количество сравнений n lg n. Также будет рассмотрена нерекурсивная версия этого алгоритма («снизу вверх»). Мы докажем, что любой алгоритм сортировки, основанный на сравнении, в худшем случае должен выполнить не менее n lg n сравнений. Мы обсудим применение различных схем упорядочения сортируемых объектов и связанную с этим концепцию устойчивости.
Name:Быстрая сортировка
Description:Мы изучим и реализуем алгоритм рандомизированной быстрой сортировки и проанализируем его эффективность. Кроме того, рассмотрим рандомизированный быстрый выбор — вариант быстрой сортировки, находящий k-й наименьший элемент за линейное время. В завершение мы рассмотрим 3-направленную быструю сортировку — вариант быстрой сортировки, особенно хорошо работающий при наличии дублирующихся ключей.
Name:Приоритизированные очереди
Description:Мы представляем тип данных «приоритизированная очередь» и его эффективную реализацию с помощью структуры данных «бинарная куча». Эта реализация также является основой эффективного алгоритма кучевой сортировки. В завершение мы познакомимся с применением приоритизированных очередей. В частности, мы смоделируем движение объекта, состоящего из n частичек, по законам упругих столкновений.
Name:Таблицы элементарных символов
Description:Мы зададим API для таблиц символов (также известных как ассоциативные массивы, карты или словари) и опишем две элементарные реализации с использованием отсортированного массива (бинарный поиск) и неупорядоченного списка (последовательный поиск). Если ключи имеют тип Comparable, мы зададим расширенный API, включающий дополнительные методы минимума и максимума, нижнего и верхнего предела, ранжирования и выбора. Для разработки эффективной реализации этого API мы изучим структуру данных «бинарное дерево поиска» и проанализируем ее эффективность.
Name:Сбалансированные деревья поиска
Description:В этой лекции наша цель состоит в создании таблицы символов с гарантированной логарифмической эффективностью поиска и вставки (а также множества других операций). Мы начнем с рассмотрения 2-3-деревьев, которые легко анализировать, но сложно реализовать. Затем рассмотрим красно-черные бинарные деревья поиска, которые послужат новым способом реализации 2-3-деревьев в виде бинарных деревьев поиска. Наконец мы представим B-деревья — обобщение 2-3-деревьев, широко применяющееся при реализации файловых систем.
Name:Применение БДП в геометрии
Description:Мы начнем с поиска в 1-мерных и 2-мерных диапазонах, цель которого — найти все точки в заданном 1-мерном или 2-мерном диапазоне. Для выполнения данной задачи рассмотрим k-мерные деревья — естественное обобщение БДП, ключи которого — точки на плоскости (или в пространствах более высокого порядка). Также рассмотрим проблемы пересечений, когда требуется найти все пересечения среди множества отрезков или прямоугольников.
Name:Хэш-таблицы
Description:Вначале мы опишем желательные свойства хэш-функции и ее реализацию в Java, включая фундаментальное допущение о равномерности хэширования, определяющее потенциальную успешность хэширования. Затем рассмотрим две стратегии реализации хэш-таблиц — раздельное связывание цепочками и линейное исследование. Обе стратегии имеют постоянную по времени эффективность поиска и вставки при удовлетворении допущения о равномерности хэширования.
Name:Области применения таблиц символов
Description:Рассмотрим различные практические области применения таблиц символов, включая множества, клиенты словарей, клиенты индексирования и разреженные векторы.
Данный курс охватывает ключевые знания об алгоритмах и структурах данных, которыми обязан владеть каждый профессиональный программист. При этом акцент сделан на практических областях применения и научном анализе эффективности алгоритмов, реализованных на Java. В части I рассматриваются элементарные структуры данных, а также алгоритмы сортировки и поиска. В части II освещаются алгоритмы обработки графов и строк. Все компоненты этого курса предоставляются бесплатно. При этом по завершении не выдаются какие-либо сертификаты.
