...

воскресенье, 1 марта 2015 г.

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

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

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




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





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




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

Рассматриваются такие виды структур и абстрактные типы данных, как:



  • массив и динамический массив;

  • стек, очередь и дэк;

  • очередь с приоритетом;

  • связные списки: однонаправленные и двунаправленные;

  • двоичная куча.




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


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




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


  • сортировка одного, двух и трёх элементов;

  • сортировка выбором;

  • сортировка вставками;

  • сортировка пузырьком;

  • быстрая сортировка Хоара.




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


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




На этой лекции рассматриваются другие виды алгоритмов и их применение:


  • сортировка слиянием, в том числе двух упорядоченных массивов;

  • сортировка подсчётом;

  • поразрядная сортировка;

  • пирамидальная сортировка и ряд других.




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


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




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


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




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


This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.


Комментариев нет:

Отправить комментарий