Планарность

  1. Теорема Эйлера. E + K + 1 = V + G.
  2. Любой граф можно уложить в R3. Например, все вершины на прямой, каждому ребру своя плоскость.
  3. Укладка на сфере = укладке на плоскости. Любую грань можно сделать внешней.
  4. K3,3 и K5 не планарны.
  5. Теорема Куратовского: если в графе нет подграфов гомеоморфных K3,3 или K5, граф планарен.
  6. Алгоритм Демукрона укладки графа за O(V2).
  7. Док-во времени работы (разбиение на k компонент работает за O(Vk), сумма всех k = O(V)).
  8. Алгоритм разбиения графа на грани за O(V + sort). Как этот алгоритм применить к результату алгоритма Демукрона?
  9. Алгоритм определения внешних граней за O(V).

2-SAT

  1. Постановки задачи. Решение перебором за O(2N*N)
  2. Жадное решение за O(NE). Алгоритм = пусть (x[i] = 0) из этого что-то следует... dfs. Если нашли противоречие, значит x[i] = 1.
  3. Док-во: если есть ребро (x[i]=a) --> (x[p]=b), то есть ребро (x[p]=!b) --> (x[i]=!a). То же можно сформулировать для путей.
  4. Решение за O(E) = топологическая сортировка вершин в орграфе из 2N вершин.

Нейрон. Нейросети.

  1. Общий случай: "кошка" или не "кошка".
  2. Линейные неравенства и пороговое значение.
  3. Разделение: меньше t=0.3 или больше 1. Бинпоиск по t.
  4. Если все неравенства выполняются - Л.П.
  5. Обучение нейрона.
    1. Л.П. с выкидыванием строк
    2. Л.П. с итеративным наращиванием множества строк
    3. Градиентный спуск (сглаживание целевой функции до arctg(t) или e-t)
  6. Примеры
    1. Распознавание распределения в R.
    2. Распознавание распределения в более сложном пространстве (строки).
    3. Кто автор этого стиха? Пушкин или Лермонтов?
  7. Обобщение
    1. (Выбор 1..N) = {N - 1 последовательный метод 0..1)

Линейное программирование.

  1. Системы Ax = b. Решение ее методом Гаусса за O(nm2), где m - число строк, n - число столбцов.
  2. Метод Гаусса приводит матрицу A к виду (E,A'). Храним p[1..m] --- переменные, которые соответствуют первым m столбцам.
  3. Добавляем условие x >= 0 и условие summ (x[i]*c[i]) --> min|max. Получаем задачу Л.П. в виде, с которым можно работать.
  4. Если b[i] < 0, то поиск начального решения = summ z[i] --> min. Где x[i] = y[i] - z[i];
  5. p[1..m] - наш базисный план.
  6. Собственно Simplex-метод = последовательный переход к следующему базисному плану
  7. Переход = замена p[i] на некоторое j.
  8. Собственно код.
  9. Решение задач maxflow и mincostflow с помощью Л.П.