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

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

Курс о разработке и использовании разнообразных алгоритмов и структур данных
Начало занятий
В июне
Что даст вам этот курс

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

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

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

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

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


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

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

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

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


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

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

Без алгоритмов и структур данных языки программирования мертвы. Это именно то, что вдыхает жизнь в Java, C++ и Python
Михаил Горшков
Преподаватель курса
Без алгоритмов и структур данных языки программирования мертвы. Это именно то, что вдыхает жизнь в Java, C++ и Python
Михаил Горшков
Преподаватель курса
Преподаватели
Михаил Степанов
Jet Infosystems
Валерий Мазнев
СТО в Mobile Angels
Михаил работает в отделе машинного обучения компании Jet Infosystems. Занимается проектами по агрегации отзывов, по анализу и оптимизации производства крупных промышленных компаний. В data science пришел из промышленного программирования на Python, где разрабатывал код для "толстого клиента" в проекте по созданию "умных окон".
Ранее учил талантливых школьников программированию, машинному обучению и программированию учебных моделей спутников.

Область интересов: data science, математика, космос и Python.
Мой взгляд на программирование: с великой силой приходит великая ответственность.
Опытный инженер-программист, системный аналитик, руководитель IT-проектов. Общий бэкграунд в сфере информационных технологий превышает 30 лет. Программировал на многих языках, включая Java, JavaScript, C#, C/C++, Pascal, Delphi, Basic, SWIFT, PHP, HTML, SQL, Fortran, Assembler (IBM System 370).

Окончил Московский Авиационный Институт (МАИ) по специальности «Инженер-системотехник». Имеет обширные знания по архитектуре software и hardware, владеет методиками проектирования, разработки и тестирования ПО: от драйверов устройств до прикладных систем. Участвовал в реализации крупных IT-проектов, неоднократно выступал на отраслевых конференциях и семинарах. Имеет навыки преподавательской деятельности.
Преподаватели
Михаил Степанов
Jet Infosystems
Михаил работает в отделе машинного обучения компании Jet Infosystems. Занимается проектами по агрегации отзывов, по анализу и оптимизации производства крупных промышленных компаний. В data science пришел из промышленного программирования на Python, где разрабатывал код для "толстого клиента" в проекте по созданию "умных окон".
Ранее учил талантливых школьников программированию, машинному обучению и программированию учебных моделей спутников.

Область интересов: data science, математика, космос и Python.
Мой взгляд на программирование: с великой силой приходит великая ответственность.
Валерий Мазнев
СТО в Mobile Angels
Опытный инженер-программист, системный аналитик, руководитель IT-проектов. Общий бэкграунд в сфере информационных технологий превышает 30 лет. Программировал на многих языках, включая Java, JavaScript, C#, C/C++, Pascal, Delphi, Basic, SWIFT, PHP, HTML, SQL, Fortran, Assembler (IBM System 370).

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

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


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

для (каждого i от 0 до N-1)
для (каждого k от i+1 до N)
если(элемент[k] < элемент[i]) {
// поменять местами элемент[k] и элемент[i]
элемент_tmp = элемент[k];
элемент[k] = элемент[i];
элемент[i] = элемент_tmp;
}
Для реализации использовать заготовку из материалов к уроку в личном кабинете : "RAM - заготовка для сортировки"


Опционально (но очень желательно):

Доделать улучшение в алгоритм умножения через сложение
Доделать алгоритм деления с остатком через вычитание
Базовые структуры данных: массив, динамический массив, список, стек, очередь, очередь с приоритетами
Студенты ознакомятся с реализацией базовых структур данных, и научатся правильно выбирать структуру данных под задачу
Домашние задания: 1
1 Реализация очереди с приоритетом
Написать реализацию PQueue - очередь с приоритетом.
Варианты реализации - список списков, массив списков

Методы к реализации:
enqueue(int priority, T item) - поместить элемент в очередь
T dequeue() - выбрать элемент из очереди

Для реализации можно использовать только стандартный массив [], массив или список из материалов к занятию. Стандартные библиотеки не используем!


Опционально (но очень желательно):
Доделать алгоритм IArray - массив массивов с неполным заполнением. Делать на основе BArray - блочный массив вашей реализации, на основе приложенного к материалам DArray
А еще лучше сделать список массивов. Сами блоки (строки) это массивы, а вертикально они объединяются списком. Потому что что бы понять, в какой блок мы попали, все равно бежать перебором. Тоже брать только массив BArray и OList нашей реализации.

реализовать метод T get(int i) - взять элемент по индексу

Совсем опционально:
add(int index, T item) - добавить элемент в произвольное место массива
remove(index) - удалить произвольный элемент массива

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

Опционально
Алгоритм решета Эратосфена, экономичный к памяти, сразу откинуть четные числа
Варианты: битовые операции, сегментация

