Вступительный семинар (11 сентября 2013)

  1. Упражение на O-шки
    1. f = O(Θ(O(g))
    2. f = O(Θ(Ω(g))
    3. f = Θ(Ω(Θ(g))
  2. Соцопрос
    1. Алгоритмы (bfs, Дейкстра, Эдмондс, нахождение вещественных корней многочлена)
    2. Математика (простые числа, комплексные числа, ортоганализация Грамма-Шмидта, Тоерема Рисса, интегральчик)
    3. Языки программирования (C++, Java, Python, Haskell, ASM, Pascal)
  3. Даны N натуральных чисел, найти кол-во различных
    1. За O(NlogN) с использованием сортировки
    2. За O(N), если исходные числа от 1 до N (used[a[i]] = 1)
    3. За O(N), если исходные числа произвольные (хеш-таблица)
    4. Самая простая реализация хеш-таблицы (List L[M]; a[i] → L[a[i]%M])
  4. Решить в натуральных числах уравнение N = x2 + y2
    1. За O(N)
    2. За O(√ N )
    3. За O(√ N ) и без извлечения корня
    4. Как еще оптимизировать: убрать все умножения (-20%), минимизировать количество сложений/вычитаний/сравнений (еще -10%)
  5. Дано N, найти натуральные x, y, z: N = xyz, и величина 2(xy + yz + zx) минимальна
    1. За O(N3)
    2. За O(N2)
    3. За O(N1/3N1/2) − x ≤ y ≤ z поэтому x ≤ N1/3, y ≤ N1/2
    4. За O(N1/2 + Neps) − нашли все делители числа N, перебираем x, y, z, как делители числа
    5. Количество делителей: 109 → 103; 1018 → 105
  6. Даны N различных чисел от 1 до N, найти количество треугольников, длины сторон которых выбираются из данных N чисел
    1. За O(N3)
    2. За O(N2) − метод двух указателей
    3. Доказательство, что метод двух указателей работает за O(N)
  7. Теория чисел
    1. Проверка числа на простоту за O(√ N )
    2. Разложение числа на простые за O(√ N )
    3. Нахождение всех делителей числа за O(√ N )
    4. Проверка k чисел на простоту за O(√ N (1 + k / logn))
  8. Сложение матриц
    1. Два варианта написать циклы for: (for i, for j) и (for j, for i)
    2. Кеши и оперативная память: 4K, 4M, 4G. Кешируется ровно один из вариантов.
  9. Подсчет асимптотики
    1. Умеем считать циклы for
    2. Простой пример на амортизационный анализ анализ: Add(x) добавить x, Del(k) удалить последние k элементов. Среднее время работы Del = O(1).
    3. T(n) = T(n-1) + T(n-3), ищем ответ в виде an, находим его бинпоиском


  10. Упражения на дом
    1. Доказать, что D(N) = O(Neps) для любого eps > 0