Группы. Теоремы Кэли, Лагранжа, Силова.

Apr 2, 2014Download as PPTX, PDF0 likes1,004 views

Alex Dainiak

Дискретные
структуры
МФТИ, осень 2013
Александр Дайняк
www.dainiak.com

Единственность нейтрального и
обратных элементов

Аддитивные и мультипликативные
обозначения
Общая запись

Группы подстановок
Тождественная подстановка:

Группы подстановок
Композиция подстановок:

Группы подстановок
Обратная подстановка:

Доказательство теоремы Силова:
различные орбиты не пересекаются

Доказательство теоремы Силова:
подбираем специальную орбиту

Доказательство теоремы Силова:
определяем искомую подгруппу

Доказательство теоремы Силова:
описываем смежные классы

Доказательство теоремы Силова:
находим порядок подгруппы

Обсуждаем два определения k-связности. Доказываем теорему Менгера об их эквавалентности (через теорему Форда—Фалкерсона). Доказываем теоремы о построении 2-связных и 3-связных графов. Вводим деревья блоков и точек сочленения. Доказываем теорему Мадера о существовании k-связного подграфа. [Слайды курса, прочитанного в МФТИ в 2013 году.]

Основы теории графов 06: триангуляции и трёхсвязные планарные графыAlex Dainiak

��

Вводим понятие триангуляций. Доказываем, что триангуляции трёхсвязны. Доказываем критерий Татта о том, когда множество образует границу грани в трёхсвязном планарном графе. Доказываем теорему Вагнера—Фари о том, что у любого планарного графа существует укладка, в которой рёбра — отрезки прямых линий. [Слайды курса, прочитанного в МФТИ в 2013 году.]

Основы теории графов 01: напоминание определений, теорема Форда—ФалкерсонаAlex Dainiak

��

Асимптотики комбинаторных чиселAlex Dainiak

��

Раскраски и укладки графовAlex Dainiak

��

Основы теории графов 08: раскраски и списочные раскраскиAlex Dainiak

��

Вводим понятие списочной раскраски. Демонстрируем различие между обчным и списочным хроматическим числом. Доказываем теоремы Брукса и Визинга. Доказываем теорему Алона об оценки списочного хроматического числа через минимальную степень вершин. Доказываем верхнюю оценку на списочное хроматическое число через обычное. [Слайды курса, прочитанного в МФТИ в 2013 году.]

Основы теории графов 07: сепараторы в планарных графахAlex Dainiak

��

Обращение Мёбиуса. Разбиения чисел на слагаемые.Alex Dainiak

��

Автоморфизмы графов. Перечисление графов.Alex Dainiak

��

Теорема о 5 красках. Теорема Холла.Alex Dainiak

��

Основы теории графов 02: факторизация графов (разложение на простые подграфы)Alex Dainiak

��

Доказываем теоремы о разложении полных графов на полные двудольные: Грэхема—Поллака и Анселя. Доказываем теорему Татта о критерии существования совершенного паросочетания в произвольном графе. [Слайды курса, прочитанного в МФТИ в 2013 году.]

Основные определения теории графов. Деревья.Alex Dainiak

��

Свойства биномиальных коэффициентов, формула включений-исключений, неравенств...Alex Dainiak

��

Гиперграфы. Покрытия. Жадный алгоритм.Alex Dainiak

��

Эйлеровы и гамильтоновы циклы. Теорема Турана.Alex Dainiak

��

Основы теории графов 10: экстремальная теория графовAlex Dainiak

��

Доказываем теорему Турана, а затем теорему Эрдёша—Стоуна—Симоновица(Шимоновича) о связи хроматического числа подграфа с максимальным числом рёбер в графе, его не содержащего. [Слайды курса, прочитанного в МФТИ в 2013 году.]

Основы теории графов 11: гамильтоновы циклыAlex Dainiak

��

Доказываем достаточные условия существования в графе гамильтоновых циклов: условия Эрдёша—Хватала, Асратяна—Хачатряна, Хватала. Доказываем необходимые условия существования гамильтонова цикла в планарном графе (теорема Гринберга). [Слайды курса, прочитанного в МФТИ в 2013 году.]

Основы теории графов 04: метрики на деревьяхAlex Dainiak

��

Основы теории графов 05: критерии планарности графовAlex Dainiak

��

Основы теории графов 09: раскраски планарных графов, совершенные графыAlex Dainiak

��

Рассматриваем раскраски планарных графов и другие темы, связанные с раскрасками. Доказываем теорему Томассена о том, что списочное хроматическое число любого планарного графа не превышает пяти. Доказываем теорему Эрдёша о том, что существуют графы с большим хроматическим числом и одновременно большим обхватом. Рассматриваем совершенные графы и доказываем слабую гипотезу Бержа. [Слайды курса, прочитанного в МФТИ в 2013 году.]

Конспект лекций по теории кодированияAlex Dainiak

��

Графовая модель канала связи. Шенноновская ёмкостьAlex Dainiak

��

Приложения теории кодированияAlex Dainiak

��

Приложения кодов, исправляющих ошибки. Рандомизированный протокол в коммуникационной сложности. Криптосхема МакЭлиса. Однородные (псевдослучайные) множества на основе кодов, их приложения к дерандомизации задачи выполнимости и к задаче разделения секрета.

Циклические коды БЧХ, Хемминга. Восстановление синхронизацииAlex Dainiak

��

Циклические коды. Граница БЧХAlex Dainiak

��

