Реферат: Математические методы в информатике

Математические методы в информатике


Преподаватель: Привалов А.А. доцент кафедры ТИДМ


Структура и содержание дисциплины


Общая трудоемкость дисциплины составляет 6 зачетных единиц (216 часов).


Структура дисциплины



№ п/п

Наименование раздела дисциплины

Семестр

Виды учебной работы

(в академических часах)


Л


С


ПЗ


ЛБ


СР

1

Множества.

2

4







1

2

2

Операции и функции над множествами.

2

4







4

2

3

Числа комбинаторики.

2

4







1

2

4

Начала алгебры

2

2







2

4

5

Симметрическая группа.

2

4







2

2

6

Функции и размещения

2

4







4

3

7

Перестановки

2

2







4

4

8

Генерирование перестановок

2

4







6

6

9

Подмножества, множества с повторениями

2

2







2

4

10

Генерирование k-элементных подмножеств

2

2







4

6

11

Разбиение множества

2

2







4

6

12

Числа Стирлинга первого и второго рода

2

2







2

4

13

Генерирование разбиений множества

3

2







6

4

14

Разбиения чисел

3

2







6

4

15

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

3

1







4

4

16

Рекуррентные последовательности и уравнения

3

2







4

4

17

Принцип включения и исключения

3

1







4

4

18

Обратные задачи комбинаторики

3

2







2

4

19

Конечные поля.

3

1







2

4

20

Уравнения и системы уравнений над Zm.

3

2







2

5

21

Цепные дроби.

3

2







2

4

22

Алгоритм Евклида

3

1







2

4

23


Рекурсия

3

2







2

4


^ Содержание дисциплины



№п/п

Наименование раздела дисциплины

Содержание раздела

(дидактические единицы)

1

Множества.

Множества. Кортеж. Декартово произведение множеств. Конечные и бесконечные множества. Мощность множества

2

Операции и функции над множествами.

Операции и функции над множествами. Решение уравнений на нахождение неизвестного множества. Моделирование подмножеств множества. Введение в комбинаторику.

3

Числа комбинаторики.

Числа комбинаторики. Моделирование сочетаний множества

4


Начала алгебры


Группы и подгруппы. Теорема Лагранжа. Теоремы Ферма и Эйлера

5

Симметрическая группа.

Симметрическая группа. Теорема Кэли. Моделирование перестановок. Кольцо и поле

6

Функции и размещения

Решение задач на нахождение функция и размещения с помощью ЭВМ

7

Перестановки

Различные алгоритмы моделирования перестановок. Разложение на циклы. Тип перестановки.

8

Генерирование перестановок

Различные компьютерные программы, моделирующие перестановки, сравнение их по сложности. Программы для определения четности и типа перестановки

9

Подмножества, множества с повторениями

Алгоритмы и компьютерные программы, моделирующие подмножества и множества с повторениями

10

Генерирование k-элементных подмножеств

Алгоритмы и компьютерные программы, моделирующие k-элементные подмножества

11

Разбиение множества

Алгоритмы, моделирующие разбиения множества. Тип разбиения множества.

12

Числа Стирлинга первого и второго рода

Свойства и теоремы для чисел Стирлинга. Число сюръективных отображений. Числа Белла.

13

Генерирование разбиений множества

Алгоритмы и компьютерные программы, моделирующие разбиения множества

14

Разбиения чисел

Алгоритмы и компьютерные программы, моделирующие разбиения множества. Диаграммы Ферреса. Тип разбиения числа.

15

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

Теормы о производящих функциях. Числа Фибоначчи. Бинарные деревья и числа Каталана.

16

Рекуррентные последовательности и уравнения

Решение рекуррентных уравнений и систем. Задачи на нахождение пределов некоторых рекуррентных последовательностей с использованием ЭВМ

17

Принцип включения и исключения

Задачи и теоремы принципа включения и исключения.

18

Обратные задачи комбинаторики

Постановка задачи. Примеры решения обратных комбинаторных задач.

19

Конечные поля.

Конечные поля. Кольца и поля Zm. Теорема Гаусса. Теорема Эйлера – Гаусса. Алгебра и криптология

