+7 499 110-61-65

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

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

Подойдет ли мне этот курс?

Обучение сотрудников

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

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

Всё о курсе «Алгоритмы для разработчиков», 19 июля в 20:00

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

Ведет

Михаил
Степанов

Предыдущий день открытых дверей

Без алгоритмов и структур данных языки программирования мертвы. Это именно то, что вдыхает жизнь в Java, C++ и Python

Михаил Горшков

Преподаватель курса

Без алгоритмов и структур данных языки программирования мертвы. Это именно то, что вдыхает жизнь в Java, C++ и 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 часов на домашнюю работу.

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

Подробная программа PDF 239 kb

Программа обучения

Модуль 1

Введение в алгоритмы и структуры данных

Модуль 2

Сортировки

Модуль 3

Деревья

Модуль 4

Хеш-таблицы

Модуль 5

Графы

Модуль 6

Алгоритмы на строках

Модуль 7

Динамическое программирование

Модуль 8

Вероятностные алгоритмы и структуры данных

Модуль 9

Численные методы оптимизации

Модуль 10

Проектная работа

Подробная программа PDF 239 kb

Введение в алгоритмы и структуры данных

Тема 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 минут, после начала тестирования отложить тестирование не получится!

Пройти вступительное тестирование

После обучения вы