company_banner

Лекции Техносферы. Подготовительный курс «Алгоритмы и структуры данных» (весна 2016)

  • Tutorial


Цель этого курса — познакомить слушателей с основными алгоритмами, применяемыми для разработки программного обеспечения. Вы научитесь выбирать подходящие структуры данных и алгоритмы для реализации возникающих задач, и узнаете, как использовать языки С/С++ для реализации алгоритмов.

Курс ведет Сергей Бабичев, доцент кафедр информатики и вычислительной математики, а также теоретической и прикладной информатики в МФТИ. Под катом вас ждет восемь лекций:

  • Лекция 1. «Введение. Исполнители. Абстракции интерфейсов. Рекурсия»
  • Лекция 2. «Жадные алгоритмы»
  • Лекция 3. «Сортировки»
  • Лекция 4. «Поиск. Списки»
  • Лекция 5. «Деревья»
  • Лекция 6. «Хеш-таблицы»
  • Лекция 7. «Динамическое программирование»
  • Лекция 8. «Алгоритмы на графах»

Лекция 1. «Введение. Исполнители. Абстракции интерфейсов. Рекурсия»



На первой лекции вспомним основы алгоритмов и посмотрим, как их можно использовать на практике. Поговорим о свойствах алгоритмов, исполнителях, нотациях, параметрах и классах сложности. Разберем неполиномиальную задачу (сколько поместится предметов в рюкзак). Кроме того, поговорим об абстракциях (массив, стек, множество) и рекурсии (основная теорема).

Лекция 2. «Жадные алгоритмы»



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

Лекция 3. «Сортировки»



Сведения про разные сортировки и около сортировочную деятельность. Будут рассмотрены несколько технологий сортировок: сравнением, быстрая, с использованием свойств элементов, внешняя и другие. Также дается сравнение сортировок, когда и какой метод нужно применять.

Лекция 4. «Поиск. Списки»



Занимаемся поиском, работой с динамическими структурами данных, работой со списками и деревьями. Проводим сравнительный анализ методов поиска: простой последовательный поиск, распределяющий поиск, поиск с сужением зоны. Кроме того, поговорим о структуре данных «список», который тоже используется для поиска, и структуре данных «дерево», который считается обобщением «списка».

Лекция 5. «Деревья»



Продолжение темы «деревьев», затронутой еще на второй лекции. Рассматриваются две абстракции (множество и отображение), от них перейдем к сбалансированным деревьям поиска, красно-черным деревьям (двоичное дерево поиска), после чего коснемся интерфейса абстракции приоритетной очереди (основанной на деревьях).

Лекция 6. «Хеш-таблицы»



Как производить внешний поиск (на внешних носителях) с использованием B-деревьев, что такое обобщенный быстрый поиск, хеш-функции, разные виды хеш-таблиц. Также вы узнаете об еще одном виде поиска, который хорошо подходит к параллельным алгоритмам — списки с пропусками. Напоследок рассматривается пример решения задачи, которая требует нескольких разных структур данных.

Лекция 7. «Динамическое программирование»



Тут мы поговорим о способах решения больших задач, которые сами по себе делятся на подзадачи. Узнаете, как с помощью структур данных можно решать своеобразные задачи (о количестве маршрутов, о возрастающей подпоследовательности наибольшей длины), метод решения которых мы попробуем обобщить. Пойдет разбор этапов решения задачи методом динамического программирования.

Лекция 8. «Алгоритмы на графах»



Последняя лекция, в которой будут разные виды представления граф, понятие релаксации, несколько режимов поиска (BFS, DFS), топологическая сортировка, поиск остовных деревьев в графе, алгоритм Дейкстры (его связь с жадными алгоритмами) и алгоритм Флойда-Уоршалла (и его связь с динамическим программированием).

По завершению курса вы узнаете основные понятия: исполнитель, абстракция, объекты, методы, итерация, рекурсия, жадные алгоритмы, динамическое программирование, сортировка, поиск, графы. Получите навык анализировать основные свойства алгоритмов, научитесь выбирать необходимые структуры данных для решения задач и обосновывать свой выбор. Сможете эффективно реализовывать алгоритмы на языках С и С++.

Плейлист всех лекций находится по ссылке. Напомним, что актуальные лекции и мастер-классы о программировании от наших IT-специалистов в проектах Технопарк, Техносфера и Технотрек по-прежнему публикуются на канале Технострим.
  • +52
  • 31,2k
  • 7
Mail.ru Group
1110,00
Строим Интернет
Поделиться публикацией

Комментарии 7

    0
    В каком объеме и какую математическую подготовку необходимо иметь для просмотра и понимания данного курса?
      0
      А также на каком уровне С++? Заранее спасибо за ответ.
        0
        Насколько я вижу, для понимания алгоритмов математика не нужна. С её помощью лектор объясняет сложность задачи и прочие сопутствующие вещи. А сам курс читается математикам, ибо он(лектор) явно говорит, что они(слушатели) уже знают матанализ.
          0
          При этом лектор так и говорит, надо решать задачи, будете не хуже Перельмана. То есть курс для учёных — математиков.
          Кстати в первой лекции лектор советует две книги isbn: 978-5-4439-0236-4 (попроще первая редакция), 978-5-8459-2016-4. Подскажите, пожалуйста, ещё какую нибудь литературу советуют?
          А то я видео смотреть не буду, книжки полистаю.
            0
            Там тоже полно формул и куча доказательств. А лектор на видео старается какие-то аналогии приводить, которые легче для понимания.
              0
              Есть список рекомендованной литературы другого нашего проекта — Технопарка https://habrahabr.ru/company/mailru/blog/265103/ там есть часть по алгоритмам и структурам данных.
          0
          В части «Динамическое программирование» уже тяжело без знаний серьёзной математики. И догадаться, что там лектор показывает указкой на слайдах не всегда получается.

          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.