20

Уравнения и системы уравнений над Zm.

Уравнения и системы уравнений над Zm. Решение уравнений и систем уравнений над Zm на ЭВМ. Позиционные и непозиционные системы счисления.

21

Цепные дроби.

Алгоритм Евклида и цепные дроби. Моделирование цепных дробей. Представления числа обыкновенной дробью с ограничением на знаменатель.

22

Алгоритм Евклида

Алгоритм Евклида и теорема Безу. Аддитивные цепочки и их применение. Быстрое умножение. Разложение на бесквадратные множители. Теорема Остроградского.

23


Рекурсия

Понятие рекурсии. Рекурсивные программы: факториал, «Ханойские башни», генерирование перестановок и сочетаний.



Примерный перечень вопросов к зачету.


Понятие множества. Кортеж. Декартово произведение множеств.

Мощность множества. Конечные и бесконечные множества.

Операции и функции над множествами. Решение уравнений на нахождение неизвестного множества.

Моделирование подмножеств множества..

Числа комбинаторики. Моделирование сочетаний множества

Группы и подгруппы. Теорема Лагранжа. Теоремы Ферма и Эйлера

Симметрическая группа. Теорема Кэли.

Моделирование перестановок. Кольцо и поле

Решение задач на нахождение функция и размещения с помощью ЭВМ

Различные алгоритмы моделирования перестановок. Разложение на циклы. Тип перестановки.

Различные компьютерные программы, моделирующие перестановки, сравнение их по сложности. Программы для определения четности и типа перестановки.

Алгоритмы и компьютерные программы, моделирующие подмножества и множества с повторениями

Алгоритмы и компьютерные программы, моделирующие k-элементные подмножества

Алгоритмы, моделирующие разбиения множества. Тип разбиения множества.

Свойства и теоремы для чисел Стирлинга. Число сюръективных отображений. Числа Белла.

Алгоритмы и компьютерные программы, моделирующие разбиения множества

Алгоритмы и компьютерные программы, моделирующие разбиения множества.

Диаграммы Ферреса. Тип разбиения числа.

Теормы о производящих функциях.

Числа Фибоначчи.

Бинарные деревья и числа Каталана.

Решение рекуррентных уравнений и систем.

Задачи на нахождение пределов некоторых рекуррентных последовательностей с использованием ЭВМ.

Задачи и теоремы принципа включения и исключения.

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

Конечные поля. Кольца и поля Zm. Теорема Гаусса. Теорема Эйлера – Гаусса.

Уравнения и системы уравнений над Zm.

Решение уравнений и систем уравнений над Zm на ЭВМ.

Позиционные и непозиционные системы счисления.

Алгоритм Евклида и цепные дроби.

Моделирование цепных дробей.

Представления числа обыкновенной дробью с ограничением на знаменатель.

Алгоритм Евклида и теорема Безу.

Аддитивные цепочки и их применение. Быстрое умножение. Разложение на бесквадратные множители. Теорема Остроградского.

Понятие рекурсии. Рекурсивные программы: факториал.

Рекурсивные программы: «Ханойские башни», генерирование перестановок и сочетаний.



Учебно-методическое и информационное обеспечение дисциплины


а) основная литература:

Белоусов А.И., Ткачев С.Б., Дискретная математика, М., Изд.МГТУ им.Н.Э.Баумана, 2006

Гашков С.Б., Современная элементарная алгебра, М., Изд. МЦНМО, 2006

Дэвенпорт Г., Высшая арифметика, М., Наука, 1965

б) дополнительная литература::

Акулич И.М. Математическое программирование в примерах и задачах. - М.: Высшая школа,1993.

Л. Аммерал. Машинная графика на персональных компьютерах. - М.: "Сол систем", 1992.

Гостко А.Б. Познакомьтесь с математическим моделированием. - М.: Знание, 1991.

Моисеев Н.Н. Математика ставит эксперимент. - М.: Наука, 1979. Николис Дж. Динамика иерархических систем: эволюционное представление. - М.: Мир, 1989.

Амелькин В. В., М., Дифференциальные уравнения в приложениях , М., Наука,1987