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

Курсы

Курсы в разработке Подготовительные курсы
Работа в компаниях Компаниям Блог +7 499 110-61-65

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

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

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

5 месяцев

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

В январе 2020 года

Продолжительность
5 месяцев, 4 академ. часа в неделю
Начало занятий
В январе 2020 года
Что даст вам этот курс

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

Поэтому для вас мы разработали уникальную авторскую программу от инженера-программиста из Лаборатории Касперского, которая поможет на профессиональном уровне:

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

Для кого этот курс?
Программа создана для Junior/Middle разработчиков, владеющих разными языками программирования. Откроет огромные перспективы для развития тем, кто застоялся на месте, и тем, кто хочет вырасти профессионально, избежав многих ошибок. И, конечно, курс просто жизненно необходим всем, кто прогулял или недостаточно серьёзно относился к занятиям по алгоритмам в вузе.


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

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

Примеры не на псевдокоде, а на одном из языков: С++, Python, Java

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

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

Присоединяйтесь, будет круто!

Опыт разработки программного обеспечения с 1990 года. Работал и с привычными ныне dos, windows и linux системами, и с редко встречающимися специализированными вычислительными устройствами (системами реального времени, ibm i). Профессионально использую C++, С#, assembler, java, RPG.

Закончил МАИ, к.т.н., старший преподаватель, кафедра «Робототехнические и интеллектуальные системы».
Участвовал в проектах разработки программного обеспечения, связанного с навигацией. Решал задачи для процессоров цифровой обработки сигналов в операционных системах реального времени включая параллельную обработку данных.
Разработал и вёл курс вероятностных конечных автоматов.

В 2000-2002г самостоятельно разработал, используя C++ и Dephi, биллинговый комплекс АСР «ИнтБиллинг» (оборудование VocalTec). Сертификат № ОС/1-СТ-219 Министерства Российской Федерации по связи и информатизации. Биллинг выставлялся на СвязьЭкспоком, имел инсталляции заказчиков.

Долгое время работал с Java2EE (back-end и front-end). Сначала в первом агрегаторе контента для сотовых устройств "Никита-мобайл". Затем в компании "Микротест" занимался разработкой и реализацией систем информирования пользователя, основанных на web интерфейсе и являющихся частью больших распределённых систем, таких как биллинговые системы (Oracle BRM), CRM (Oracle Siebel), интеграционные шины (Tibco), SMS шлюзы.
С 2016 года - архитектор направления Equation на ibm i в одном из крупнейших банков страны.

Люблю и умею преподавать. Более 20 лет помимо программирования изучаю и обучаю айкидо (5й дан Айкикай).

Подобно технике боевых искусств мы изучаем базис: языки, паттерны, платформы. Чтобы затем перевести это всё в зодчество ПО, его архитектуру. С другой стороны, программный продукт всегда есть отражение создателя. Любая система, согласно закону Конвея, есть отражение людей, создавших её. Программирование суть искусство в мире электронных форм. Взрослый ничем не отличается от маленького ребенка, играющего с кубиками. Только кубики другие. Творчество это основа всего. И свобода ошибаться и искать. Обучение это игра и освоение новых миров.

Профессиональный программист. Преподаватель языка 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 году по специальности «Учитель профессии»

«В детстве меня вдохновила "Занимательная ***" серия книг Я. И. Перельмана. Считаю своим призванием создать занимательную методику обучения программированию.»

Окончил Волгоградский государственный технический университет по специальности «Автоматизированные системы обработки информации и управления». Увлёкся программированием ещё в студенческие годы (в 2010 году) и остановиться так и не смог. В коммерческой разработке с 2012 года.
Работал с проектами разного масштаба, прошёл путь от Junior до Senior. С 2016 года — старший инженер-программист в EPAM Systems, с 2018 по май 2019 — технический руководитель по разработке софта в Skywind Group.
Участвовал в международном проекте компании Ericsson, занимался web-программированием и собственными проектами.
Является специалистом по архитектуре веб-приложений, хорошо знает JS/NodeJS, Mongo, MySQL, фреймворки Express, Koa2, React, AngularJS. Уверен, что в программировании всё приходит с практикой.

