Алгоритмы для разработчиков

Курс о разработке и использовании разнообразных алгоритмов и структур данных

Длительность

5 месяцев

Начало занятий

29 июля

Продолжительность
5 месяцев, 3 академических часа в неделю
Начало занятий
29 июля
Что даст вам этот курс

  • Понимание принципов работы разнообразных алгоритмов, структур данных

  • Умение использовать готовые алгоритмы и структуры данных и создавать свои под поставленную задачу

  • Владение техникой вычисления сложности алгоритмов

  • Освоение продвинутых структур данных: хэш-таблиц, графов, деревьев поиска и многих других

  • Умение решать алгебраические задачи и задачи динамического программирования


Знание классических алгоритмов и структур данных — обязательное требование, которое предъявляют брендовые IT-компании к претендентам на вакансию Middle developer.

Благодаря этим знаниям, можно повысить производительность и улучшить качество кода. Именно поэтому так важно понимать принципы работы алгоритмов и структур данных и уметь использовать их с учётом поставленных задач. Получить эти ценные навыки вы сможете на этом курсе по уникальной авторской программе от инженера-программиста из Лаборатории Касперского.

Курс предназначен для разработчиков, владеющих разными языками программирования. Он подходит и для Middle-специалистов, которые застоялись на месте, и для «джуниоров», которые хотят быстрее вырасти как профессионалы и избежать многих ошибок. И, конечно, курс по алгоритмам и структурам данных просто жизненно необходим всем тем, кто прогулял или недостаточно серьёзно отнёсся к занятиям по алгоритмизации в университете ;-)

И, конечно, разбираем примеры алгоритмов и делаем домашние задания не на псевдокоде, а на одном из языков: С++, Python, Java.


50+ работодателей ждут наших выпускников

Большое количество практических заданий

Без алгоритмов и структур данных языки программирования мертвы. Это именно то, что вдыхает жизнь в Java, C++ и Python
Михаил Горшков
Преподаватель курса
Без алгоритмов и структур данных языки программирования мертвы. Это именно то, что вдыхает жизнь в Java, C++ и Python
Михаил Горшков
Преподаватель курса
Преподаватели
Михаил Горшков
Лаборатория Касперского
Евгений Волосатов
Михаил Степанов
Jet Infosystems
Программирую на С++ и Python в течение 18 лет, как хобби — играю на фортепиано. Работаю в Лаборатории Касперского, окончил курс по С++ в Otus и занимаюсь на курсе DataScience. Сейчас являюсь наставником на курсе С++. Специально для проекта OTUS создал программу "Алгоритмы для разработчиков".

Этот курс для тех, кто не проходил или пропустил алгоритмы в своем ВУЗе, а также для всех программистов, интересующихся данной темой: от любителей до профессионалов. Вы узнаете о популярных алгоритмах и структурах данных, научитесь их реализовывать и применять, сможете претендовать на вакансии в лучшие компании России и всего мира: Яндекс, Google, Facebook!

Присоединяйтесь, будет круто!
Профессиональный программист. Преподаватель языка Java в колледже.
Автор видеокурсов по C#, Java, PHP

20 лет опыта ведущим программистом в разных фирмах и опыта преподавания в университете, колледже. 6 лет опыта ведения вебинаров и создания видеокурсов

Три самых крупных завершенных проекта:
PHP. Служба знакомств в интернете - PHP, MySQL, FreeBSD, C/C++
C#. Программа расчёта заработной платы на АЭС - C#, MS-SQL Server
Java. Видеокурс создания игры Сапёр на Java: https://goo.gl/24DgBg

Статьи на Habrahabr:
Как я создавал методику изучения C# - habr.com/post/239825/
Об альтернативном образовании и про C# - habr.com/post/257957/
Изучение C# — Практический подход - habr.com/post/304142/

Участие в IT-конференциях в Литве, призовое место в конкурсе программирования InfoBalt, призовое место на республиканской олимпиаде по математике и информатике

С окончания школы в 1996 году постоянно преподавал информатику в университете, школе, на кружках, в ДДТ, на предприятиях, в колледже. С 2013 года ведет вебинары онлайн, записывает видеокурсы
https://www.VideoSharp.info/

В 2002 году закончил Вильнюсский государственный университет по специальности «Магистр математики и информатики», а в 2008 году по специальности «Учитель профессии»

