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

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

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

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

== 2 Задача о максимальном потоке ==
# [[Определение сети, потока]]
# [[Разрез, лемма о потоке через разрез]] 
# [[Дополняющая сеть, дополняющий путь]]
# [[Лемма о сложении потоков]]
# [[Теорема Форда-Фалкерсона]]
# [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
# взяли [[Алоритм Эдмондса-Карпа]] (0,5)
## Добавить см также
# [[Алгоритм масштабирования потока]]
# взяли [[Блокирующий поток]] (0,5)
## Добавить немного общей информации
## Интервики
# [[Схема алгоритма Диница]]
# [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]] 
# [[Алгоритм поиска блокирующего потока в ациклической сети]] (10)
## алгоритм МКМ плохо и непонятно написан, желательно переписать описание, сделать псевдокод чуть менее абстрактным, добавить доказательство, добавить картиночку, вынести в отдельную статью, ссылка на оригинальную статью есть в обсуждении 
# взяли [[Метод проталкивания предпотока]] (7)
## Картиночки с резервуарами!
## Источники информации
## Добавить см. также
## Дефисы заменить на тире
## Отформатировать псевдокоды
# [[Алгоритм "поднять-в-начало"]]
# [[Теорема о декомпозиции]]
# [[Теорема о декомпозиционном барьере]]
# [[Циркуляция потока]]
# [[Алгоритм Каргера для нахождения минимального разреза]]

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

== 4 Классы чисел и основная теорема арифметики ==
# [[Классы чисел]] 
# [[Натуральные и целые числа]] 
# [[Простые числа]]
# [[Наибольший общий делитель]] 
# [[Основная теорема арифметики]] 
# [[Теоремы о простых числах]] 
# [[Системы счисления]] 
# [[Арифметика чисел в b-ичной системе счисления (Длинная арифметика)]] 
# [[Разложение на множители (факторизация)]]

== 5 Лекция - Основные элементы теории чисел ==
# [[Сравнения, система вычетов, решение линейных систем по модулю]] 5-10-15
## поправить тех
## источники информации, см также
## сделать конспект нормальным
## разбить на 3 конспекта
# [[Китайская теорема об остатках]] 1-5
## поправить тех
## источники информации, см также
## добавить информации или поместить в конспект, где она должна быть теорема
# [[Теорема Ферма]] 1-5
## все правки из китайской теоремы об остатках
# [[Теорема Вильсона]] 1-5
## все правки из китайской теоремы об остатках 
# [[Мультипликативность функции, свертка Дирихле]] 5-10
## разбить на 2, добавить информации
## поправить тех
## английские термины
## добавить использование шаблонов теорем/утверждений
# [[Функция Эйлера]] 1
## поправить тех
## английские термины
## добавить использование шаблонов терем/утверждений
## придать структуру
# [[Количество делителей, сумма делителей]]
# [[Функция Мебиуса]]

<!--=== Практика - Основные алгоритмы теории чисел ===-->
# [[Решето Эратосфена]]
# [[Быстрое возведение в степень]]
# [[Умножение по Монтгомери]]
# [[Дискретное преобразование Фурье]]
# [[Быстрое преобразование Фурье]]

== 6 Лекция - Основы теории групп ==
# [[Полугруппа]], [[моноид]], [[группа]]
# [[Абелева группа]], [[Конечная группа]]
# [[Гомоморфизм групп]], [[изоморфизм групп]]
# [[Подгруппа]], [[нормальная подгруппа]]
# [[Порядок элемента группы]], [[циклическая группа]], [[конечно порожденная группа]]
# [[Регулярное представление группы]]
# [[Теорема о подгруппах циклической группы]]
# [[Смежные классы]], [[теорема Лагранжа]], [[факторгруппы]]
<!--=== Практика - Основы теории групп ===-->
# [[Вычисление порядка элемента в группе]]
# [[Вычисление порядка перестановки в группе перестановок]]
# [[Дискретное логарифмирование в группе]]
# [[Действие группы на множестве]]
# [[Лемма Бернсайда, задача о числе ожерелий]]
# [[Представление групп]]

== 7 Лекция - Основы теории колец ==
#[[Определение кольца, подкольца, изоморфизмы колец]]
#[[Делители нуля, области целостности]]
#[[Единицы (обратимые элементы), группа обратимых элементов]]
#[[Неразложимые элементы, ассоциированные элементы и разложение на множители в целостных кольцах]]
#[[Евклидовы кольца]]
<!--=== Практика - Арифметика полиномов от одной переменной над полем ===-->

== 8 Лекция - Основы теории полей ==
# [[Определение поля и подполя, изоморфизмы полей]]
# [[Примеры полей]]
# [[Мультипликативная группа поля]]
# [[Расширения полей]]

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

== 10 Лекция - Квадратичные вычеты ==
#[[Квадратичный закон взаимности]]
#[[Символ Якоби и его свойства]]
#[[Обобщенный квадратичный закон взаимности]]
#[[Алгоритм вычисления символа Якоби]]
<!--=== Практика - Вероятностные тесты чисел на простоту ===-->
#[[Тест Ферма проверки чисел на простоту, числа Кармайкла]]
#[[Тест Соловея-Штрассена]]
#[[Тест Миллера-Рабина]]

== 11 Лекция - Аналитическая теория чисел ==
# [[Факты из математического анализа]]
# [[Теорема Чебышёва]]
# [[Постулат Бертрана]]
# [[Уточнение констант в теореме Чебышёва]]
# [[Сумма обратных к простым]]
# [[Асимптотический закон распределения простых чисел]]

<!--=== Практика - Вычисление <math>\pi(x)</math> ===-->

== 12 Лекция - Цепные (непрерывные) дроби и уравнение Пелля ==
# [[Цепная дробь]]
# [[Связь цепных дробей и алгоритма Евклида]]
# [[Сходимость цепных дробей]]
# [[Цепные дроби как приближение к числу]]
# [[Квадратичная иррациональность]]
# [[Периодичность цепных дробей]]
# [[Цепные дроби для sqrtd и квадратичных иррациональностей|Цепные дроби для <tex>\sqrt{d}</tex> и квадратичных иррациональностей]]
# [[Уравнение Пелля]]
# [[Представление простых в виде суммы двух квадратов]]