План ДМ-2010

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

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

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

Номера

недель

Дата

Тема

Практика

1

9.02.10 (13.02.10)

 

4 часа

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

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

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

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

 

2

16.02.10 (20.02.10)

2 часа

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

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

Работа с длинными числами.

Выдача ИДЗ-1

3

23.02.10 (27.02.10)

4 часа


 

4

02.03.10 (06.03.10)

2 часа

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

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


Алгоритм Евклида и решение диофантовых уравнений.

5

09.03.10 (13.03.10)

4 часа

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

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

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

4. Классы вычетов. Арифметика остатков.

 Признаки делимости.


6

16.03.10 (20.03.10)

2 часа

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

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


Арифметика остатков. Малая теорема Ферма, функция Эйлера, китайская теорема об остатках.

7

23.03.10 (27.03.10)

4 часа

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

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

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

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

 

8

30.03.10 (03.04.10)

2 часа

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

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


Работа с многочленами. Выдача ИДЗ-2 и ИДЗ-3.

9

06.04.10 (10.04.10)

4 часа

 

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

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

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

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


10

13.04.10 (17.04.10)

2 часа

1-2. Контрольная работа №1. Числа и многочлены.


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

 

11

20.04.10 (24.04.10)

4 часа

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

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

3. Отношение порядка.

4. Алгоритм топологической сортировки.

 

12

27.04.10 (01.05.10)

(15.05.10)

2 часа

1. Транзитивное замыкание.

2. Алгоритм Уоршалла.

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

13

04.05.10 (08.05.10)

(22.05.10)

4 часа

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

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

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

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

 

14

11.05.10 

(29.05.10)

2 часа

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

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

Бинарные отношения.

15

18.05.10

(доп. встреча)

4 часа

 


1-2. Контрольная работа №2. Комбинаторика.

3-4. Примеры экзаменационных задач.

 

16

25.05.10 

2 часа

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


 

Зачеты по курсовой работе (защита всех трех ИДЗ).

17

 

 

 

 

Comments