«В детстве меня вдохновила "Занимательная ***" серия книг Я. И. Перельмана. Считаю своим призванием создать занимательную методику обучения программированию.»
Михаил работает в отделе машинного обучения компании Jet Infosystems. Занимается проектами по агрегации отзывов, по анализу и оптимизации производства крупных промышленных компаний. В data science пришел из промышленного программирования на Python, где разрабатывал код для "толстого клиента" в проекте по созданию "умных окон".

Ранее учил талантливых школьников программированию, машинному обучению и программированию учебных моделей спутников.

Область интересов: data science, математика, космос и Python.
Мой взгляд на программирование: с великой силой приходит великая ответственность.
Михаил
Горшков
Евгений
Волосатов
Михаил
Степанов
Преподаватели
Михаил Горшков
Лаборатория Касперского
Программирую на С++ и Python в течение 18 лет, как хобби — играю на фортепиано. Работаю в Лаборатории Касперского, окончил курс по С++ в Otus и занимаюсь на курсе DataScience. Сейчас являюсь наставником на курсе С++. Специально для проекта OTUS создал программу "Алгоритмы для разработчиков".

Этот курс для тех, кто не проходил или пропустил алгоритмы в своем ВУЗе, а также для всех программистов, интересующихся данной темой: от любителей до профессионалов. Вы узнаете о популярных алгоритмах и структурах данных, научитесь их реализовывать и применять, сможете претендовать на вакансии в лучшие компании России и всего мира: Яндекс, Google, Facebook!

Присоединяйтесь, будет круто!
Евгений Волосатов
Профессиональный программист. Преподаватель языка Java в колледже.
Автор видеокурсов по C#, Java, PHP

20 лет опыта ведущим программистом в разных фирмах и опыта преподавания в университете, колледже. 6 лет опыта ведения вебинаров и создания видеокурсов

Три самых крупных завершенных проекта:
PHP. Служба знакомств в интернете - PHP, MySQL, FreeBSD, C/C++
C#. Программа расчёта заработной платы на АЭС - C#, MS-SQL Server
Java. Видеокурс создания игры Сапёр на Java: https://goo.gl/24DgBg

Статьи на Habrahabr:
Как я создавал методику изучения C# - habr.com/post/239825/
Об альтернативном образовании и про C# - habr.com/post/257957/
Изучение C# — Практический подход - habr.com/post/304142/

Участие в IT-конференциях в Литве, призовое место в конкурсе программирования InfoBalt, призовое место на республиканской олимпиаде по математике и информатике

С окончания школы в 1996 году постоянно преподавал информатику в университете, школе, на кружках, в ДДТ, на предприятиях, в колледже. С 2013 года ведет вебинары онлайн, записывает видеокурсы
https://www.VideoSharp.info/

В 2002 году закончил Вильнюсский государственный университет по специальности «Магистр математики и информатики», а в 2008 году по специальности «Учитель профессии»

«В детстве меня вдохновила "Занимательная ***" серия книг Я. И. Перельмана. Считаю своим призванием создать занимательную методику обучения программированию.»
Михаил Степанов
Jet Infosystems
Михаил работает в отделе машинного обучения компании Jet Infosystems. Занимается проектами по агрегации отзывов, по анализу и оптимизации производства крупных промышленных компаний. В data science пришел из промышленного программирования на Python, где разрабатывал код для "толстого клиента" в проекте по созданию "умных окон".

Ранее учил талантливых школьников программированию, машинному обучению и программированию учебных моделей спутников.

Область интересов: data science, математика, космос и Python.
Мой взгляд на программирование: с великой силой приходит великая ответственность.
Минимальные знания
  • Опыт программирования на одном из следующих языков: С++, Python, Java (начальный или средний уровень)
  • Знание элементарной математики в объёме средней школы
  • Минимальное знание алгоритмов и структур данных и желание развиваться в области их изучения
Процесс обучения
Обучение проходит онлайн, в формате вебинаров. Длительность этого курса составляет 5 месяцев, финальный месяц отводится для выполнения проектной работы и оттачивания полученных навыков.

Расписание занятий включает 2 вебинара в неделю по 2 академических часа и от 2 до 4 часов на домашнюю работу.


