Tinkoff Generation

Алгоритмы. Параллель С. План занятий первого полугодия

14 сентября 2019.Оценка времени работы программы.

  1. O-нотация. Математическое определение. Замечание о том, что для конкретных ограничений алгоритм, более быстрый асимптотически, не всегда действительно быстрее. Сколько операций в секунду способен обрабатывать компьютер (порядка \(10^8\)).

  2. Навык "по ограничениям в задаче понять, решения каких асимптотик зайдут, а какие нет".

  3. Квадратичные сортировки: пузырьком, выбором, вставками. Сортировка подсчетом.

21 сентября 2019.Бинарный Поиск #1.

  1. Бинарный поиск. Понимание того, что для бинпоиска нужны

    • Монотонная функция.

    • Инвариант для границ бинпоиска.

  2. Вещественный бинарный поиск. Замечание о том, что лучше всего устанавливать константное число итераций.

  3. Утверждение о том, что непрерывная функция, принимающая в одной точке неположительное значение, а в другой -- неотрицательное, имеет точку, в которой принимает нулевое значение. Применение бинпоиска для поиска этой точки.

28 сентября 2019.C++.

  1. Ускорение ввода-вывода

  2. cppreference - наше всё

  3. Работа с файлами

  4. Встроенные полезности

    • __gcd, gcd, lcm

    • min_element, max_element, nth_element

    • merge, sort, stable_sort

    • fill, copy, (C: memset, memcpy)

    • reverse, rotate

    • unique

    • lower_bound, upper_bound, binary_search

    • next_permutation, prev_permutation

  5. Компараторы

  6. vector, set, map, priority_queue

5 октября 2019.Теория чисел.

  1. НОД и НОК.

    • Алгоритм Евклида.

    • Расширенный алгоритм Евклида.

  2. Нахождение всех делителей числа за \(O(\sqrt n)\)

  3. Факторизация за \(O(\sqrt n)\)

  4. Быстрое возведение в степень.

  5. Решето Эратосфена за \(O(n \log \log n)\)

  6. Применение решета Эратосфена для факторизации чисел за \(O(\log n)\) с предпосчетом за \(O(n)\).

12 октября 2019.Динамическое программирование.

  1. Базовое представление о ДП - задача про кузнечика, подсчет чисел Фибоначчи

  2. Составляющие решения задачи на ДП : состояния, переходы, порядок подсчета, где взять ответ

  3. Двумерная динамика - черепашка

  4. Восстановление ответа в кузнечике и черепашке

  5. второе измерение - 0/1, задача про количество последовательностей без трех единиц поряд

  6. Динамика по цифрам, пилообразная последовательность из чисел от 0 до 9

  7. .