Один из разработчиков academy.cppstudio.com - бесплатного интерактивного сервиса по обучению С++. Свыше 5 лет опыта разработки приложений на C++ и C#.
Используемые технологии и фрэймворки:
WPF, WinForms, EF6, ASP.NET MVC5, ASP.NET Core 2.

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

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

Область интересов: data science, математика, космос и Python.
Мой взгляд на программирование: с великой силой приходит великая ответственность.



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

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

Присоединяйтесь, будет круто!

Матвей Калинин
Опыт разработки программного обеспечения с 1990 года. Работал и с привычными ныне dos, windows и linux системами, и с редко встречающимися специализированными вычислительными устройствами (системами реального времени, ibm i). Профессионально использую C++, С#, assembler, java, RPG.

Закончил МАИ, к.т.н., старший преподаватель, кафедра «Робототехнические и интеллектуальные системы».
Участвовал в проектах разработки программного обеспечения, связанного с навигацией. Решал задачи для процессоров цифровой обработки сигналов в операционных системах реального времени включая параллельную обработку данных.
Разработал и вёл курс вероятностных конечных автоматов.

В 2000-2002г самостоятельно разработал, используя C++ и Dephi, биллинговый комплекс АСР «ИнтБиллинг» (оборудование VocalTec). Сертификат № ОС/1-СТ-219 Министерства Российской Федерации по связи и информатизации. Биллинг выставлялся на СвязьЭкспоком, имел инсталляции заказчиков.

Долгое время работал с Java2EE (back-end и front-end). Сначала в первом агрегаторе контента для сотовых устройств "Никита-мобайл". Затем в компании "Микротест" занимался разработкой и реализацией систем информирования пользователя, основанных на web интерфейсе и являющихся частью больших распределённых систем, таких как биллинговые системы (Oracle BRM), CRM (Oracle Siebel), интеграционные шины (Tibco), SMS шлюзы.
С 2016 года - архитектор направления Equation на ibm i в одном из крупнейших банков страны.

Люблю и умею преподавать. Более 20 лет помимо программирования изучаю и обучаю айкидо (5й дан Айкикай).

Подобно технике боевых искусств мы изучаем базис: языки, паттерны, платформы. Чтобы затем перевести это всё в зодчество ПО, его архитектуру. С другой стороны, программный продукт всегда есть отражение создателя. Любая система, согласно закону Конвея, есть отражение людей, создавших её. Программирование суть искусство в мире электронных форм. Взрослый ничем не отличается от маленького ребенка, играющего с кубиками. Только кубики другие. Творчество это основа всего. И свобода ошибаться и искать. Обучение это игра и освоение новых миров.

Евгений Волосатов
Профессиональный программист. Преподаватель языка 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 году по специальности «Учитель профессии»

«В детстве меня вдохновила "Занимательная ***" серия книг Я. И. Перельмана. Считаю своим призванием создать занимательную методику обучения программированию.»

Никита Овчинников
Окончил Волгоградский государственный технический университет по специальности «Автоматизированные системы обработки информации и управления». Увлёкся программированием ещё в студенческие годы (в 2010 году) и остановиться так и не смог. В коммерческой разработке с 2012 года.
Работал с проектами разного масштаба, прошёл путь от Junior до Senior. С 2016 года — старший инженер-программист в EPAM Systems, с 2018 по май 2019 — технический руководитель по разработке софта в Skywind Group.
Участвовал в международном проекте компании Ericsson, занимался web-программированием и собственными проектами.
Является специалистом по архитектуре веб-приложений, хорошо знает JS/NodeJS, Mongo, MySQL, фреймворки Express, Koa2, React, AngularJS. Уверен, что в программировании всё приходит с практикой.

Андрей Иванов
Один из разработчиков academy.cppstudio.com - бесплатного интерактивного сервиса по обучению С++. Свыше 5 лет опыта разработки приложений на C++ и C#.
Используемые технологии и фрэймворки:
WPF, WinForms, EF6, ASP.NET MVC5, ASP.NET Core 2.

