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

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

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

5 месяцев

Начало

29 июля

Занятия

Пт 20:00, Пн 20:00

Общая стоимость

50 000 ₽

В месяц

12 500 ₽

В кредит:

12500 ₽ в месяц

Хочу дешевле
Общая стоимость
50 000 ₽
В месяц: 12 500 ₽
В кредит: 50000 ₽
в месяц
Продолжительность
5 месяцев, 4 академических часа в неделю
Пт 20:00, Пн 20:00
Начало занятий
29 июля
Что даст вам этот курс

Знание классических алгоритмов и структур данных — обязательное требование, которое предъявляют крупные 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 году по специальности «Учитель профессии»

«В детстве меня вдохновила "Занимательная ***" серия книг Я. И. Перельмана. Считаю своим призванием создать занимательную методику обучения программированию.»
Михаил работает в отделе машинного обучения компании 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 году по специальности «Учитель профессии»

«В детстве меня вдохновила "Занимательная ***" серия книг Я. И. Перельмана. Считаю своим призванием создать занимательную методику обучения программированию.»
Михаил Степанов
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: Введение в алгоритмы, RAM-модель. Порядок роста функций.
Студенты ознакомятся с эмулятором RAM-машины, поймут состав элементарных операций и научатся оценивать сложность алгоритмов.
29 июля, 20:00 — 21:30
Домашние задания: 1
1 Реализация алгоритма сортировки на RAM
1. Написать на RAM алгоритм деления двух натуральных чисел через вычитание.
На входе делимое и делитель.
На выходе частное и остаток.

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

3. Написать, сколько времени ушло на выполнение домашнего задания.
Тема 2: Базовые структуры данных: массив, динамический массив, список, стек, очередь, очередь с приоритетами
Студенты ознакомятся с реализацией базовых структур данных, и научатся правильно выбирать структуру данных под задачу
2 августа, 20:00 — 21:30
Домашние задания: 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 балл.

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

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

2. Написать программу выполнения корректного хода
для любой шахматной позиции по техническому заданию с тестами.
Тема 4: Алгебраические алгоритмы: алгоритм Евклида, быстрое возведение в степень, решето Эратосфена, быстрое вычисление чисел Фибоначчи
Студенты ознакомятся с использованием и реализацией некоторых популярных алгебраических алгоритмов.
9 августа, 20:00 — 21:30
Домашние задания: 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: Сортировка вставками, сортировка Шелла, сортировка выбором, пузырьковая сортировка
Студенты освоят алгоритмы сортировки вставками, выбором, пузырьком, сортировку Шелла. По окончании занятия студенты смогут реализовывать и правильно применять данные алгоритмы.
12 августа, 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.
16 августа, 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.
19 августа, 20:00 — 21:30
Домашние задания: 1
1 Реализовать quicksort или mergesort, дополнительно - усовершенствовать
Реализовать:

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

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

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

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

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

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

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

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

Вариант 2. Написать реализацию Декартово дерева.
Методы:
merge
split
add
remove
Тема 2: Красно-черные деревья, расширяющиеся деревья, рандомизированные деревья
Студенты освоят и смогут применять красно-черные деревья, расширяющиеся деревья и рандомизированные деревья
30 августа, 20:00 — 21:30
Домашние задания: 1
1 Реализация красно-чёрного дерева, вставки и поиска
Домашнее задание выполняется по желанию.

Вариант A. Реализовать рандомизированное дерево с операциями вставки, поиска и удаления.
Вариант B. Реализовать расширяющееся дерево с операциями вставки и поиска и удаления.
Вариант С. Реализовать красно-чёрное дерево с операциями вставки и поиска.
Сравнить производительность операций с AVL деревом.
Тема 3: B-деревья, B+-деревья. Деревья отрезков
Студенты освоят и смогут применять B-деревья и В+-деревья. Ознакомятся с деревьями отрезков.
2 сентября, 20:00 — 21:30
Домашние задания: 1
1 Реализовать оптимальное дерево поиска
Реализовать оптимальное дерево поиска
- Алгоритм 1
- Алгоритм 2

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Дедлайн 17.03.2019 включительно
Тема 3: Минимальные остовные деревья. Алгоритмы Крускала и Прима
Студенты освоят, смогут реализовывать и применять алгоритмы нахождения минимальных остовных деревьев.
23 сентября, 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: Поиск кратчайшего пути в графе. Алгоритмы Дейкстры, Беллмана-Форда, Флойда-Уоршалла
Студенты освоят, смогут реализовывать и применять алгоритмы поиска кратчайшего пути в графе.
27 сентября, 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 включительно
Тема 5: Алгоритмы Джонсона, А*, и способы решения задачи коммивояжера
Студенты освоят, смогут реализовывать и применять алгоритмы Джонсона, А* и ознакомятся со способами решения задачи коммивояжера.
30 сентября, 20:00 — 21:30
Домашние задания: 1
1 Предложить вариант алгоритма для решения задачи
Задача: Нужно быстро строить кратчайший маршрут на большие расстояния по реальной дорожной сети, например от Лиссабона до Владивостока. Можно взять данные OSM.

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

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

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


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

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

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

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

Прошедшие открытые вебинары по курсу
Открытый вебинар — это настоящее занятие в режиме он-лайн с преподавателем курса, которое позволяет посмотреть, как проходит процесс обучения. В ходе занятия слушатели имеют возможность задать вопросы и получить знания по реальным практическим кейсам.
Эффективность структур данных
Евгений Волосатов
День открытых дверей
15 июля в 20:00
Для доступа к прошедшим мероприятиям необходимо пройти входное тестирование
Возможность пройти вступительное тестирование повторно появится только через 2 недели
Результаты тестирования будут отправлены вам на e-mail, указанный при регистрации.
Тест рассчитан на 30 минут, после начала тестирования отложить тестирование не получится!
Пройти вступительное тестирование
После обучения вы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Лицензия на осуществление образовательной деятельности
№ 039825 от 28 декабря 2018г.
Общая стоимость
50 000 ₽
В месяц: 12 500 ₽
В кредит: ₽ в месяц
Продолжительность
5 месяцев
Начало занятий
29 июля