Алгебра и теория чисел :: занятие 01 (09.02.2010)

Занятие 1 (09.02.2010)
Практические задачи. Разложение на множители и длинная арифметика
Лекция. (Теория) Классы чисел и основная теорема арифметики
Лекция. (Практика) Разложение на множители и длинная арифметика

Занятие 1 (09.02.2010)
Разложение на множители и длинная арифметика ps pdf
factor1.Разложение на множители-1ps pdf
numsyst.Cистемы счисленияps pdf
arithmetics.Длинная арифметикаps pdf
fibonacci1.Числа Фибоначчи-1ps pdf
egcd.Расширенный алгоритм Евклидаps pdf
(Теория) Классы чисел и основная теорема арифметики
План лекции
  1. Классы чисел: натуральные, целые, рациональные, вещественные, комплексные
    1. Определения натуральных чисел
      • Неформальное определение
      • Аксиомы Пеано
      • Теоретико-множественное определение
    2. Определение целых, рациональных, вещественных и комплексных чисел
    3. Операции сложения, вычитания, умножения, деления, извлечение корня
  2. Натуральные и целые числа
    1. Принцип индукции, существование наименьшего числа в любом множестве натуральных чисел
    2. Деление чисел с остатком
  3. Простые числа
    1. Существование разложения на простые
  4. Наибольший общий делитель
    1. Наибольший общий делитель как максимальное число, делящее два данных числа
    2. Алгоритм Евклида (обычный и расширенный)
    3. Наибольший общий делитель как общий делитель, делящий все остальные общие делители
  5. Основная теорема арифметики
    1. Теорема о том, что если произведение двух чисел делится на простое, то одно из них на него делится
    2. Основная теорема арифметики
  6. Теоремы о простых числах
    1. Теорема о существовании бесконечного числа простых чисел
    2. Теорема о расходимости ряда $\sum 1/n$
    3. Теорема о сходимости ряда $\sum 1/n^2$
    4. Теорема о расходимости ряда $\sum 1/p$
(Практика) Разложение на множители и длинная арифметика
План лекции
  1. Системы счисления
    1. Позиционные системы счисления, запись числа в b-ичной системе счисления
    2. Смешанные системы счисления
    3. Фибоначчиева система счисления
  2. Арифметика чисел в b-ичной системе счисления (Длинная арифметика)
    1. Представление в памяти
    2. Сложение, вычитание, умножение, деление на короткое, деление на длинное
    3. Подбор значения очередной цифры в алгоритме деления в столбик
  3. Разложение на множители (факторизация)
    1. Проверка числа на простоту за $O(\sqrt{n})$
    2. Разложение на множители за $O(\sqrt{n})$
  4. Алгоритм Евклида
    1. Числа Фибоначчи, формула Бине, асимптотика роста
    2. Время работы алгоритма Евклида
    3. Двоичный алгоритм Евклида, расширенный двоичный алгоритм Евклида