Михаил Степанов
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
Проектная работа
Введение в алгоритмы и структуры данных
Тема 1: Математика для разработчиков
освежить основные разделы математики, использующиеся в курсе "алгоритмы для разработчиков"
Тема 2: Введение в алгоритмы, RAM-модель. Порядок роста функций.
Студенты ознакомятся с эмулятором RAM-машины, поймут состав элементарных операций и научатся оценивать сложность алгоритмов.
Домашние задания: 1
1 Реализация алгоритма сортировки на RAM
Цель: 1. Написать на RAM алгоритм умножения двух целых неотрицательных чисел через сложение 2. Написать на RAM алгоритм деления двух целых неотрицательных чисел через вычитание 3. Написать на RAM алгоритм простой сортировки
Тема 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 балл.

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

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

ВАЖНО! При размещении ответа укажите, на каком языке вы выполнили ДЗ. Это поможет нам ускорить его проверку.
Тема 4: Алгебраические алгоритмы: алгоритм Евклида, быстрое возведение в степень, решето Эратосфена, быстрое вычисление чисел Фибоначчи
Студенты ознакомятся с использованием и реализацией некоторых популярных алгебраических алгоритмов.
12 ноября, 20:00 — 21:30
Лектор: Евгений Волосатов
Домашние задания: 1
1 Вычисление чисел Фибоначчи
Написать следующие алгоритмы и сравнить их быстродействие.
Приложить скриншоты/ссылки на результаты экспериментов.

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

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

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

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

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

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

ВАЖНО! При размещении ответа укажите, на каком языке вы выполнили ДЗ. Это поможет нам ускорить его проверку.
Тема 5: Шахматное программирование
Студенты повторят все правила игры в шахматы, получат техническое задание по их кодированию.
14 ноября, 20:00 — 21:30
Лектор: Евгений Волосатов
Домашние задания: 1
1 Битый конь и FEN-ходы
Решить столько задач, сколько получится в порядке их расположения.
Самостоятельно проверить корректность алгоритмов по приложенным тестам.
После каждых 4 задач написать в ЧАТ сообщение со ссылкой на репозиторий.
Написать, сколько времени ушло на выполнение.

ВАЖНО! При размещении ответа укажите, на каком языке вы выполнили ДЗ. Это поможет нам ускорить его проверку.
Сортировки
Тема 1: Сортировка вставками, сортировка Шелла, сортировка выбором, пузырьковая сортировка
Студенты освоят алгоритмы сортировки вставками, выбором, пузырьком, сортировку Шелла. По окончании занятия студенты смогут реализовывать и правильно применять данные алгоритмы.
19 ноября, 20:00 — 21:30
Лектор: Евгений Волосатов
Домашние задания: 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

ВАЖНО! При размещении ответа укажите, на каком языке вы выполнили ДЗ. Это поможет нам ускорить его проверку.
Тема 2: Пирамидальная сортировка (heap sort), tree sort
Студенты смогут реализовывать и применять пирамидальную сортировку, tree sort.
21 ноября, 20:00 — 21:30
Лектор: Евгений Волосатов
Домашние задания: 1
1 Реализация heapsort
- Реализовать Drown - 1 балл
- Реализовать BuildHeap - 1 балл
- Реализовать алгоритм Heapsort - 1 балл
- Можно все inline и без отдельных процедур, тогда 3 балла, если все иделаьно работает
- Heapsort должен работать для получения зачета
- Дополнительно 1: реализовать итеративно, а не через рекурсию - 1 балл
- Дополнительно 2: реализовать удаление элемента с сохранением свойст пирамиды - 1 балл
- Дополнительно 3: реализовать очередь с приоритетами при помощи heap, сравнить с тем, что было ранее сделано - без баллов, по своему желанию (т.к. нам сложно гарантировать быструю проверку)

ВАЖНО! При размещении ответа укажите, на каком языке вы выполнили ДЗ. Это поможет нам ускорить его проверку.
Тема 3: Сортировка слиянием, timsort. Быстрая сортировка
Студенты освоят и смогут реализовать алгоритмы быстрой сортировки, сортировки слиянием и timsort.
26 ноября, 20:00 — 21:30
Лектор: Евгений Волосатов
Домашние задания: 1
1 Реализовать quicksort или mergesort, дополнительно - усовершенствовать
Реализовать:

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

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

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

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


