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

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

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

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

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

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

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


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


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

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

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

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

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

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

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

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

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

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

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