Во время обучения слушатель может задавать преподавателю уточняющие вопросы по материалам лекций, домашних заданий и выпускного проекта.
Программа обучения
Модуль 1
Введение в алгоритмы и структуры данных
Модуль 2
Сортировки
Модуль 3
Деревья
Модуль 4
Хеш-таблицы
Модуль 5
Графы
Модуль 6
Алгоритмы на строках
Модуль 7
Динамическое программирование
Модуль 8
Вероятностные алгоритмы и структуры данных
Модуль 9
Численные методы оптимизации
Модуль 10
Проектная работа
Введение в алгоритмы и структуры данных
Введение в алгоритмы, RAM-модель. Порядок роста функций.
Студенты ознакомятся с эмулятором RAM-машины, поймут состав элементарных операций и научатся оценивать сложность алгоритмов.
Домашние задания: 1
1 Реализация алгоритма сортировки на RAM
1. Написать на RAM алгоритм деления двух натуральных чисел через вычитание.
На входе делимое и делитель.
На выходе частное и остаток.

2. Написать на RAM алгоритм простой сортировки.
На входе число N и потом N целых чисел.
На выходе N чисел отсортированных по возрастанию.
для (каждого i от 0 до N-1)
для (каждого k от i+1 до N-1)
если (элемент[i] > элемент[k])
элемент[k] <=> элемент[i];

3. Написать, сколько времени ушло на выполнение домашнего задания.
Базовые структуры данных: массив, динамический массив, список, стек, очередь, очередь с приоритетами
Студенты ознакомятся с реализацией базовых структур данных, и научатся правильно выбирать структуру данных под задачу
Домашние задания: 1
1 Неполный массив или очередь с приоритетом.
1 задание. Динамические массивы.
Написать метод добавления и удаления элементов:
void add(T item, int index);
T remove(int index); // возвращает удаляемый элемент
по индексу во все варианты динамических массивов:
SingleArray, VectorArray, FactorArray, MatrixArray *.
+1 балл.

2 задание. Таблица сравнения производительности.
Сравнить время выполнения разных операций
для разных массивов с разным порядком значений.
* сделать обёртку над ArrayList() и тоже сравнить.
Составить таблицу и приложить её скриншот.
Сделать выводы и сформулировать их в нескольких предложениях.
+1 балл.

3 задание. Приоритетная очередь (на выбор).
Написать реализацию PriorityQueue - очередь с приоритетом.
Варианты реализации - список списков, массив списков
Методы к реализации:
enqueue(int priority, T item) - поместить элемент в очередь
T dequeue() - выбрать элемент из очереди
+2 балла

4 задание (на выбор).
Написать Реализацию класса SpaceArray массив массивов с неполным заполнением.
Делать на основе одного из уже созданных массивов и/или списков.
+2 балла дополнительно.

За выполнение задания до начала следующего урока:
+1 балл.

Напишите сколько времени ушло на домашнее задание.

Для реализации можно использовать только
стандартные массивы [], созданные классы массивов и/или списков.
Стандартные библиотеки не используем!
Шахматное программирование
Студенты повторят все правила игры в шахматы, получат техническое задание по их кодированию.
Домашние задания: 1
1 Битый конь и FEN-ходы
1. Решить задачу "Лошадью ходи" на сайте:
https://www.videosharp.info/console/task/level=1745

2. Написать программу выполнения корректного хода
для любой шахматной позиции по техническому заданию с тестами.
Алгебраические алгоритмы: алгоритм Евклида, быстрое возведение в степень, решето Эратосфена, быстрое вычисление чисел Фибоначчи
Студенты ознакомятся с использованием и реализацией некоторых популярных алгебраических алгоритмов.
Домашние задания: 1
1 Вычисление чисел Фибоначчи
Написать следующие алгоритмы и сравнить их быстродействие.
Приложить скриншоты/ссылки на результаты экспериментов.

1. Алгоритм Евклида поиска НОД +1 балл
1a. Через вычитание
1b. Через остаток

2. Алгоритм возведения в степень +1 балл
2а. Итеративный (n умножений)
2b. Через степень двойки с домножением
2c. Через двоичное разложение показателя степени.

3. Алгоритмы поиска кол-ва простых чисел до N +1 балл
3a. Через перебор делителей.
3b. Оптимизация перебора делителей.
3c. Решето Эратосфена.
3d. Решето Эратосфена с битовой матрицей, по 32 значения в одном int (по желанию) +1 балл