** ТЕСТИРОВАНИЕ QUICKSORT **
Массивы для тестирования Quicksirt: тестируйте алгоритм так, как объяснено в конце занятия; при этом тестируйте на "случайно" неупорядоченных массивах и отдельно на массивах с упорядоченными данными, которые будут "ломать" Partition и приводить к квадратичному времени работы алгоритма.

ВАЖНО! При размещении ответа укажите, на каком языке вы выполнили ДЗ. Это поможет нам ускорить его проверку.
Тема 4: Сортировка за линейное время. Поиск порядковых статистик за линейное время.
Студенты освоят и смогут реализовать сортировку подсчетом, поразрядную сортировку, блочную сортировку.

Будет разобран научатся алгоритм для нахождения порядковых статистик за линейное время.
28 ноября, 20:00 — 21:30
Лектор: Евгений Волосатов
Деревья
Тема 1: Двоичные деревья поиска, декартовы деревья, АВЛ-деревья
Студенты узнают, что такое дерево, двоичные дерево поиска и декартово дерево. Изучат структуры данных и алгоритмы, реализующие операции над ними.
3 декабря, 20:00 — 21:30
Лектор: Евгений Волосатов
Домашние задания: 1
1 Реализовать АВЛ или Декартово дерево
Вариант 1. Написать реализацию АВЛ-дерева
Методы к реализации:
smallLeft/RightRotation - малое левое/правое вращение
bigLeft/RightRotation - большое левое/правое вращение, написать через вызов малых вращений
insert
remove
rebalance

Вариант 2. Написать реализацию Декартово дерева.
Методы:
merge
split
add
remove

ВАЖНО! При размещении ответа укажите, на каком языке вы выполнили ДЗ. Это поможет нам ускорить его проверку.
Тема 2: Красно-черные деревья, расширяющиеся деревья, рандомизированные деревья
Студенты освоят и смогут применять красно-черные деревья, расширяющиеся деревья и рандомизированные деревья
5 декабря, 20:00 — 21:30
Лектор: Евгений Волосатов
Домашние задания: 1
1 Реализация красно-чёрного дерева, вставки и поиска
Домашнее задание выполняется по желанию.

Вариант A. Реализовать рандомизированное дерево с операциями вставки, поиска и удаления.
Вариант B. Реализовать расширяющееся дерево с операциями вставки и поиска и удаления.
Вариант С. Реализовать красно-чёрное дерево с операциями вставки и поиска.
Сравнить производительность операций с AVL деревом.

ВАЖНО! При размещении ответа укажите, на каком языке вы выполнили ДЗ. Это поможет нам ускорить его проверку.
Тема 3: B-деревья, B+-деревья. Деревья отрезков
Студенты освоят и смогут применять B-деревья и В+-деревья. Ознакомятся с деревьями отрезков.
10 декабря, 20:00 — 21:30
Лектор: Евгений Волосатов
Домашние задания: 1
1 Реализовать оптимальное дерево поиска
Реализовать оптимальное дерево поиска
- Алгоритм 1
- Алгоритм 2

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

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

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

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

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

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

2. _Или_: реализовать хеш-таблицу с открытой адресацией
- дополнительно: реализовать "ленивое" удаление
- реализовать квадратичный пробинг

ВАЖНО! При размещении ответа укажите, на каком языке вы выполнили ДЗ. Это поможет нам ускорить его проверку.
Тема 2: Хеш-функции. Стратегии поиска. Универсальное хеширование
Студенты смогут реализовывать хэш-таблицы с открытой адресацией. Будут рассмотрены различные стратегии поиска, универсальное хеширование, различные хеш-функции.
17 декабря, 20:00 — 21:30
Лектор: Никита Овчинников
Домашние задания: 1
1 Домашнего задания нет
Домашнего задания нет
Тема 3: Универсальное и идеальное хэширование.
Будет рассмотрено универсальное и идеальное хеширование, области их применения.
19 декабря, 20:00 — 21:30
Лектор: Никита Овчинников
Домашние задания: 1
1 Домашнего задания нет
Домашнего задания нет
Графы
Тема 1: Поиск в ширину. Поиск в глубину, поиск компонент сильной связности. Алгоритм Косарайю.
Студенты освоят, смогут реализовывать и применять поиск в ширину и поиск в глубину. Будут разобраны алгоритмы поиска компонент сильной связности.
24 декабря, 20:00 — 21:30
Лектор: Евгений Волосатов
Домашние задания: 1
1 Реализовать алгоритм Косарайю
Реализовать алгоритм Косарайю

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

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

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

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

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

