Алгоритмы и структуры данных4:Тикеты

Материал из Викиконспекты
Перейти к: навигация, поиск

Почти конспектов из теории чисел (начиная с [math]4[/math]й группы) есть одна большая правка: сделать конспект нормальным

Если берете конспект из [math]4[/math]й и ниже группы, то надо написать куратору, чтобы он оценил количество баллов

1 Задача о паросочетании

  1. Алгоритм Форда-Фалкерсона для поиска максимального паросочетания
  2. Алгоритм Куна для поиска максимального паросочетания
  3. Паросочетания в недвудольных графах. Алгоритм вырезания соцветий (7)
    1. как-то тут сумбурно написано и все в кучу, надо это аккуратно расписать, выделить алгоритм, доказательство и привести пример с картинками

2 Задача о максимальном потоке

  1. Определение сети, потока
  2. Разрез, лемма о потоке через разрез
  3. Дополняющая сеть, дополняющий путь
  4. Лемма о сложении потоков
  5. Теорема Форда-Фалкерсона
  6. Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину
  7. взяли Алоритм Эдмондса-Карпа (0,5)
    1. Добавить см также
  8. Алгоритм масштабирования потока
  9. взяли Блокирующий поток (0,5)
    1. Добавить немного общей информации
    2. Интервики
  10. Схема алгоритма Диница
  11. Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями
  12. Алгоритм поиска блокирующего потока в ациклической сети (10)
    1. алгоритм МКМ плохо и непонятно написан, желательно переписать описание, сделать псевдокод чуть менее абстрактным, добавить доказательство, добавить картиночку, вынести в отдельную статью, ссылка на оригинальную статью есть в обсуждении
  13. взяли Метод проталкивания предпотока (7)
    1. Картиночки с резервуарами!
    2. Источники информации
    3. Добавить см. также
    4. Дефисы заменить на тире
    5. Отформатировать псевдокоды
  14. Алгоритм "поднять-в-начало"
  15. Теорема о декомпозиции
  16. Теорема о декомпозиционном барьере
  17. Циркуляция потока
  18. Алгоритм Каргера для нахождения минимального разреза

3 Задача о потоке минимальной стоимости

  1. Поток минимальной стоимости 3
    1. исправить замечания из обсуждения статьи
  2. Теорема Форда-Фалкерсона о потоке минимальной стоимости
  3. Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети
  4. Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости
  5. Использование потенциалов Джонсона при поиске потока минимальной стоимости (5)
    1. Написать и оформить так, чтобы не было чуши
  6. Сведение задачи о назначениях к задаче о потоке минимальной стоимости (0,5)
    1. Добавить см также
    2. Источники информации оформить нормально
  7. Венгерский алгоритм решения задачи о назначениях

4 Классы чисел и основная теорема арифметики

  1. Классы чисел
  2. Натуральные и целые числа
  3. Простые числа
  4. Наибольший общий делитель
  5. Основная теорема арифметики
  6. Теоремы о простых числах
  7. Системы счисления
  8. Арифметика чисел в b-ичной системе счисления (Длинная арифметика)
  9. Разложение на множители (факторизация)

5 Лекция - Основные элементы теории чисел

  1. Сравнения, система вычетов, решение линейных систем по модулю 5-10-15
    1. поправить тех
    2. источники информации, см также
    3. сделать конспект нормальным
    4. разбить на 3 конспекта
  2. Китайская теорема об остатках 1-5
    1. поправить тех
    2. источники информации, см также
    3. добавить информации или поместить в конспект, где она должна быть теорема
  3. Теорема Ферма 1-5
    1. все правки из китайской теоремы об остатках
  4. Теорема Вильсона 1-5
    1. все правки из китайской теоремы об остатках
  5. Мультипликативность функции, свертка Дирихле 5-10
    1. разбить на 2, добавить информации
    2. поправить тех
    3. английские термины
    4. добавить использование шаблонов теорем/утверждений
  6. Функция Эйлера 1
    1. поправить тех
    2. английские термины
    3. добавить использование шаблонов терем/утверждений
    4. придать структуру
  7. Количество делителей, сумма делителей
  8. Функция Мебиуса
  1. Решето Эратосфена
  2. Быстрое возведение в степень
  3. Умножение по Монтгомери
  4. Дискретное преобразование Фурье
  5. Быстрое преобразование Фурье

6 Лекция - Основы теории групп

  1. Полугруппа, моноид, группа
  2. Абелева группа, Конечная группа
  3. Гомоморфизм групп, изоморфизм групп
  4. Подгруппа, нормальная подгруппа
  5. Порядок элемента группы, циклическая группа, конечно порожденная группа
  6. Регулярное представление группы
  7. Теорема о подгруппах циклической группы
  8. Смежные классы, теорема Лагранжа, факторгруппы
  9. Вычисление порядка элемента в группе
  10. Вычисление порядка перестановки в группе перестановок
  11. Дискретное логарифмирование в группе
  12. Действие группы на множестве
  13. Лемма Бернсайда, задача о числе ожерелий
  14. Представление групп

7 Лекция - Основы теории колец

  1. Определение кольца, подкольца, изоморфизмы колец
  2. Делители нуля, области целостности
  3. Единицы (обратимые элементы), группа обратимых элементов
  4. Неразложимые элементы, ассоциированные элементы и разложение на множители в целостных кольцах
  5. Евклидовы кольца

8 Лекция - Основы теории полей

  1. Определение поля и подполя, изоморфизмы полей
  2. Примеры полей
  3. Мультипликативная группа поля
  4. Расширения полей

9 Лекция - Первообразные корни и квадратичные вычеты

  1. Теорема о цикличности мультипликативной группы поля [math]\mathbb{Z}/p\mathbb{Z}[/math]
  2. Первообразные корни
  3. Теорема о существовании первообразных корней по модулям вида [math]2,4,p^n,2\cdot p^n[/math]
  4. Квадратичные вычеты, количество квадратичных вычетов по простому модулю
  5. Символ Лежандра, критерий Эйлера
  6. Теорема о [math]((\frac{p-1}{2})!)^2\equiv -1 (mod ~p)[/math] при [math]p=4\cdot k+1[/math]
  7. Лемма Гаусса для вычисления квадратичного характера числа по простому модулю

10 Лекция - Квадратичные вычеты

  1. Квадратичный закон взаимности
  2. Символ Якоби и его свойства
  3. Обобщенный квадратичный закон взаимности
  4. Алгоритм вычисления символа Якоби
  5. Тест Ферма проверки чисел на простоту, числа Кармайкла
  6. Тест Соловея-Штрассена
  7. Тест Миллера-Рабина

11 Лекция - Аналитическая теория чисел

  1. Факты из математического анализа
  2. Теорема Чебышёва
  3. Постулат Бертрана
  4. Уточнение констант в теореме Чебышёва
  5. Сумма обратных к простым
  6. Асимптотический закон распределения простых чисел


12 Лекция - Цепные (непрерывные) дроби и уравнение Пелля

  1. Цепная дробь
  2. Связь цепных дробей и алгоритма Евклида
  3. Сходимость цепных дробей
  4. Цепные дроби как приближение к числу
  5. Квадратичная иррациональность
  6. Периодичность цепных дробей
  7. Цепные дроби для [math]\sqrt{d}[/math] и квадратичных иррациональностей
  8. Уравнение Пелля
  9. Представление простых в виде суммы двух квадратов
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Алгоритмы_и_структуры_данных4:Тикеты&oldid=69902»