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



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

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

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

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



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

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



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

Лекція 3. «Сортування»



Відомості про різні сортування і близько сортувальну діяльність. Будуть розглянуті кілька технологій сортувань: порівнянням, швидка, з використанням властивостей елементів, зовнішня та інші. Також дається порівняння сортувань, коли і який метод потрібно застосовувати.

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



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

Лекція 5. «Дерева»



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

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



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

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



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

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



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

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

Плейлист всіх лекцій перебуває за адресою. Нагадаємо, що актуальні лекції та майстер-класи про програмуванні від наших ІТ-фахівців в проектах Технопарк, Техносфера і Технотрек як і раніше, публікуються на каналі Технострим.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.