ДМ-2017

ПЛАН ЛЕКЦИЙ И ПРАКТИЧЕСКИХ ЗАНЯТИЙ

ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ НА ВЕСЕННИЙ СЕМЕСТР, 2017 ГОД

лектор Поздняков С.Н.

Даты

Тема

Практика

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

1

04.02.17

1. Деление с остатком. Позиционные системы счисления.

2. Алгоритмы перехода к новому основанию (схема Горнера и алгоритм деления).

3*. Алгоритм быстрого возведения числа в степень.

4*. Алгоритмы арифметических операций в арифметике длинных чисел.

Алгоритмы перехода к новому основанию (схема Горнера и алгоритм деления). Алгоритм быстрого возведения числа в степень*

 Тем, кто интересуется и успешно осваивает математический анализ можно посоветовать прочитать несколько первых страницы из статьи про p-адические числа

Можно начать слушать лекции Н.Н.Васильева. В конце 1-ой лекции (1 час 23 минуты) будет рассказ об аддитивных цепочках. Это более общая постановка задачи о быстром возведении числа в степень.

2

11.02.17

1. Делимость. Свойства делимости
2. Алгоритмы НОД.
Классический алгоритм Евклида. Общий подход,

2*. Бинарный алгоритм Евклида.

3. Конечные непрерывные дроби.

Алгоритмы НОД. Общий подход, классический алгоритм Евклида. Конечные непрерывные дроби.

Выдача ИДЗ-1


Тренажер на алгоритм Евклида и связанные с ним понятия
(всем обязательно выполнить все задания в режиме контроля)

Советую порешать задачи с преподавателем практики или самостоятельно по задачнику Франка

3

18.02.17

1. Расширенный алгоритм Евклида. Диофантово уравнение ax+by=c. Подходящие дроби.

2. Бесконечные непрерывные дроби. Наилучшие приближения*.

Расширенный алгоритм Евклида. Диофантово уравнение ax+by=c.

Подходящие дроби.

 Для тех, кто хочет узнать больше о диофантовых уравнениях, предлагаю прочитать интересную брошюру "Уравнения Пелля"
Для тех, кто хочет попробовать себя в самостоятельном исследовании, предлагаю решить диофантовы уравнения:
1) x2+xy=120
2*) x2+xy=c
3**) x2+bxy=c
4***) ax2+bxy=c

Для тех, кто хочет узнать больше:
А. Я. Хинчин "Цепные дроби"
  25.02.17 Объявлено выходным днём
  

4

04.03.17

1. Простые числа. Основная теорема арифметики. 

2*. Разложение на множители. Алгоритм Ферма.

2. Классы вычетов. Арифметика остатков. Признаки делимости.

Классы вычетов. Арифметика остатков. Признаки делимости.

Для тех, кто хочет узнать больше:
Калужнин Л.А. Основная теорема арифметики

Это интересно: "О различии между числами и будильниками"

Для тех, кто хочет узнать больше: Н.Н.Воробьев "Признаки делимости"

5

11.03.17

1. Китайская теорема об остатках.

2. Малая теорема Ферма.

Китайская теорема об остатках.

Малая теорема Ферма.

 

6

18.03.17

1. Функция и теорема Эйлера.

2. Алгоритм RSA. Электронная подпись, электронные деньги.

Функция и теорема Эйлера. Алгоритм RSA.

 

7

25.03.17

1. Арифметика многочленов. Разложение на свободные от квадратов множители*.

2. Примитивные многочлены. Признаки неразложимости.

Арифметика многочленов. 2. Примитивные многочлены. Признаки неразложимости.

 

8

01.04.17

1. Основные понятия комбинаторики. Принцип включения-исключения.

2. Сочетания с повторениями.

Основные понятия комбинаторики. Принцип включения-исключения.

Сочетания с повторениями.

Выдача ИДЗ-2

 Выложены модули для работы с самопроверяемыми задачами по комбинаторике (wisetask_win.zip - самопроверяемые задачи по комбинаторике под Windows, аналогично wisetask_linux.zip - под Linux). Каждый студент должен решить 7 задач из разных разделов (только по комбинаторике) и составить (и решить) 3 задачи из первых трех разделов (задачи на картах, задачи на числах, задачи на словах). Сканы решений выложить на своем сайте, также на сайте выложить xml-файлы составленных задач. Надо стараться выбирать и составлять задачи настолько трудные, насколько по силам студенту.

9

08.04.17

1. Производящие функции. Производящая функция чисел Фибоначчи*.

2. Производящая функция числа билетов с заданной суммой цифр.

Контрольная работа №1.

 

 

10

15.04.16

1. Перечислительная комбинаторика: перечисление подмножеств.

2. Перечисление элементов декартова произведения, перестановок.

Производящие функции.

 

11

22.04.17

 

1. Бинарные отношения и их свойства. Графы бинарных отношений.

2. Отношение эквивалентности и алгоритм построения классов эквивалентности.

Выдача ИДЗ-3

Перечислительная комбинаторика.

 

12

29.04.17


1. Отношение порядка. Алгоритм топологической сортировки.

2. Транзитивное замыканиелгоритм Уоршалла.

Решение комбинаторных задач

 

13

06.05.17


1. Основные задачи и понятия теории графов.

2. Эйлеровы пути и графы.

Бинарные отношения и их свойства.

 

14

13.05.17


1. Планарные графы

2. Теорема о линейном пространстве циклов графа.

Контрольная работа №2.

 

15

20.05.17

 


1. Связность графов.

2. Раскраска графов. Хроматические числа

Алгоритм топологической сортировки. Транзитивное замыкание. Алгоритм Уоршалла.

 

16

27.05.17

Деревья и их свойства.

Решение задач на графы

 
 17 ???
 Репетиционный экзамен.  Переписывание КР-1 и КР-2
 
     
     

В середине семестра:
Коллоквиум по длинным числам

Comments