|
|
| (не показано 20 промежуточных версий 2 участников) |
| Строка 1: |
Строка 1: |
| | Преподаватель (лекции и практика): Горячко Евгений Евгеньевич | | Преподаватель (лекции и практика): Горячко Евгений Евгеньевич |
| | | | |
| − | == [http://mit.spbau.ru/courses/algstructures_se Программа курса] ==
| + | [http://mit.spbau.ru/courses/algstructures_se Программа курса] |
| − | # Структуры, гомоморфизмы структур. Моноиды. Группы. Числовые группы, симметрические группы и группы автоморфизмов графов.
| + | |
| − | # Подгруппы, классы смежности. Лемма о разбиениях на классы смежности, теорема Лагранжа. Порядок элемента. Лемма о порядке элемента.
| + | |
| − | # Циклические группы. Теорема об описании циклических групп. Дискретный логарифм. Две теоремы о подгруппах циклической группы.
| + | |
| − | # Нормальные подгруппы. Сопряжение элементов. Разбиение на классы сопряженности. Факторгруппы. Теорема о гомоморфизме для групп.
| + | |
| − | # Прямое произведение групп. Теорема о прямом произведении. Теорема о разложении конечной циклической группы в прямое произведение.
| + | |
| − | # Кольца. Числовые кольца, кольца многочленов. Области целостности. Поля. Подкольца. Идеалы, факторкольца. Прямое произведение колец.
| + | |
| − | # Описание <math>\mathrm{gcd}</math> и <math>\mathrm{lcm}</math> в кольце <math>\mathbb Z</math> в терминах идеалов. Соотношение и коэффициенты Безу, алгоритм Евклида. Китайская теорема об остатках.
| + | |
| − | # Функция Эйлера. Лемма об обратимых остатках. Теорема Эйлера. Теорема о функции Эйлера. Теорема о группах обратимых остатков.
| + | |
| − | # Критерий существования дискретного логарифма по модулю <math>n</math>. Тесты Ферма, Эйлера и Миллера–Рабина. Числа Кармайкла. Алгоритм RSA.
| + | |
| − | # Симметрические группы. Транспозиции. Инверсии. Теорема о разложении перестановки в произведение фундаментальных транспозиций.
| + | |
| − | # Знак перестановки и знакопеременные группы. Цикловый тип. Теорема об описании классов сопряженности в симметрических группах.
| + | |
| | | | |
| − | == Основные материалы == | + | == Результаты == |
| − | * [http://mit.spbau.ru/sewiki/images/0/0a/%D0%9E%D1%81%D0%BD%D0%BE%D0%B2%D0%BD%D1%8B%D0%B5_%D0%BE%D0%B1%D0%BE%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%2C_%D0%B8%D1%81%D0%BF%D0%BE%D0%BB%D1%8C%D0%B7%D1%83%D0%B5%D0%BC%D1%8B%D0%B5_%D0%B2_%D0%BA%D1%83%D1%80%D1%81%D0%B5_%C2%AB%D0%90%D0%BB%D0%B3%D0%B5%D0%B1%D1%80%D0%B0%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B5_%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D1%8B%C2%BB.pdf Основные обозначения]
| + | |
| − | * [http://mit.spbau.ru/sewiki/images/4/40/%D0%9E%D1%81%D0%BD%D0%BE%D0%B2%D0%BD%D1%8B%D0%B5_%D1%83%D1%82%D0%B2%D0%B5%D1%80%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D1%8F_%D0%B2_%D0%BA%D1%83%D1%80%D1%81%D0%B5_%C2%AB%D0%90%D0%BB%D0%B3%D0%B5%D0%B1%D1%80%D0%B0%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B5_%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D1%8B%C2%BB.pdf Основные утверждения]
| + | |
| − | * [http://mit.spbau.ru/sewiki/images/0/03/Q3._%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%BF%D0%BE_%D1%86%D0%B8%D0%BA%D0%BB%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%BC_%D0%B3%D1%80%D1%83%D0%BF%D0%BF%D0%B0%D0%BC.pdf Теория по циклическим группам]
| + | |
| | | | |
| − | == Домашние задания== | + | [https://docs.google.com/spreadsheet/ccc?key=0AhaIVBqbQZzvdFNreW56QnRyU1duWGJiaGFBWmktRkE&output=html Результаты] |
| − | ===Требования===
| + | |
| − | Решения задач нужно сдавать преподавателю в виде записей или распечаток. Посылать решения по электронной почте можно, если и только если имеется уважительная причина, по которой их нельзя отдать на бумаге. Решения задачи не принимаются после того, как эта задача разобрана на практике. За каждую задачу можно получить баллы в количестве от нуля до полной стоимости задачи (она указана около номера задачи). На одной практике планируется разбирать около пяти задач в порядке возрастания номера задачи.
| + | |
| | | | |
| − | ===Задачи=== | + | == Основные материалы == |
| − | # [http://mit.spbau.ru/sewiki/images/b/b9/%D0%94%D0%971._%D0%9C%D0%BE%D0%BD%D0%BE%D0%B8%D0%B4%D1%8B%2C_%D0%B3%D1%80%D1%83%D0%BF%D0%BF%D1%8B_%28%D0%B2_%D1%82.%D1%87._%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%BE%D1%80%D1%84%D0%B8%D0%B7%D0%BC%D1%8B_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2%2C_%D1%82%D0%B0%D0%B1%D0%BB%D0%B8%D1%86%D1%8B_%D0%9A%D1%8D%D0%BB%D0%B8%29.pdf Моноиды и группы] (к 10 сентября) [без баллов]
| + | * [http://mit.spbau.ru/files/notation.pdf Основные обозначения] |
| − | # [http://mit.spbau.ru/sewiki/images/d/d3/%D0%94%D0%BE%D0%BC%D0%B0%D1%88%D0%BD%D0%B5%D0%B5_%D0%B7%D0%B0%D0%B4%D0%B0%D0%BD%D0%B8%D0%B5_1_%D0%BF%D0%BE_%D0%90%D0%BB%D0%B3%D0%B5%D0%B1%D1%80%D0%B0%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%BC_%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D0%B0%D0%BC.pdf ДЗ1: подгруппы, циклические группы, сопряженность] (задачи 1-5 к 24 сентября, задачу 10 к 1 октября, задачи 6-9 к 8 октября) + [http://mit.spbau.ru/sewiki/images/0/03/Q3._%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%BF%D0%BE_%D1%86%D0%B8%D0%BA%D0%BB%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%BC_%D0%B3%D1%80%D1%83%D0%BF%D0%BF%D0%B0%D0%BC.pdf теория по циклическим группам]
| + | * [http://mit.spbau.ru/files/assertions.pdf Основные утверждения] |
| − | # Задача к 15 октября: для каждой ниже представленной пары изоморфных групп вида <math>G/{...}_1 \cong {...}_2</math> задать явно какой-либо гомоморфизм <math>f\in \mathrm{Hom}(G, {...}_2)</math> такой, что у него ядро <math>\mathrm{Ker} f= {...}_1</math> и образ <math>\mathrm{Im} f= {...}_2</math> (в общем, как в теореме на практике 8.10.2014):
| + | |
| − | ## <math>\mathbb{C}^\times/\mu_n \cong \mathbb{C}^\times</math>, где <math>n\in \mathbb{N}</math>
| + | |
| − | ## <math>\mathbb{Q}^+/\mathbb{Z}^+\cong \mu_\infty</math>, где <math>\mu_\infty=\{z\in\mathbb{C}\mid \exists n\in\mathbb{N}(z^n=1)\}</math>
| + | |
| − | ## <math>\mathbb{C}^\times / (\mu_n\mathbb{R}_{>0})\cong\mathbb{T}</math><!--
| + | |
| − | --><p>Например, для пары групп <math>(\mathbb{C}^\times, \mathbb{R}_{>0}) </math> примером требуемого гомоморфизма является <math>z\mapsto |z|</math>, т.к. <math>\mathbb{C}^\times / \mathrm{Ker} f \cong \mathrm{Im} f \Leftrightarrow \mathbb{C}^\times /\mathbb{T}\cong \mathbb{R}_{>0}</math>.</p>
| + | |
| | | | |
| | == Список литературы == | | == Список литературы == |
| Строка 37: |
Строка 16: |
| | * Кострикин А.И. Введение в агебру. Том 1. | | * Кострикин А.И. Введение в агебру. Том 1. |
| | * Ленг С. Алгебра | | * Ленг С. Алгебра |
| − | Первые две книги с разжеванным материалом, третья — с сжатым, но многочисленным.
| + | * Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: Построение и анализ. Глава "Теоретико-числовые алгоритмы" |
| | + | * [https://synrc.com/publications/cat/Algebra/Groups/%D0%92%D0%B0%D0%B2%D0%B8%D0%BB%D0%BE%D0%B2%20%D0%9D.%20%D0%9A%D0%BE%D0%BD%D0%BA%D1%80%D0%B5%D1%82%D0%BD%D0%B0%D1%8F%20%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8F%20%D0%B3%D1%80%D1%83%D0%BF%D0%BF.pdf Вавилов Н. Конкретная теория групп] |
| | + | * [https://synrc.com/publications/cat/Algebra/Rings/%D0%92%D0%B0%D0%B2%D0%B8%D0%BB%D0%BE%D0%B2%20%D0%9D.%20%D0%9A%D0%BE%D0%BD%D0%BA%D1%80%D0%B5%D1%82%D0%BD%D0%B0%D1%8F%20%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8F%20%D0%BA%D0%BE%D0%BB%D0%B5%D1%86.pdf Вавилов Н. Конкретная теория колец] |
| | | | |
| | === Дополнительная литература === | | === Дополнительная литература === |
| | * Кострикин А.И. Введение в агебру. Том 3. | | * Кострикин А.И. Введение в агебру. Том 3. |
| | * Верещагин Н.К., Шень А.Х. Языки и исчисления | | * Верещагин Н.К., Шень А.Х. Языки и исчисления |
| | + | |
| | + | [[Category:5 курс. Осень 2014]] |
