Лекции школы анализа данных яндекса книги
Обновлено: 02.07.2024
Поступить и учиться в ШАД от Яндекс – мечта многих начинающих специалистов по Data Science. Рассказываем, как это можно сделать, пройдя пять простых шагов.
Набор проходит в три этапа:
- Онлайн-тестирование: решение заданий теста за 5 часов;
- Для поступающих в московское отделение второй этап состоит из двух частей: первая – математика и алгоритмы, вторая – программирование и основы анализа данных;
- Заключительный этап – очное собеседование, во время которого придется решать задачи по математике, алгоритмам и программированию.
Шаг 1: Выясните, каких знаний вам не хватает
При поступлении в ШАД проверяются знания по общей программе , включающей базовые разделы высшей алгебры, математического анализа, комбинаторики, теории вероятностей, а также основы программирования и анализа данных. Оцените свои знания и начните интенсивную подготовку с практикой по темам, в которых вы еще не сильны. Для упрощения этой задачи в статье мы собрали все необходимые темы и ресурсы для их изучения.
Шаг 2: Математическая подготовка
Алгeбра
- Определение, четность, произведение подстановок. Разложение подстановок в произведение транспозиций и независимых циклов.
- Комплексные числа. Геометрическое изображение, алгебраическая и тригонометрическая форма записи, извлечение корней, корни из единицы.
- Системы линейных уравнений. Прямоугольные матрицы. Приведение матриц и систем линейных уравнений к ступенчатому виду. Метод Гаусса.
- Линейная зависимость и ранг. Линейная зависимость строк (столбцов). Основная лемма о линейной зависимости, базис и ранг системы строк (столбцов). Ранг матрицы. Критерий совместности и определенности системы линейных уравнений в терминах рангов матриц. Фундаментальная система решений однородной системы линейных уравнений.
- Определитель квадратной матрицы, его основные свойства. Критерий равенства определителя нулю. Формула разложения определителя матрицы по строке (столбцу).
- Операции над матрицами и их свойства. Теорема о ранге произведения двух матриц. Определитель произведения квадратных матриц. Обратная матрица, ее явный вид (формула), способ выражения с помощью элементарных преобразований строк.
- Векторное пространство, его базис и размерность. Преобразования координат в векторном пространстве. Подпространства как множества решений систем однородных линейных уравнений. Связь между размерностями суммы и пересечения двух подпространств. Линейная независимость подпространств. Базис и размерность прямой суммы подпространств.
- Линейные отображения, их запись в координатах. Образ и ядро линейного отображения, связь между их размерностями. Сопряженное пространство и сопряженные базисы. Изменение матрицы линейного оператора при переходе к другому базису.
- Билинейные функции, их запись в координатах. Изменение матрицы билинейной функции при переходе к другому базису. Ортогональное дополнение к подпространству относительно симметрической билинейной функции. Связь между симметричными билинейными и квадратичными функциями. Существование ортогонального базиса для симметрической билинейной функции. Нормальный вид вещественной квадратичной функции. Закон инерции.
- Евклидовы пространства. Неравенство Коши-Буняковского. Ортогональные базисы. Ортогонализация Грама-Шмидта. Ортогональные операторы.
- Собственные векторы и собственные значения линейного оператора. Собственные подпространства линейного оператора, их линейная независимость. Условие диагонализируемости оператора.
Математически анализ
- Пределы и непрерывность. Пределы последовательностей и функций. Непрерывные функции.
- Ряды. Числовые и функциональные ряды. Признаки сходимости (Даламбера, Коши, интегральный, Лейбница). Абсолютно и условно сходящиеся ряды.
- Дифференцирование. Дифференцирование функций. Применение производной для нахождения экстремумов функций. Формула Тейлора.
- Функции многих переменных. Частные производные. Градиент и его геометрический смысл. Гессиан. Метод градиентного спуска. Поиск экстремумов функций от многих переменных.
- Интегрирование. Определенный и неопределенный интегралы. Методы интегрирования функций. Первообразные различных элементарных функций. Кратные интегралы (двойные, тройные), замена координат, связь с повторными.
- Элементы функционального анализа: нормированные, метрические пространства, непрерывность, ограниченность.
Комбинаторика
- Основные правила комбинаторики. Правило подсчета количества комбинаторных объектов. Принцип Дирихле. Примеры.
- Множества. Круги Эйлера, операции на множествах. Формула включений и исключений. Примеры.
- Сочетания. Размещения, перестановки и сочетания. Бином Ньютона. Треугольник Паскаля. Сочетания с повторениями.
Теория вероятностей
- Основные понятия теории вероятностей. Определение вероятностного пространства, простейшие дискретные случаи (выборки с порядком и без него, упорядоченные и неупорядоченные), классическая вероятностная модель. Случайная величина, функция распределения.
- Условные вероятности. Определение условной вероятности, формула полной вероятности, формула Байеса.
- Математическое ожидание, дисперсия, корреляция. Определение математического ожидания, дисперсии, ковариации и корреляции, их свойства.
- Независимость событий. Попарная независимость и независимость в совокупности.
- Основные теоремы теории вероятностей. Неравенство Чебышева. Закон больших чисел. Центральная предельная теорема.
- Распределения. Стандартные дискретные и непрерывные распределения, их математические ожидания, дисперсии и свойства: биномиальное; равномерное; нормальное; пуассоновское; показательное; геометрическое.
Шаг 3: Программирование
- Простейшие конструкции языка программирования. Циклы, ветвления, рекурсия.
- Анализ алгоритмов. Понятие о сложности по времени и по памяти. Асимптотика, O-символика. Инварианты, пред- и пост- условия. Доказательство корректности алгоритмов.
- Простейшие структуры данных. Массивы, стеки, очереди, связные списки, Сравнение временных затрат при различных типах операций.
- Строки и операции над ними. Представление строк. Вычисление длины, конкатенация.
- Сортировки. Нижняя теоретико-информационная оценка сложности задачи сортировки. Алгоритмы сортировки вставками, пузырьком, быстрая сортировка, сортировка слиянием. Оценка сложности.
- Указатели.Указатели и динамическое управление памятью.
Курсы для подготовки:
Шаг 4: Анализ данных
Крайне важно понимать, как подготовить базу данных для получения желаемых результатов без потери информации. Далее специалист по Data Science с помощью различных инструментов, методов, методологий и алгоритмов анализирует и оптимизирует информацию для создания эффективных бизнес стратегий.
- Основные машинного обучения: классификация, регрессия, ранжирование, кластеризация. Обучение с учителем и без учителя.
- Предобработка и очистка данных. Работа с пропущенными значениями.
- Feature Engineering. Работа с категориальными признаками.
- Переобучение: как его обнаружить и как с ним бороться. Разделение на обучающую и тестовую выборки. Методы регуляризации.
- Сравнение моделей. Метрики в задачах классификации и регрессии. Методология подборара гиперпараметров.
- Основные модели классификации и регрессии: линейные модели, решающие деревья. Ансамбли алгоритмов.
Курсы для подготовки:
Шаг 5: Практика
После изучения необходимых тем, переходите к практическим занятиям. Это лучший способ закрепить полученные знания и подготовится к интервью, во время которого вам предстоит решать задачи в режиме реального времени.
Примеры упражнений:
В этом курсе рассматриваются базовые алгоритмы и структуры данных, включая хешировани, сложность и модели вычислений, деревья поиска, B-деревья, задачи геометрического поиска, динамическую связность в графах и другое.
Лекции читает Максим Александрович Бабенко, заместитель директора отделения computer science, ассистент кафедры математической логики и теории алгоритмов механико-математического факультета МГУ им. М. В. Ломоносова, кандидат физико-математических наук.
Полный курс в виде папки на Яндекс.Диске
Лекция 1. Сложность и модели вычислений. Анализ учетных стоимостей (начало)
Основные ресурсы: память и время. О-символика. Примеры моделей вычисления: машина Тьюринга, RAM-машина. Сложность в среднем и худшем случаях. Пример: задача сортировки. Сортировка выбором. Теоретико-информационная нижняя оценка сложности. Разрешающие деревья. Нижняя оценка сложности в модели разрешающих деревьев. Массивы переменного размера: аддитивная и мультипликативная схемы реаллокации. Анализ мультипликативной схемы для массива переменного размера с помощью банковского метода.
Лекция 2. Анализ учетных стоимостей (окончание)
Анализ учетных стоимостей операций: функция потенциала, истинные и учетные стоимости. Стеки и очереди. Реализация на основе массива переменного размера и на основе связанного списка. Моделирование очереди с помощью двух стеков. Задача о поддержании динамического максимума в стеке и очереди. Изменяемые (mutable) и неизменяемые (immutable) структуры данных. Структуры данных с хранением истории (persistent). Immutable-стек и immutable-очередь. Проблема множественного будущего при анализе учетных стоимостей в persistent-структурах.
Лекция 3. Функции быстрой сортировки и сортировки слиянием
Лекция 4. Порядковые статистики. Кучи (начало)
Нахождение порядковых статистик с помощью рандомизированной модификации алгоритма Quick-Sort. Линейность матожидания времени работы. Приближенные медианы. Выбор k-й порядковой статистики за линейное в худшем случае. Деревья со свойствами кучи. Почти полные бинарные деревья: нумерация вершин, навигация. Двоичная куча. Операция просеивания вниз и вверх. Реализация операций вставки, удаления и поиска минимума. Преобразование произвольного массива ключей в кучу (операция Make-Heap), линейность времени работы. Алгоритм сортировки Heap-Sort.
Лекция 5. Кучи (начало). Хэширование (начало)
k-ичные кучи, зависимость сложности операций от выбора k. Биномиальные (binomial), левацкие (leftlist) и косые (skew) кучи.
Лекция 6. Хэширование
Хеш-функции. Коллизии. Разрешение коллизий методом цепочек, методом последовательных проб и методом двойного хеширования. Гипотеза простого равномерного хеширования, оценка средней длины цепочки. Универсальные семейства хеш-функций, оценка средней длины цепочки. Построение универсального семейства для целочисленных ключей. Совершенные хеш-функции. Построение совершенной хеш-функции с помощью универсального семейства. Интерфейс множества с ошибками. Фильтр Блюма (Bloom filter). Оценка вероятности ложноположительного срабатывания. Интерфейс словаря с ошибками. Модификация фильтра Блюма (bloomier filter).
Лекция 7. Деревья поиска (начало)
Определение дерева поиска. Вставка и удаление элементов. Inorder-обход дерева. Красно черные деревья: определение и основные свойства. Реализация операций вставки для красно-черного дерева. Splay-деревья. Операция splay: zig, zig-zig и zig-zag шаги. Реализация операций вставки, удаления, слияния и разделения для splay-деревьев.
Лекция 8. Деревья поиска (окончание). Декартовы деревья
Декартовы деревья (дучи). Единственность декартова дерева для заданного набора различных ключей и приоритетов. Логарифмическая оценка матожидания высоты дучи.Операции слияния и разделения для дуч. Операции вставки и удаления элементов для дуч. Построение декартового дерева за линейное время при условии предварительной сортировки ключей.
Лекция 9. B-деревья. Система непересекающихся множеств
B+ деревья: определения и основные свойства. Операции поиска, вставки и удаления для B+ деревьев. Системы непересекающихся множеств. Реализация с использованием леса. Ранги вершин, эвристика ранга. Логарифмическая оценка ранга через количество элементов. Рандомизированная ранговая эвристика. Эвристика сжатия путей. Оценка учетной стоимости операций (без доказательства).
Лекция 10. Задачи RMQ и LCA
Лекция 11. Задачи геометрического поиска
Location problem, stabbing problem. Деревья интервалов. Сведение системы интервалов к двумерной задаче. Задача поиска точек в коридоре. Priority search tree. Задача поиска точек в прямоугольнике. Дерево отрезков по координате X, упорядоченные по Y списки точек в каждой вершине. Сложность O(n log n) для построения и O(log^2 n) для запроса. Уменьшение времени поиска до O(log n). Задача одновременного поиска в наборе упорядоченных списков. Fractional cascading.
Лекция 12. Динамическая связность в графах
Задача о динамической связности: вставки и удаления ребер, запросы о связности. Частный случай задачи для случая лесов. Деревья эйлеровых обходов: слияние и разделение. Использование амортизации и набора остовных лесов для решения со сложностью O(log^2 n).
( 0 из 5 ) [ 0 оценок]
В курсе дается краткое изложение классических способов построения и анализа алгоритмов. Первая часть.
6 марта 1874 года родился Николай Александрович Бердяев, философ, публицист (умер в 1948 году).
Недавно стартовал весенний семестр обучения в Школе анализа данных. Наши студенты начали осваивать новые предметы, делать домашние задания, посещать лекции и семинары.
В этом семестре мы решили опубликовать видеозаписи лекций некоторых курсов, и теперь все желающие могут посмотреть их здесь. Все лекции будут появляться на сайте через несколько дней после того, как их прочитали на занятиях в ШАД.
Конечно, полноценного обучения видеолекции не заменят. Во-первых, выкладываться будут лекции не всех курсов, во-вторых, материалы семинаров и домашние задания по-прежнему будут доступны только студентам ШАД. Но тем, у кого нет возможности обучаться в Школе, или тем, кому хочется узнать больше по конкретной теме, наши лекции могут оказаться очень полезными.
Кстати, совсем скоро начнется новый набор в ШАД, сроки проведения вступительных испытаний уже появились здесь.
Читайте также: