Компания
1 083,48
рейтинг
1 марта 2015 в 16:23

Разработка → Лекции Технопарка. 1 семестр. Алгоритмы и структуры данных tutorial

Очередной пост в рамках нашего цикла лекций Технопарка. В этот раз мы предлагаем вашему вниманию курс, посвящённый алгоритмам и структурам данных. Автор курса — Степан Мацкевич, сотрудник компании ABBYY.

Лекция 1. Основы


Начало первой лекции посвящено обсуждению основных понятий, на которых строится вся дальнейшая программа курса: что такое алгоритм и структура данных. Описаны базовые виды алгоритмов, их характеристики и методы анализа. Далее рассматриваются примеры создания алгоритмов для вычисления чисел Фибоначчи, проверки числа на простоту, быстрого возведения числа в целую степень. В конце лекции рассказывается об особенностях использования алгоритмов для работы с массивами: создание однопроходных алгоритмов, поиск минимального элемента, бинарный поиск.



Лекция 2. Элементарные структуры данных


Вторая лекция посвящена изучению элементарных структур данных. В начале даётся определение понятия «абстрактного типа данных». Далее лектор рассказывает о том, что такое амортизационный анализ и каковы его особенности.

Рассматриваются такие виды структур и абстрактные типы данных, как:
  • массив и динамический массив;
  • стек, очередь и дэк;
  • очередь с приоритетом;
  • связные списки: однонаправленные и двунаправленные;
  • двоичная куча.

Разбираются недостатки и преимущества каждого вида структур, а также их реализация в виде программного кода.



Лекция 3. Сортировки (часть 1)


Тема сортировок оказалась настолько объёмной, что её пришлось разделить на две лекции. В первой части подробно рассматриваются такие виды алгоритмов, как:
  • сортировка одного, двух и трёх элементов;
  • сортировка выбором;
  • сортировка вставками;
  • сортировка пузырьком;
  • быстрая сортировка Хоара.

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



Лекция 4. Сортировки (часть 2)


На этой лекции рассматриваются другие виды алгоритмов и их применение:
  • сортировка слиянием, в том числе двух упорядоченных массивов;
  • сортировка подсчётом;
  • поразрядная сортировка;
  • пирамидальная сортировка и ряд других.

Напоследок проводится сравнительный анализ разных алгоритмов.



Лекция 5. Хеш-таблицы


Из этой лекции вы сначала узнаете, что такое метод поиска хешированием, какие бывают хеш-функции (в том числе хеш-функции строк). Затем идёт подробное рассмотрение хеш-таблиц и способов их применения: что они собой представляют, каковы основные методы разрешения коллизий (метод цепочек и метод открытой адресации), а также методы вставки, удаления и поиска элементов. Напоследок проводится сравнение хеш-таблиц по затратам времени и памяти.



Лекция 6. Деревья


Последняя лекция в рамках курса АиСД посвящена таким структурам данных, как деревья. Разумеется, в начале лекции дается определение понятия «деревья», рассматриваются их характеристики и приводятся примеры. Затем вы узнаете, как деревья представлены в памяти, какие есть способы обхода дерева. Далее рассматриваются так называемые двоичные деревья поиска и группа самобалансирующихся деревьев: декартовы и АВЛ-деревья. И в завершение лекции рассказывается об абстрактном типе данных «ассоциативный массив».

Автор: @Dmitry21

Комментарии (14)

  • НЛО прилетело и опубликовало эту надпись здесь
    • +1
      Да, при этом есть же stepic(и там даже был уже похожий курс), да и для алго/обучения языкам запилить проверяющую систему, имхо, не очень сложно. Может стоит как то скооперироваться, вместо того что бы похожий материал с похожей программой, готовить, можно было бы какой нибудь продвинутый курс прочитать например?:)

      Хотя вот CSС, вот свои курсы закрывает со временем, а вы тоже так планируете делать?
      • +1
        Насчет кооперации — подумаем, Stepic — хорошая мысль )
        А что CSC закрывает, я не понял?
        • НЛО прилетело и опубликовало эту надпись здесь
          • 0
            а, ясно. ну тут я ничего сказать не могу за коллег )
    • +1
      Хоть я и не автор статьи, но думаю ничего страшного не случится, если отвечу как студент присутствующий на данных видеолекциях.

      Проверяющая система (в природе) есть, также как и задачи. На самом деле у нас было разделение на 3 модуля по 6 задач в каждом, и в каждой задаче есть около 6 вариантов + проверка на утечки памяти. Помимо этого было ограничение на рантайм и последующая модерация семинаристами: на синтаксис, структуру и прочее.

      Есть-ли смысл в выкладывание их? Не знаю, с одной стороны да, с другой многие задачи были олимпиадного уровня и у нас происходил разбор в неформальной обстановке (на семинарах) о том, как их решать и с какой стороны лучше подходить. Т.е если взять тупо какую-то задачу, то будет необходимо несколько дней думать о том, как к ней подступиться, так можно и мотивацию потерять )))). Просто сама тестовая система и подход не предполагает дистанционного обучения.
      • 0
        Костя, спасибо за ответ. Совершенно согласен
        • НЛО прилетело и опубликовало эту надпись здесь
          • +1
            Мы подумаем о системе тестирования. Лекции выкладываем для того, что бы принести пользу комьюнити.
            • НЛО прилетело и опубликовало эту надпись здесь
  • 0
    Залил лекции на rutracker. Качество — лучшее что было доступно в YouTube.

    «Лекции Технопарка. 1 семестр. Алгоритмы и структуры данных»
    rutracker.org/forum/viewtopic.php?t=4963811
    • 0
      а задачи есть?
      • 0
        На сайте Технопарка, по моему, их нет. Если есть то перезалью торрент.
        • 0
          Задачи пока не планируем публиковать

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

Самое читаемое Разработка