748
правок
Изменения
Новая страница: «== 1 Задача о паросочетании == # Алгоритм Форда-Фалкерсона для поиска максимального парос…»
== 1 Задача о паросочетании ==
# [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]
# [[Алгоритм Куна для поиска максимального паросочетания]]
# [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]] (7)
## как-то тут сумбурно написано и все в кучу, надо это аккуратно расписать, выделить алгоритм, доказательство и привести пример с картинками
== 2 Задача о максимальном потоке ==
# [[Определение сети, потока]]
# [[Разрез, лемма о потоке через разрез]]
# [[Дополняющая сеть, дополняющий путь]]
# [[Лемма о сложении потоков]]
# [[Теорема Форда-Фалкерсона]]
# [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
# [[Алоритм Эдмондса-Карпа]] (0,25)
## Добавить см также
# [[Алгоритм масштабирования потока]]
# [[Блокирующий поток]] (0,5)
## Добавить немного общей информации
## Интервики
# [[Схема алгоритма Диница]]
# [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]]
# [[Алгоритм поиска блокирующего потока в ациклической сети]] (10)
## алгоритм МКМ плохо и непонятно написан, желательно переписать описание, сделать псевдокод чуть менее абстрактным, добавить доказательство, добавить картиночку, вынести в отдельную статью, ссылка на оригинальную статью есть в обсуждении
# [[Метод проталкивания предпотока]] (7)
## Картиночки с резервуарами!
## Источники информации
## Добавить см. также
## Дефисы заменить на тире
## Отформатировать псевдокоды
# [[Алгоритм "поднять-в-начало"]]
# [[Теорема о декомпозиции]]
# [[Теорема о декомпозиционном барьере]]
# [[Циркуляция потока]]
# [[Алгоритм Каргера для нахождения минимального разреза]]
== 3 Задача о потоке минимальной стоимости ==
# [[Поток минимальной стоимости]] 3
## исправить замечания из обсуждения статьи
# [[Теорема Форда-Фалкерсона о потоке минимальной стоимости]]
# [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]]
# [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]]
# [[Использование потенциалов Джонсона при поиске потока минимальной стоимости]] (5)
## Написать и оформить так, чтобы не было чуши
# [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]] (0,5)
## Добавить см также
## Источники информации оформить нормально
# [[Венгерский алгоритм решения задачи о назначениях]]
== 4 Классы чисел и основная теорема арифметики ==
# [[Классы чисел]] 1-1,5
## увеличить дроби
## все формулы в тех
## источники информации добавить
## см также добавить
## английские термины
## заменить дефисы на тире, там где должно быть тире
## указать ссылки на основные статьи классов
# [[Натуральные и целые числа]] 5-10
## источники информации добавить
## см также добавить
## заменить дефисы на тире, там где должно быть тире
## Сделать нормальным
# [[Простые числа]] 2
## "Так как n делится на q, то n делится на a." показать формально
## поправить пунктуацию
## "Число N не делится ни на одно из простых чисел (2,3,5,…,p), так как при делении N на эти числа получится остаток 1." показать формально
# [[Наибольший общий делитель]] 2
## "Тогда gcd(a,b)=pmin(α1,β1)1⋅pmin(α2,β2)2⋅…⋅pmin(αk,βk)k" что такое p_i?
## Оформить правильно псевдокод
## заменить дефисы на тире, там где должно быть тире
## все формулы в тех
## второй пункт в лемме стандартного алгоритма Евклида переписать
# [[Основная теорема арифметики]] 2
## поместить в натуральные числа, нормально оформить
# [[Теоремы о простых числах]] 2
## переместить в конспект с простыми числами и нормально оформить
<!--=== Практика - Разложение на множители и длинная арифметика ===-->
# [[Системы счисления]] 2
## Нормально заюзать тех
## источники информации добавить
## см также добавить
## английские термины
# [[Арифметика чисел в b-ичной системе счисления (Длинная арифметика)]] 5-8
## английские термины
## все формулы в тех
## категории
## источники информации
## см также
## знаки неравенств
## дроби
## добавить псевдокод
## сделать статью нормальной
# [[Разложение на множители (факторизация)]] 1-2
## знаки неравенств
## дефисы заменить на тире, там же должно быть тире
## английские термины
## сделать псевдокод одинаковым во всех частях статьи
## поправить статью
== 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> и квадратичных иррациональностей]]
# [[Уравнение Пелля]]
# [[Представление простых в виде суммы двух квадратов]]
# [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]
# [[Алгоритм Куна для поиска максимального паросочетания]]
# [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]] (7)
## как-то тут сумбурно написано и все в кучу, надо это аккуратно расписать, выделить алгоритм, доказательство и привести пример с картинками
== 2 Задача о максимальном потоке ==
# [[Определение сети, потока]]
# [[Разрез, лемма о потоке через разрез]]
# [[Дополняющая сеть, дополняющий путь]]
# [[Лемма о сложении потоков]]
# [[Теорема Форда-Фалкерсона]]
# [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
# [[Алоритм Эдмондса-Карпа]] (0,25)
## Добавить см также
# [[Алгоритм масштабирования потока]]
# [[Блокирующий поток]] (0,5)
## Добавить немного общей информации
## Интервики
# [[Схема алгоритма Диница]]
# [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]]
# [[Алгоритм поиска блокирующего потока в ациклической сети]] (10)
## алгоритм МКМ плохо и непонятно написан, желательно переписать описание, сделать псевдокод чуть менее абстрактным, добавить доказательство, добавить картиночку, вынести в отдельную статью, ссылка на оригинальную статью есть в обсуждении
# [[Метод проталкивания предпотока]] (7)
## Картиночки с резервуарами!
## Источники информации
## Добавить см. также
## Дефисы заменить на тире
## Отформатировать псевдокоды
# [[Алгоритм "поднять-в-начало"]]
# [[Теорема о декомпозиции]]
# [[Теорема о декомпозиционном барьере]]
# [[Циркуляция потока]]
# [[Алгоритм Каргера для нахождения минимального разреза]]
== 3 Задача о потоке минимальной стоимости ==
# [[Поток минимальной стоимости]] 3
## исправить замечания из обсуждения статьи
# [[Теорема Форда-Фалкерсона о потоке минимальной стоимости]]
# [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]]
# [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]]
# [[Использование потенциалов Джонсона при поиске потока минимальной стоимости]] (5)
## Написать и оформить так, чтобы не было чуши
# [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]] (0,5)
## Добавить см также
## Источники информации оформить нормально
# [[Венгерский алгоритм решения задачи о назначениях]]
== 4 Классы чисел и основная теорема арифметики ==
# [[Классы чисел]] 1-1,5
## увеличить дроби
## все формулы в тех
## источники информации добавить
## см также добавить
## английские термины
## заменить дефисы на тире, там где должно быть тире
## указать ссылки на основные статьи классов
# [[Натуральные и целые числа]] 5-10
## источники информации добавить
## см также добавить
## заменить дефисы на тире, там где должно быть тире
## Сделать нормальным
# [[Простые числа]] 2
## "Так как n делится на q, то n делится на a." показать формально
## поправить пунктуацию
## "Число N не делится ни на одно из простых чисел (2,3,5,…,p), так как при делении N на эти числа получится остаток 1." показать формально
# [[Наибольший общий делитель]] 2
## "Тогда gcd(a,b)=pmin(α1,β1)1⋅pmin(α2,β2)2⋅…⋅pmin(αk,βk)k" что такое p_i?
## Оформить правильно псевдокод
## заменить дефисы на тире, там где должно быть тире
## все формулы в тех
## второй пункт в лемме стандартного алгоритма Евклида переписать
# [[Основная теорема арифметики]] 2
## поместить в натуральные числа, нормально оформить
# [[Теоремы о простых числах]] 2
## переместить в конспект с простыми числами и нормально оформить
<!--=== Практика - Разложение на множители и длинная арифметика ===-->
# [[Системы счисления]] 2
## Нормально заюзать тех
## источники информации добавить
## см также добавить
## английские термины
# [[Арифметика чисел в b-ичной системе счисления (Длинная арифметика)]] 5-8
## английские термины
## все формулы в тех
## категории
## источники информации
## см также
## знаки неравенств
## дроби
## добавить псевдокод
## сделать статью нормальной
# [[Разложение на множители (факторизация)]] 1-2
## знаки неравенств
## дефисы заменить на тире, там же должно быть тире
## английские термины
## сделать псевдокод одинаковым во всех частях статьи
## поправить статью
== 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> и квадратичных иррациональностей]]
# [[Уравнение Пелля]]
# [[Представление простых в виде суммы двух квадратов]]