1) Битовые операции - храним как элемент массива целое число, например byte в Java 8 бита. Соответственно, каждый бит представляет собой true/false для определенного числа. Используя этот алгоритм можно уменьшить потребности в памяти в 8 раз. Откинув четные числа, еще в 2 раза.

2) Сегментация - делаем блоками по определенного размера. Выделяем блок фиксированного размера считаем в нем, например блок размером 1000, а посчитать надо до 5000. Соответственно сеем 5 блоков, не забывая, как у нас смещаются индексы.

Сроки сдачи: до 13.01.2019 включительно
Сортировки
Сортировка вставками, сортировка Шелла, сортировка выбором, пузырьковая сортировка
Студенты освоят алгоритмы сортировки вставками, выбором, пузырьком, сортировку Шелла. По окончании занятия студенты смогут реализовывать и правильно применять данные алгоритмы.
Домашние задания: 1
1 Реализовать Insertion Sort и Shell Sort
Реализовать алгоритмы insertion sort и Shell sort. Дополнительно: протестировать работу алгоритмов на случайных массивах и на практически упорядоченных массивах, сравнить производительность. Сравнить производительнсоть сортировки Шелла c разной последовательностью шагов.
Пирамидальная сортировка (heap sort), tree sort
Студенты смогут реализовывать и применять пирамидальную сортировку, tree sort.
Домашние задания: 1
1 Реализация heapsort
- Реализовать Drown - 1 балл
- Реализовать BuildHeap - 1 балл
- Реализовать алгоритм Heapsort - 1 балл
- Можно все inline и без отдельных процедур, тогда 3 балла, если все иделаьно работает
- Heapsort должен работать для получения зачета
- Дополнительно 1: реализовать Drown через стек, а не через рекурсию - 1 балл
- Дополнительно 2: реализовать удаление элемента с сохранением свойст пирамиды - 1 балл
- Дополнительно 3: реализовать очередь с приоритетами при помощи heap, сравнить с тем, что было ранее сделано - без баллов, по своему желанию (т.к. нам сложно гарантировать быструю проверку)
Сортировка слиянием, timsort. Быстрая сортировка
Студенты освоят и смогут реализовать алгоритмы быстрой сортировки, сортировки слиянием и timsort.
Домашние задания: 1
1 Реализовать quicksort или mergesort, дополнительно - усовершенствовать
Реализовать:

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

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

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

- делать оба алгоритма не обязательно, но при желании можно, баллы ставятся за лучший :
Сортировка подсчетом, поразрядная сортировка, блочная сортировка (bucket sort)
Студенты освоят и смогут реализовать сортировку подсчетом, поразрядную сортировку, блочную сортировку.
Домашние задания: 1
1 Сортировки за линейное время
Основное задание - 2 балла

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

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

- Сдать работу вовремя - 1 балл
- Реализовать Trie (с возможностью добавления и удаления элементов) - 1 балл
- Реализовать Trie-based Radix Sort - 1 балл
Внешняя сортировка, порядковые статистики
Студенты научатся реализовывать алгоритмы для нахождения медианы и порядковых статистик.

Будет также разобран (по заявкам) алгоритм внешней сортировки.
Домашние задания: 1
1 Реализовать Select, и, опционально, External Sorting
- Основное: реализовать Select: 3 балла максимум; 2 балла - если есть недочеты, влияющие на производительность, но элемент выбирается за $O(n)$
- Дополнительное:
- реализовать сортировку, использующую (возможно, искуственные - я понимаю, что она сортировка будет работать _долго_, и тестировать будет непросто, если сортировать несколько Gb) ограничения по памяти, любым из алгоритмов k-way merge (2 балла).
- Сравнить работоспособность сортировки для разного $K$ - 10, 20, 50, 100.. или другая подобная последовательность (1 балл)
Деревья
Двоичные деревья поиска, декартовы деревья, АВЛ-деревья
Студенты узнают, что такое дерево, двоичные дерево поиска и декартово дерево. Изучат структуры данных и алгоритмы, реализующие операции над ними.
Домашние задания: 1
1 Реализовать АВЛ дерево
Написать реализацию АВЛ-дерева

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

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

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

Сроки сдачи: до 24.02.2019 включительно
Красно-черные деревья, расширяющиеся деревья, рандомизированные деревья
Студенты освоят и смогут применять красно-черные деревья, расширяющиеся деревья и рандомизированные деревья
Домашние задания: 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-деревья и В+-деревья. Ознакомятся с деревьями отрезков.
Домашние задания: 1
1 Реализовать оптимальное дерево поиска
Реализовать оптимальное дерево поиска
- Алгоритм 1
- Алгоритм 2

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

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

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

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

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


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

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

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

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

Подглядеть
Адресация в хэш-таблицах
Михаил Степанов
Видеоматериалы по теме
День открытых дверей
19 декабря 2018 года в 20:00
После обучения вы

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

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

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

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

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

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