Полная программа
Курс «Алгоритмы и структуры данных»
Содержание курса
Курс состоит из двух разделов:
а) основы – уроки по 10-15-20 минут
б) продвинутый – уроки по 20-30 минут
а) основы – уроки по 10-15-20 минут
б) продвинутый – уроки по 20-30 минут
— Фундаментальные структуры данных и алгоритмы работы с ними
— Примерный состав стандартной библиотеки языков программирования
— Примерный состав стандартной библиотеки языков программирования
В результате обучения слушатель будет:
Процесс обучения
На каждом уроке будут рассмотрены необходимые теоретические вопросы и множество практических примеров. На каждом уроке будет получать практические задания для закрепления материала.
Знать:
— Применять их при разработке программ
Уметь:
Соответствует односеместровому университетскому курсу по алгоритмам и структурам данных.
Курс предназначен для джунов-программистов, которые стремятся дорасти до мидла.
--- Требования к квалификации ---
Знание элементарной школьной математики.
Знание основ программирования на одном из языков высокого уровня (желательно С++).
Знать, что такое массив, структура (запись).
Умение читать код, писать циклы.
Умение писать функции, в том числе рекурсивные.
--- Будет плюсом или двумя плюсами --- (если нет – объясню по ходу)
Знать, что такое класс, поле класса, метод класса. Уметь написать простой класс.
Знать, что такое указатель и уметь работать с динамической памятью.
Знакомство с шаблонами (template, generic)
Содержание курса соответствует односеместровому университетскому курсу по алгоритмам и структурам данных.
Курс состоит из двух разделов
а) основы – уроки по 10-15-20 минут
б) продвинутый – уроки по 20-30 минут
В результате обучения слушатель будет знать фундаментальные структуры данных и алгоритмы работы с ними, примерный состав стандартной библиотеки языков программирования, будет уметь применять их при разработке программ.
В процессе обучения на каждом уроке будут рассмотрены необходимые теоретические вопросы и множество практических примеров. На каждом уроке слушатель будет получать практические задания для закрепления материала.
а) основы – уроки по 10-15-20 минут
б) продвинутый – уроки по 20-30 минут
В результате обучения слушатель будет знать фундаментальные структуры данных и алгоритмы работы с ними, примерный состав стандартной библиотеки языков программирования, будет уметь применять их при разработке программ.
В процессе обучения на каждом уроке будут рассмотрены необходимые теоретические вопросы и множество практических примеров. На каждом уроке слушатель будет получать практические задания для закрепления материала.
Применение полученных знаний и умений.
Алгоритмы и структуры данных для программиста являются очень важными, и их, несомненно нужно знать. Тут, конечно, многое зависит от области разработки. Например, для написания интерфейса пользователя (типа простых веб-страниц с использованием html, css + языков типа javascript и сопутствующих фреймворков) знание алгоритмов и структур данных не является абсолютно необходимым. Или достаточно знать их на каком-то минимальном уровне.
Однако в большинстве случаев при разработке сложных систем и приложений требуются очень широкие знания структур данных и алгоритмов. Это игры, операционные системы, компиляторы, архиваторы и редакторы, шифрование данных, сетевые приложения, обработка данных и системы искусственного интеллекта. Для таких систем всегда нужно выбирать, какую структуру данных лучше использовать, какой алгоритм будет более эффективным.
Например, при разработке любого компилятора с любого языка обязательно реализуется таблица имен, которая обычно представляет собой либо балансированное дерево, либо хеш-таблицу. При разработке базы данных обязательно применяется B-деревья. Сортировки и поиск практически всегда используются в типовых задачах обработки данных. При разработке игры вроде шахмат требуется знать методы полного перебора и способы его сокращения (например, альфа-бета процедура). А без стека не работает ни одна программа вообще ни на одном компьютере.
Знание уже готовых вариантов решений для типовых задач, позволит не изобретать "велосипед", а применить подходящий из фремворка.
Однако в большинстве случаев при разработке сложных систем и приложений требуются очень широкие знания структур данных и алгоритмов. Это игры, операционные системы, компиляторы, архиваторы и редакторы, шифрование данных, сетевые приложения, обработка данных и системы искусственного интеллекта. Для таких систем всегда нужно выбирать, какую структуру данных лучше использовать, какой алгоритм будет более эффективным.
Например, при разработке любого компилятора с любого языка обязательно реализуется таблица имен, которая обычно представляет собой либо балансированное дерево, либо хеш-таблицу. При разработке базы данных обязательно применяется B-деревья. Сортировки и поиск практически всегда используются в типовых задачах обработки данных. При разработке игры вроде шахмат требуется знать методы полного перебора и способы его сокращения (например, альфа-бета процедура). А без стека не работает ни одна программа вообще ни на одном компьютере.
Знание уже готовых вариантов решений для типовых задач, позволит не изобретать "велосипед", а применить подходящий из фремворка.
Темы вебинаров
1. Обзор стандартной библиотеки С++20
2. Параллельные алгоритмы (общий обзор с реализацией на С++)
3. Алгоритмы на Python (общий обзор по первой части)
---------------------
Варианты:
- Алгоритмы на Javascript
- Алгоритмы на Java
- Алгоритмы на матрицах (часто бывает нужно студентам)
- Суффиксные деревья (многие задачи на строках, в том числе поиск)
- Приближенные алгоритмы
- Метод ветвей и границ (важно для ИИ)
- Списки с пропусками (линейная структура с логарифмическим временем поиска)
2. Параллельные алгоритмы (общий обзор с реализацией на С++)
3. Алгоритмы на Python (общий обзор по первой части)
---------------------
Варианты:
- Алгоритмы на Javascript
- Алгоритмы на Java
- Алгоритмы на матрицах (часто бывает нужно студентам)
- Суффиксные деревья (многие задачи на строках, в том числе поиск)
- Приближенные алгоритмы
- Метод ветвей и границ (важно для ИИ)
- Списки с пропусками (линейная структура с логарифмическим временем поиска)
Список уроков – базовый уровень
1
Введение. Производительность алгоритмов
1 урок
— Кто авторы курса, план курса.
— Определение алгоритма, примеры разных алгоритмов для решения одной задачи.
— Способы измерения времени выполнения алгоритмов (benchmarking).
— Теоретическая оценка производительности, О-нотация.
— Определение алгоритма, примеры разных алгоритмов для решения одной задачи.
— Способы измерения времени выполнения алгоритмов (benchmarking).
— Теоретическая оценка производительности, О-нотация.
Результат
Слушатель знает, зачем ему изучать алгоритмы и что его ждет на курсе, знает и понимает теоретические оценки производительности алгоритмов.
1 урок
Работа с числами
2
— Числовые алгоритмы: алгоритм Евклида, возведения в целую степень, проверка простоты, решето Эратосфена.
Слушатель знает и понимает схему работы данных алгоритмов, способен самостоятельно реализовать.
Результат
2 урока
Массивы
3
— Массивы. Указатели. Доступ к элементам. Линейный поиск. Двумерные массивы. Динамический массив.
Слушатель понимает устройство массива и списка, знает виды списков, способы доступа к элементам.
Результат
1 урок
Алгоритмы на массивах
4
— Бинарный поиск. Вставка и удаление элемента. Удаление нескольких элементов.
Слушатель понимает устройство массива и списка, разбирается в работе с элементами массивов.
Результат
2 урока
Списки. Стек, очередь, дек
5
— Понятие об АТД, интерфейсе. Односвязные, двусвязные списки. Основные операции. std::forward_list, std::list.
— Стек, очередь, дек. std::stack, std::queue, std::deque.
— Реализации на массиве. Реализация на списке. Применение.
— Стек, очередь, дек. std::stack, std::queue, std::deque.
— Реализации на массиве. Реализация на списке. Применение.
Слушатель знает типовые схемы циклов; понимает реализацию длинных целых чисел, знает, что такое АТД. Различает реализацию на массиве и на списке.
Результат
1 урок
Очередь с приоритетом
6
— Понятие о пирамиде (куче), построение пирамиды.
— Извлечение максимума, добавление элемента. std::priority_queue.
— Извлечение максимума, добавление элемента. std::priority_queue.
Слушатель знает понятие пирамиды (кучи), что такое АТД, извлекает максимум, работает с командами.
Результат
1 урок
Порядковые статистики
8
— Поиск медианы и порядковых статистик методом QuickSelect.
Слушатель умеет находить медиану и работать с помощью метода QuickSelect
Результат
2 урока
Сортировки
7
— Квадратичные сортировки. Сортировка слиянием. Быстрая сортировка. Пирамидальная сортировка. std::sort. Сортировка подсчетом.
Слушатель знает, что такое сортировки, понимает отличия реализаций на различных сортировках.
Результат
2 урока
Деревья
9
— Виды деревьев. Обходы в глубину и в ширину. Двоичные деревья поиска. Поиск, вставка, удаление, минимум/максимум. Необходимость балансировки. АВЛ-деревья. std::set, std::map.
Слушатель знает представление деревьев, двоичных деревьев, умеет реализовать обходы и другие алгоритмы.
Результат
2 урока
Хеш-таблицы
10
— Хеш-функции.
— Хеш-таблицы и ассоциативный доступ.
— Методы разрешения коллизий. std::unordered_set, std::unordered_map.
— Хеш-таблицы и ассоциативный доступ.
— Методы разрешения коллизий. std::unordered_set, std::unordered_map.
Слушатель понимает устройство хеш-таблиц, знает варианты разрешения коллизий.
Результат
2 урока
Жадные алгоритмы. Динамическое программирование
11
— Примеры жадных алгоритмов, их корректность.
—Задача о рюкзаке. Одномерная и двумерная динамика.
—Задача о рюкзаке. Одномерная и двумерная динамика.
Слушатель знает представление жадных алгоритмов, умеет решать задачи с помощью динамического программирования.
Результат
2 урока
Графы
12
— Виды графов. Представление графов. Связность. Обходы в глубину и в ширину. Сильная связность, конденсация. Поиск кратчайших путей, алгоритм Дейкстры.
Слушатель знает представление графов, умеет реализовать обходы графов, знает виды задач на графах.
Результат
2 урока
Строки
13
— Символы, кодировки, юникод.
— Поиск в строках – алгоритмы Рабина-Карпа и Кнута-Морриса-Пратта. Бор.
— Поиск в строках – алгоритмы Рабина-Карпа и Кнута-Морриса-Пратта. Бор.
Слушатель умеет реализовать алгоритмы работы со строками.
Результат
1 урок
Криптография
14
— CRC-коды, MD5, SHA.
Слушатель знает разные виды шифров и умеет реализовать алгоритмы шифрования и дешифрования.
Результат
1 урок
Длинные числа. Итоги
15
— Длинные числа.
— Обзор изученного материала. Литература и дополнительные материалы.
— Обзор изученного материала. Литература и дополнительные материалы.
Слушатель понимает, в каком направлении двигаться дальше.
Результат
Список уроков — продвинутый уровень
16
Сортировки
~ 2 - 3 урока
— Шелла, быстрая, поразрядная.
Результат
Слушатель понимает принципы и способен реализовать данные алгоритмы.
17
Строки
~ 2 - 4 урока
— Сложные алгоритмы поиска строк.
— Редакционное расстояние
— Редакционное расстояние
Результат
Сложные алгоритмы поиска строк Редакционное расстояние.
18
Деревья
~ 2 - 4 урока
— Балансированные деревья.
— В-деревья.
— В-деревья.
Результат
Слушатель знает устройство балансированных деревьев (в том числе RB-tree), понимает работу алгоритмов, может реализовать некоторые.
19
Графы
4 урока
— Остовные деревья, пути, раскраски…
— Интернет и графы
— Интернет и графы
Результат
Слушатель понимает схемы работы, умеет реализовать многие алгоритмы (в том числе жадные алгоритмы поиска остовного дерева).
20
Сжатие данных
2-3 урока
— Хаффмен, Лемпель-Зив
Результат
Слушатель знает схемы работы и умеет реализовать некоторые алгоритмы.
21
Динамическое программирование
— 1-2 типичные практические задачи (связь с графами)
Результат
Слушатель понимает принцип динамического программирования и знает схемы реализации задач ДП.
22
NP-трудные задачи
— Задача коммивояжера (связь с графами)
Результат
Слушатель понимает разницу между Р и NP, умеет реализовать алгоритмы полного перебора (исчерпывающего поиска).
1-2 урока
23
Эвристические алгоритмы ИИ
— Поиск в пространстве состояний, эвристические функции, сокращение перебора, генетические алгоритмы…
Результат
Слушатель понимает схемы работы эвристических алгоритмов, способен реализовать многие эвристические алгоритмы.
2-3 урока
24
Общие итоги
— Общий обзор изученного материала.
Результат
Слушатель понимает, в каком направлении двигаться дальше.
1 урок
Программы
Партнерам
О нас