ВАЖНО! При размещении ответа укажите, на каком языке вы выполнили ДЗ. Это поможет нам ускорить его проверку.
Тема 2: Топологическая сортировка
Студенты освоят, смогут реализовывать и применять топологическую сортировку.
26 декабря, 20:00 — 21:30
Лектор: Евгений Волосатов
Домашние задания: 1
1 Алгоритм Демукрона
Реализовать алгоритм Демукрона

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

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

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

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

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

ВАЖНО! При размещении ответа укажите, на каком языке вы выполнили ДЗ. Это поможет нам ускорить его проверку.
Тема 3: Минимальные остовные деревья. Алгоритмы Крускала и Прима
Студенты освоят, смогут реализовывать и применять алгоритмы нахождения минимальных остовных деревьев.
9 января, 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
Реализовать алгоритм Борувки

ВАЖНО! При размещении ответа укажите, на каком языке вы выполнили ДЗ. Это поможет нам ускорить его проверку.
Тема 4: Поиск кратчайшего пути в графе. Алгоритмы Дейкстры, Беллмана-Форда, Флойда-Уоршалла
Студенты освоят, смогут реализовывать и применять алгоритмы поиска кратчайшего пути в графе.
14 января, 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
Реализовать алгоритм Флойда-Уоршалла или Беллама-Форда на выбор

ВАЖНО! При размещении ответа укажите, на каком языке вы выполнили ДЗ. Это поможет нам ускорить его проверку.
Тема 5: Алгоритмы Джонсона, А*, и способы решения задачи коммивояжера
Студенты освоят, смогут реализовывать и применять алгоритмы Джонсона, А* и ознакомятся со способами решения задачи коммивояжера.
16 января, 20:00 — 21:30
Лектор: Никита Овчинников
Домашние задания: 1
1 Предложить вариант алгоритма для решения задачи
Задача: Нужно быстро строить кратчайший маршрут на большие расстояния по реальной дорожной сети, например от Лиссабона до Владивостока. Можно взять данные OSM.

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

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

Дополнительное задание 1: Закодить алгоритм A*
Дополнительное задание 2: Закодить алгоритм Джонсона

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


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

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

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

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

Прошедшие открытые вебинары по курсу
Открытый вебинар — это настоящее занятие в режиме он-лайн с преподавателем курса, которое позволяет посмотреть, как проходит процесс обучения. В ходе занятия слушатели имеют возможность задать вопросы и получить знания по реальным практическим кейсам.
Заповедники двоичных деревьев поиска.
Евгений Волосатов
Эффективность структур данных
Евгений Волосатов
После обучения вы

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

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

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

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

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

Дата выдачи сертификата: 21 июля 2020 года
Ваш сертификат

онлайн-образование

Сертификат №0001

Константин Константинопольский

Успешно закончил курс «Алгоритмы для разработчиков»
Выполнено практических заданий: 16 из 16

Общество с ограниченной ответственностью “Отус Онлайн-Образование”

Город:
Москва

Генеральный директор ООО “Отус Онлайн-Образование”
Виталий Чибриков

Лицензия на осуществление образовательной деятельности
№ 039825 от 28 декабря 2018г.

онлайн-образование

Сертификат №0001

Константин Константинопольский

Успешно закончил курс «Алгоритмы для разработчиков»
Выполнено практических заданий: 16 из 16

Общество с ограниченной ответственностью “Отус Онлайн-Образование”

Город:
Москва

Генеральный директор ООО “Отус Онлайн-Образование”
Виталий Чибриков

Лицензия на осуществление образовательной деятельности
№ 039825 от 28 декабря 2018г.