4. Алгоритм поиска чисел Фибоначчи +1 балл
4a. Через рекурсию
4b. Через итерацию
4c. По формуле золотого сечения
4d. Через умножение матриц (по желанию) +1 балл

+1 балл за отправку домашнего задания до начала след. вебинара.

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


Рекомендации по реализации вычисления чисел Фибоначчи через матричный алгоритм:
Алгоритм решета Эратосфена, экономичный к памяти, сразу откинуть четные числа
Варианты: битовые операции, сегментация
1) Битовые операции - храним как элемент массива целое число, например byte в Java 8 бита. Соответственно, каждый бит представляет собой true/false для определенного числа. Используя этот алгоритм можно уменьшить потребности в памяти в 8 раз. Откинув четные числа, еще в 2 раза.
2) Сегментация - делаем блоками по определенного размера. Выделяем блок фиксированного размера считаем в нем, например блок размером 1000, а посчитать надо до 5000. Соответственно сеем 5 блоков, не забывая, как у нас смещаются индексы.
Сортировки
Сортировка вставками, сортировка Шелла, сортировка выбором, пузырьковая сортировка
Студенты освоят алгоритмы сортировки вставками, выбором, пузырьком, сортировку Шелла. По окончании занятия студенты смогут реализовывать и правильно применять данные алгоритмы.
Домашние задания: 1
1 Реализовать Insertion Sort и Shell Sort
Реализовать алгоритмы insertion sort и Shell sort. Дополнительно: протестировать работу алгоритмов на случайных массивах и на практически упорядоченных массивах, сравнить производительность. Сравнить производительнсоть сортировки Шелла c разной последовательностью шагов.

Как сравнивать производительность:

Для алгоритмов, как минимум, Insertion Sort, Shell Sort с двумя вариантами последовательностей шагов, сделать для каждого следующие измерения:

Создать массивы размера от 20, 40, 80, 160 ... и до~100.000 элементов для C++/Java или ~10.000 элементов в случае python. Для каждого размера сделать по три массива: случайный (функцией для shuffle из упорядоченного), массив, в котором перемешаны ~10% элементов, и массив, в котором перемешаны 5 элементов.

Замерять процессорное время для каждого алгоритма и каждого массива, составить табличку в формате .csv либо график, приложить к коду.

Варианты последовательностей "шагов" (gap sequences) Shell Sort можно брать отсюда, любые, но интереснее будет с O() < O(n^2): https://en.wikipedia.org/wiki/Shellsort#Gap_sequences
Пирамидальная сортировка (heap sort), tree sort
Студенты смогут реализовывать и применять пирамидальную сортировку, tree sort.
23 мая, 20:00 — 21:30
Лектор: Михаил Степанов
Домашние задания: 1
1 Реализация heapsort
- Реализовать Drown - 1 балл
- Реализовать BuildHeap - 1 балл
- Реализовать алгоритм Heapsort - 1 балл
- Можно все inline и без отдельных процедур, тогда 3 балла, если все иделаьно работает
- Heapsort должен работать для получения зачета
- Дополнительно 1: реализовать Drown через стек, а не через рекурсию - 1 балл
- Дополнительно 2: реализовать удаление элемента с сохранением свойст пирамиды - 1 балл
- Дополнительно 3: реализовать очередь с приоритетами при помощи heap, сравнить с тем, что было ранее сделано - без баллов, по своему желанию (т.к. нам сложно гарантировать быструю проверку)
Сортировка слиянием, timsort. Быстрая сортировка
Студенты освоят и смогут реализовать алгоритмы быстрой сортировки, сортировки слиянием и timsort.
28 мая, 20:00 — 21:30
Лектор: Михаил Степанов
Домашние задания: 1
1 Реализовать quicksort или mergesort, дополнительно - усовершенствовать
Реализовать:

MergeSort или QuickSort (рандомизированный и обычный) -
- алгоритм работает корректно, используется insertion sort: 3 балла
- алгоритм работает корректно, но выполняет много лишних действий / отклоняется от реализации не в лучшую сторону - 2 балл

Дополнительно:
- quicksort - сравнить рандомизированный и обычный варианты - 1 балл
- mergsesort - добавить обработку run'ов - 1 балл

- распараллелить алгоритм - 1 балл (если считаете, что этот материал надо разобрать отдельно - напишите в слак) - 1 балл

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