Циклические коды. Проверочный и порождающий многочлены, критерий существования кода с заданным порождающим многочленом. Вид порождающей и проверочной матриц. Систематическое кодирование. Граница Боуза—Чоудхури—Хоквингема.

Коды на основе многочленов и алгоритмы их декодированияAlex Dainiak

��

Коды Рида—Соломона. Алгоритм декодирования Берлекэмпа—Велча. Коды Рида—Маллера: кодовое расстояние, алгоритм мажоритарного декодирования. Варианты обобщений конструкции Рида—Маллера. Лемма Липтона—ДеМилло—Шварца—Зиппеля. Понятие об алгеброгеометрических кодах.

Задача о ближайшем кодовом слове. Коды Галлагера—Сипсера—ШпильманаAlex Dainiak

��

Сложность задачи декодирования линейных кодов: задача NCP (задачи о ближайшем кодовом слове). Графы-расширители. Вероятностное доказательство существования расширителей. Коды на основе двудольных графов. Кодовое расстояние кодов на основе расширителей. Алгоритм декодирования Сипсера—Шпильмана.

Линейные кодыAlex Dainiak

��

Линейные коды. Определения. Порождающая и проверочная матрицы. Связь кодового расстояния с проверочной матрицей. Граница Варшамова—Гилберта. Систематическое кодирование. Декодирование по синдрому. Коды Хемминга. Остаточный код. Граница Грайсмера—Соломона—Штиффлера.

Границы Плоткина и Элайеса—БассалыгоAlex Dainiak

��

Коды, исправляющие ошибки. Простейшие границы. Коды Варшамова—Тененгольца.Alex Dainiak

��

Задача исправления и обнаружения ошибок. Геометрическая интерпретация. Типы ошибок. Метрики Хемминга и Левенштейна. Кодовое расстояние. Основные задачи теории кодов, исправляющих ошибки. Коды Варшамова—Тененгольца, алгоритмы исправления одиночных ошибок выпадения и вставки символов. Простейшие границы для параметров кодов, исправляющих ошибки замещения: границы сферической упаковки, Синглтона.

More Related Content

Viewers also liked (12)

Автоморфизмы графов. Перечисление графов.Alex Dainiak

��

Теорема о 5 красках. Теорема Холла.Alex Dainiak

��

Основы теории графов 02: факторизация графов (разложение на простые подграфы)Alex Dainiak

��

Основные определения теории графов. Деревья.Alex Dainiak

��

Свойства биномиальных коэффициентов, формула включений-исключений, неравенств...Alex Dainiak

��

Гиперграфы. Покрытия. Жадный алгоритм.Alex Dainiak

��

Эйлеровы и гамильтоновы циклы. Теорема Турана.Alex Dainiak

��

Основы теории графов 10: экстремальная теория графовAlex Dainiak

��

Основы теории графов 11: гамильтоновы циклыAlex Dainiak

��

Основы теории графов 04: метрики на деревьяхAlex Dainiak

��

Основы теории графов 05: критерии планарности графовAlex Dainiak

��

Основы теории графов 09: раскраски планарных графов, совершенные графыAlex Dainiak

��

Автоморфизмы графов. Перечисление графов.Alex Dainiak

��

Теорема о 5 красках. Теорема Холла.Alex Dainiak

��

Основы теории графов 02: факторизация графов (разложение на простые подграфы)Alex Dainiak

��

Основные определения теории графов. Деревья.Alex Dainiak

��

Свойства биномиальных коэффициентов, формула включений-исключений, неравенств...Alex Dainiak

��

Гиперграфы. Покрытия. Жадный алгоритм.Alex Dainiak

��

Эйлеровы и гамильтоновы циклы. Теорема Турана.Alex Dainiak

��

Основы теории графов 10: экстремальная теория графовAlex Dainiak

��

Основы теории графов 11: гамильтоновы циклыAlex Dainiak

��

Основы теории графов 04: метрики на деревьяхAlex Dainiak

��

Основы теории графов 05: критерии планарности графовAlex Dainiak

��

Основы теории графов 09: раскраски планарных графов, совершенные графыAlex Dainiak

��

More from Alex Dainiak (19)

Конспект лекций по теории кодированияAlex Dainiak

��

Графовая модель канала связи. Шенноновская ёмкостьAlex Dainiak

��

Приложения теории кодированияAlex Dainiak

��

Циклические коды БЧХ, Хемминга. Восстановление синхронизацииAlex Dainiak

��

Циклические коды. Граница БЧХAlex Dainiak

��

Коды на основе многочленов и алгоритмы их декодированияAlex Dainiak

��

Задача о ближайшем кодовом слове. Коды Галлагера—Сипсера—ШпильманаAlex Dainiak

��

Линейные кодыAlex Dainiak

��

Границы Плоткина и Элайеса—БассалыгоAlex Dainiak

��

Коды, исправляющие ошибки. Простейшие границы. Коды Варшамова—Тененгольца.Alex Dainiak

��

Алфавитное кодирование. Коды с минимальной избыточностью. Теорема Макмиллана.Alex Dainiak

��

Алфавитное кодирование. Достаточные условия однозначности декодирования: равномерность, префиксность, суффиксность. Распознавание однозначности: критерий Маркова. Оценка длины неоднозначно декодируемого слова. Неравенство Крафта—Макмиллана; существование префиксного кода с заданным набором длин слов; следствие об универсальности префиксных кодов. Коды с минимальной избыточностью: постановка задачи, теорема Хаффмана о редукции.