ДМ-2013

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

ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ НА ВЕСЕННИЙ СЕМЕСТР 2012-2013 ГОДА

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

 

Дата

Тема

Практика

1

09.02.12

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

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

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

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

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

2

16.02.12

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

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

Выдача ИДЗ-1

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

 

3

02.03.12

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

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

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

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

 

4

16.03.12

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

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

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

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

5

23.03.12

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

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

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

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

6

30.03.12

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

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

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

7

06.04.12

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

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

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

 

8

13.04.12

 

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

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

Выдача ИДЗ-2

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

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

9

20.04.12

 

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

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

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

 

10

27.04.12

 

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

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

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

11

04.05.12

 

 

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

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

Выдача ИДЗ-3

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

12

11.05.12

 

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

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

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

13

18.05.12

 

 

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

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

 

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

14

25.05.12

 

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

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

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

15

01.06.12

 

1. Раскраска графов.

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

 

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

16

08.06.12

 

Репетиционный экзамен.

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

 

Comments