Будет разобран научатся алгоритм для нахождения порядковых статистик за линейное время.
30 мая, 20:00 — 21:30
Лектор: Михаил Степанов
Домашние задания: 1
1 Сортировки за линейное время
Основное задание - 2 балла

- Реализовать алгоритмы Counting Sort и Radix Sort
- Для сортировки разрядов Radix Sort должен использовать Counting Sort

Дополнительно

- Сдать работу вовремя - 1 балл
- Реализовать Trie (с возможностью добавления и удаления элементов) - 1 балл
- Реализовать Trie-based Radix Sort - 1 балл
Деревья
Двоичные деревья поиска, декартовы деревья, АВЛ-деревья
Студенты узнают, что такое дерево, двоичные дерево поиска и декартово дерево. Изучат структуры данных и алгоритмы, реализующие операции над ними.
4 июня, 20:00 — 21:30
Лектор: Евгений Волосатов
Домашние задания: 1
1 Реализовать АВЛ дерево
Написать реализацию АВЛ-дерева

Методы к реализации:
insert
remove
rebalance

Опционально1 :
Декартово дерево, операции merge, split, add, remove

Опционально2:
Написать реализацию бинарного дерева поиска или расширяющегося дерева или рандомизированного дерева
Включить в глобальный тест

Сроки сдачи: до 24.02.2019 включительно
Красно-черные деревья, расширяющиеся деревья, рандомизированные деревья
Студенты освоят и смогут применять красно-черные деревья, расширяющиеся деревья и рандомизированные деревья
6 июня, 20:00 — 21:30
Лектор: Евгений Волосатов
Домашние задания: 1
1 Реализация красно-чёрного дерева, вставки и поиска
Основное задание:
1. Реализовать самостоятельно красно-черное дерево, операции вставка, удаление, поиск

дедлайн 24.02.19 включительно

2. Тест на производительность.
Сравнить АВЛ-дерево и красно-черное дерево.
- тест вставки
- тест поиска
- тест удаления

Тест вставки
- 5 млн случайных чисел - random(0..LONG_MAX)
- 5 млн упорядоченных чисел
- данные из dataset в материалах занятия. Код загрузки датасета в массив там же.

Замерить высоту дерева

Тест поиска
- 5 млн случайных чисел - random(0..LONG_MAX)
- 5 тыс случайных чисел, сохранить в массив, потом поиск этих чисел в цикле 1000 раз. Общее количество поиска - 5 млн
- 5 млн случайных чисел из датасет

Тест удаление
- 1 млн случайных чисел

Замерить высоту дерева

Опционально 1:
Реализовать на выбор одно из деревьев
- BST - бинарное дерево поиска
- Splay - расширяющееся дерево
- рандомизированное дерево

Добавить в тест. Выложить в slack.
Те, кто пишет на C++, Python договориться через slack что бы реализовать разные варианты

Опционально 2:
Сделать глобальный тест, добавив туда все варианты деревьев, что будут в slack
Добавить в тест
- hash-таблицы
- стандартную реализацию деревьев из языка

дедлайн 12.03.19 включительно

B-деревья, B+-деревья. Деревья отрезков
Студенты освоят и смогут применять B-деревья и В+-деревья. Ознакомятся с деревьями отрезков.
11 июня, 20:00 — 21:30
Лектор: Евгений Волосатов
Домашние задания: 1
1 Реализовать оптимальное дерево поиска
Реализовать оптимальное дерево поиска
- Алгоритм 1
- Алгоритм 2

Сравнить
1) время построения, включая сортировку
2) время поиска

Тест провести на dataset из прошлого занятия. Включить в глобальный тест (только dataset)

Опционально 1:
Написать реализацию бинарного дерева поиска или расширяющегося дерева или рандомизированного дерева.
Включить в глобальный тест

Опционально 2:
У кого была реализация декартового дерева использовать его как оптимальное дерево поиска. Включить в тест на dataset

Сроки сдачи: до 24.02.2019 включительно
Хеш-таблицы
Таблицы с прямой адресацией. Хэш-таблицы, хэш-функции. Метод цепочек (chaining).
Студенты смогут реализовывать хэш-таблицы с прямой адресацией, а также изучат работу хэш-функций и хэш-таблиц. Борьба с коллизиями будет разобрана на примере метода цепочек.
13 июня, 20:00 — 21:30
Лектор: Михаил Степанов
Домашние задания: 1
1 Хэш-таблицы, часть I
- Домашняя работа одна на всю неделю. Это _первая половина_, которую можно начать выполнять сейчас.
- Вторая половина будет после занятия в среду.

1. Реализовать хеш-таблицу, использующую метод цепочек
- дополнительно: для хранения внутри цепочек при достижении значительного числа элементов (~32) заменять их на BST

2. _Или_: реализовать хеш-таблицу с открытой адресацией
- дополнительно: реализовать "ленивое" удаление
- реализовать квадратичный пробинг
Хеш-функции. Стратегии поиска. Универсальное хеширование
Студенты смогут реализовывать хэш-таблицы с открытой адресацией. Будут рассмотрены различные стратегии поиска, универсальное хеширование, различные хеш-функции.
18 июня, 20:00 — 21:30
Лектор: Михаил Степанов
Домашние задания: 1
1 Домашнего задания нет
Домашнего задания нет
Универсальное и идеальное хэширование.
Будет рассмотрено универсальное и идеальное хеширование, области их применения.
20 июня, 20:00 — 21:30
Лектор: Михаил Степанов
Домашние задания: 1
1 Домашнего задания нет
Домашнего задания нет
Графы
Поиск в ширину. Поиск в глубину, поиск компонент сильной связности. Алгоритм Косарайю.
Студенты освоят, смогут реализовывать и применять поиск в ширину и поиск в глубину. Будут разобраны алгоритмы поиска компонент сильной связности.
25 июня, 20:00 — 21:30
Лектор: Евгений Волосатов
Домашние задания: 1
1 Реализовать алгоритм Косарайю
Реализовать алгоритм Косарайю

Входные данные:
Граф задан вектором смежности int A[N][Smax]. Это п.5 в структурах данных в лекции. Отличие только в том, что вершины нумеруются от 0 а не от 1, и номера самой вершины первым столбцом в матрице не будет, будут только номера смежных вершин

Задание:
Реализовать алгоритм Косарайю, рекурсивный вариант, как он был дан в лекции
Если понадобится использование стека/очереди обязательно применение собственных структур данных из предыдущих занятий

Выходные данные:
Результат должен быть представлен в виде массива int[] component где элемент с номером вершины содержит номер компонента

Дополнительное задание 1
Реализовать итеративный поиск в глубину с сохранением состояния, что бы уже пройденные уровни повторно не проходились

Дополнительное задание 2
Реализовать поиск по критерию стоимости

Дедлайн 10.03.2019
Топологическая сортировка
Студенты освоят, смогут реализовывать и применять топологическую сортировку.
27 июня, 20:00 — 21:30
Лектор: Евгений Волосатов
Домашние задания: 1
1 Алгоритм Демукрона
Реализовать алгоритм Демукрона

Граф задан вектором смежности int A[N][Smax]. Это п.5 в структурах данных в лекции. Отличие только в том, что вершины нумеруются от 0 а не от 1, и номера самой вершины первым столбцом в матрице не будет, будут только номера смежных вершин

Задание:
Реализовать алгоритм Демукрона
Если понадобится использование стека/очереди обязательно применение собственных структур данных из предыдущих занятий
Можно использовать стандартный массив [] встроенный в язык

Выходные данные:
Результат должен быть представлен в виде массива int[][] level где первый индекс - номер уровня, на каждом уровне массив, с номерами вершин, принадлежащих этому уровню

Дополнительное задание 1
Реализовать алгоритм Тарьяна

Дополнительное задание 2
Реализовать алгоритм поиска мостов или точек сочленения

Дедлайн 17.03.2019 включительно
Минимальные остовные деревья. Алгоритмы Крускала и Прима
Студенты освоят, смогут реализовывать и применять алгоритмы нахождения минимальных остовных деревьев.
2 июля, 20:00 — 21:30
Лектор: Евгений Волосатов
Домашние задания: 1
1 Реализовать алгоритм нахождения минимального остовного дерева
Реализовать алгоритм Краскала

Граф задан вектором смежности int A[N][Smax]. Это п.5 в структурах данных в лекции. Отличие только в том, что вершины нумеруются от 0 а не от 1, и номера самой вершины первым столбцом в матрице не будет, будут только номера смежных вершин

Задание:
Реализовать алгоритм Краскала
Структура Union-Find собственной реализации.
Если понадобится использование стека/очереди обязательно применение собственных структур данных из предыдущих занятий
Можно использовать стандартный массив [] встроенный в язык

Выходные данные:
Результат должен быть представлен в виде массива Edge[] edges где Edge - класс, содержащий пару вершин, которые соединяет это ребро
Edge
{
int v1;
int v2;
}
Для любителей компактного хранения можно упаковать в long два int-а :)
Тогда результат будет long[] edges

Дополнительное задание 1
Реализовать алгоритм Прима

Дополнительное задание 2
Реализовать алгоритм Борувки

Дедлайн 17.03.2019 включительно
Поиск кратчайшего пути в графе. Алгоритмы Дейкстры, Беллмана-Форда, Флойда-Уоршалла
Студенты освоят, смогут реализовывать и применять алгоритмы поиска кратчайшего пути в графе.
4 июля, 20:00 — 21:30
Лектор: Евгений Волосатов
Домашние задания: 1
1 Реализовать алгоритм Дейкстры
Реализовать классику всех времен и народов, алгоритм Дейкстры :)

Граф задан вектором смежности int A[N][Smax]. Это п.5 в структурах данных в лекции. Отличие только в том, что вершины нумеруются от 0 а не от 1, и номера самой вершины первым столбцом в матрице не будет, будут только номера смежных вершин

Задание:
Реализовать алгоритм Дейкстры
Если понадобится использование дерева/кучи обязательно применение собственных структур данных из предыдущих занятий
Можно использовать стандартный массив [] встроенный в язык

Выходные данные:
Результат должен быть представлен в виде массива Edge[] edges где Edge - класс, содержащий пару вершин, которые соединяет это ребро
Edge
{
int v1;
int v2;
}
Для любителей компактного хранения можно упаковать в long два int-а :)
Тогда результат будет long[] edges

Дополнительное задание 1
"Расскажи своей бабушке".
Рассказать идею алгоритма Дейкстры совей бабушке так, что бы она это поняла. Поделиться своим опытом в слаке. Не забыть приложить ссылку на пост в задании

Дополнительное задание 2
Реализовать алгоритм Флойда-Уоршалла или Беллама-Форда на выбор

Дедлайн 24.03.2019 включительно
Алгоритмы Джонсона, А*, и способы решения задачи коммивояжера
Студенты освоят, смогут реализовывать и применять алгоритмы Джонсона, А* и ознакомятся со способами решения задачи коммивояжера.
9 июля, 20:00 — 21:30
Лектор: Евгений Волосатов
Домашние задания: 1
1 Предложить вариант алгоритма для решения задачи
Задача: Нужно быстро строить кратчайший маршрут на большие расстояния по реальной дорожной сети, например от Лиссабона до Владивостока. Можно взять данные OSM.

Предложить вариант решения задачи, работающий быстрее, чем применение A* влоб.

Идею и описание алгоритма прислать в виде небольшой записки.

Дополнительное задание 1: Закодить алгоритм A*
Дополнительное задание 2: Закодить алгоритм Джонсона
Heap manager, Garbage collector
Будет рассмотрена работа garbage collector'a на примере современных языков программирования.
11 июля, 20:00 — 21:30
Алгоритмы на строках
Алгоритм Бойера-Мура
Студенты освоят, смогут реализовывать и применять алгоритм Бойера-Мура.
23 июля, 20:00 — 21:30
Лектор: Михаил Степанов
Алгоритм Кнута-Морриса-Пратта
Студенты освоят, смогут реализовывать и применять алгоритм Кнута-Морриса-Пратта.
25 июля, 20:00 — 21:30
Лектор: Михаил Степанов
Домашние задания: 1
1 Реализовать алгоритмы Бойера-Мура и Кнута-Морриса-Пратта
Алгоритм Ахо-Корасика
Студенты освоят, смогут реализовывать и применять алгоритм Ахо-Корасика.
30 июля, 20:00 — 21:30
Лектор: Михаил Степанов
Код Хаффмана, алгоритм Лемпела-Зива. Run-length encoding.
Будет разобран run-length encoding (RLE). Студенты освоят кодирование Хаффмана, алгоритм Лемпела-Зива.
1 августа, 20:00 — 21:30
Лектор: Евгений Волосатов
Шифрование данных, базовые принципы и алгоритмы.
Будут разобраны основные алгоритмы шифрования данных.
6 августа, 20:00 — 21:30
Лектор: Евгений Волосатов
Динамическое программирование
Кэширование
Кеширование: структура кеша, стратегии кеширования, кеширование данных из БД, кеширование выполнения функций, кеширование в многопоточных системах.
8 августа, 20:00 — 21:30
Динамическое программирование: задачи динамического программирования
Студенты освоят и смогут применять метод динамического программирования для решения практических задач.
13 августа, 20:00 — 21:30
Лектор: Евгений Волосатов
Домашние задания: 1
1 Решить задачу на динамическое программирование
Вероятностные алгоритмы и структуры данных
Фильтр Блума
Студенты освоят, смогут реализовывать и применять фильтр Блума.
22 августа, 20:00 — 21:30
Алгоритмы MinHash, SimHash
Студенты освоят, смогут реализовывать и применять алгоритмы MinHash, SimHash.
27 августа, 20:00 — 21:30
Домашние задания: 1
1 Реализовать фильтр Блума, вероятностные алгоритмы
Алгоритмы HyperLogLog, Count-Min Sketch
Студенты освоят, смогут применять и реализовывать алгоритмы HyperLogLog и Count-Min Sketch.
29 августа, 20:00 — 21:30
Численные методы оптимизации
Поиск экстремума функции
Потск эстремума функции, основные методы. Многокритериальные задачи, область Поретто, свертка критериев.
3 сентября, 20:00 — 21:30
Лектор: Михаил Степанов
Нейронные сети. Алгоритм обратного распространения ошибки (backpropagation)
Будет рассмотрено устройство нейросетей, алгоритм backpropagation и подходы к созданию современных фреймворков для работы с нейросетями.
5 сентября, 20:00 — 21:30
Лектор: Михаил Степанов
Проектная работа
Урок о проекте
Урок о проекте - какие могут быть проекты, что для этого надо сделать + вопросы по несделанным домашкам.
Домашние задания: 1
1 Проектная работа
Промежуточная встреча
Обзор состояния дел по проекту, текущие вопросы студентов по их проектам.
Презентация проектов
Презентация проектов, рефлексия.
Заключительное занятие
Обзор пройденных тем. Студенты вспомнят пройденный материал.
Выпускной проект
В рамках курса предусмотрена защита проекта. Это отдельная работа, на выполнение которой отводится последний месяц обучения. Проект включает в себя имплементацию сложного алгоритма и/или сложной структуры данных. При подготовке проектной работы студент может рассчитывать на консультации преподавателя и его экспертные советы.


  • написать кастомную хэш-таблицу

  • реализовать свой менеджер памяти с garbage collector

  • реализовать B-tree индекс для СУБД

  • любая тема на выбор студента, связанная с продвинутыми алгоритмами и структурами данных

Прошедшие открытые вебинары по курсу
Открытый вебинар - это настоящее занятие в режиме он-лайн с преподавателем курса, которое позволяет посмотреть, как проходит процесс обучения. В ходе занятия слушатели имеют возможность задать вопросы и получить знания по реальным практическим кейсам.
Heap, Heapsort и Heapqueue
Михаил Степанов
День открытых дверей
25 апреля в 20:00
После обучения вы

  • получите материалы по всем пройденным занятиям (видеозаписи вебинаров, выполненные домашние задания, выпускной проект)

  • сможете писать рациональный и хорошо структурированный код

  • получите сертификат об окончании курса

  • приобретёте навыки работы с алгоритмами и структурами данных, которые необходимы при реализации сложных проектов в крупных компаниях

  • получите приглашение пройти собеседование в компаниях-партнёрах (в случае успешного обучения)

Дата выдачи сертификата: 2 февраля 2020 года
Ваш сертификат
otus.ru
Константин Константинопольский
успешно закончил курс
«Алгоритмы для разработчиков»
Успешных заданий:
16 из 16
Проектная работа:
Распределённая система сетевого мониторинга
Виталий Чибриков
Генеральный директор
№ 0001
otus.ru
Константин Константинопольский
успешно закончил курс
«Алгоритмы для разработчиков»
Успешных заданий:
16 из 16
Проектная работа:
Распределённая система сетевого мониторинга
Виталий Чибриков
Генеральный директор
№ 0001
Партнеры ждут выпускников этого курса