Рабочая программа по дисциплине «дискретная математика» для специальности



Скачать 359.54 Kb.
страница2/3
Дата22.12.2012
Размер359.54 Kb.
ТипРабочая программа
1   2   3



  1. Принципы построения

курса «Логика»
Курс «ДИСКРЕТНАЯ МАТЕМАТИКА» входит в раздел:общепрофессиональные дисциплины.
Курс входит в число математических дисциплин Курс готовит студентов к

использованию языка математики на основе логико-предметных языков,

основных понятий дискретной математики, математической логики и теории

алгоритмов. Основная цель курса для студента - освоение

математического фундамента большей части компьютерных наук.
Дисциплина "Дискретная математика" ставит свой целью ознакомление

студентов с важнейшими разделами дискретной математики и ее

применением в компьютерных науках. В процессе обучения прививаются

навыки свободного обращения с такими дискретными объектами как функции

алгебры логики, автоматные функции, машины Тьюринга, рекурсивные

функции, графы и коды. Во всех разделах дисциплины большое внимание

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

математики. Это способствует более глубокому пониманию проблематики

теории алгоритмов, ее возможностей и трудностей, помогает строить

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

Ядро курса - логико-предметные языки, с помощью которых ведется

изложение всего остального материала. Курс является начальным и для

начала освоения не требует никакой дополнительной подготовки, кроме

обычного школьного образования.
В курсе выделено 3 блока: основания математики (элементы математической

логики и теория множеств и их приложения в математике), основы теории

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

преподавателем в аудитории и выполнения некоторых домашних заданий.
Оценка знаний и умений студентов проводится с помощью тестирования,

проверки зачетных заданий и экзамена.



  1. Цели курса


После изучения теоретических разделов курса и выполнения практических

занятий в объеме рабочей программы студент должен
- знать и уметь использовать основные понятия и методы дискретной

математики: логические исчисления, функциональные системы с

операциями, дискретные структуры (графы, сети, коды), дизъюнктивные

нормальные формы и схемы из функциональных элементов, комбинаторику,

основы теории алгоритмов;
- иметь опыт употребления математической символики для выражения

количественных и качественных отношений объектов; применения теории

алгоритмов;
- иметь представление о соотношении дискретности и непрерывности в

математике;
Структура курса:
[0] Основы формальных языков
[0]->[1] Основы математической логики
[1]->[2] Логико-предметные языки
[2]->[3] Теория множеств
[3]->[4] Построение основных математических структур в теории множеств
[0]->[5] Основы теории алгоритмов
[3]->[6] Основы теории графов
[3]->[7] Комбинаторика
[6,7]->[8] Построение логических функций
[4,5,6,7]->[9] Элементы теории кодирования



  1. Учебно-тематический план





Тема


Количество часов

Лекц

Практ

Сам

1

основы формальных языков

2

1

2

2

язык исчисления высказываний

2

2

2

3

язык исчисления предикатов

2

2

2

4

логико-предметные языки

2

2

2

5

логический вывод

2

2

2

6

аксиоматика формальных предметных теорий

2

2

1

7

язык теории множеств

2

2

1

8

наивная теория множеств и ее парадоксы

2

2

1

9

аксиомы теории множеств

2

2

1

10

отношения и функции в теории множеств

2

1

1

11

Упорядочения

2

1

1

12

эквивалентности и разбиения

2

1

1

13

алгебры и алгебраические системы

2

1

1

14

натуральные и целые числа в теории множеств

2

1

1

15

рациональные и вещественные числа и их функции в теории множеств

2

1

1

16

бесконечные порядковые и количественные числа

2

1

1

17

рекурсивные функции натуральных чисел

2

1

1

18

математическое понятие алгоритма

2

1

1

19

вычислимые и невычислимые функции

2

1

1

20

разрешимые и неразрешимые, перечислимые и неперечислимые множества

2

1

1

21

подклассы множества вычислимых функций

2

1

0

22

основы теории графов

2

1

0

23

основы комбинаторики

2

1

0

24

перечисление дискретных объектов

2

1

0

25

построение логических функций

2

1

0

26

дизъюнктивные нормальные формы

2

1

0

27

схемы из функциональных элементов

2

1

0

28

коды для сжатия информации

1

1

0

29

коды повышенной надежности передачи и хранения информации

1

1

0

30

коды для защиты информации

1

1

0




  1. Содержание лекционных занятий


Лекция 1. Введение, основы формальных языков
Место дискретной математики в системе математического образования.

Дискретная математика и компьютерные науки. Соотношение между

дискретными и непрерывными подходами к изучению различных явлений.

Основы формальных языков. Алфавит, слова, выражения, предложения.

Особенности логических языков.

Лекция 2. Язык исчисления высказываний
Алгебра логики. Функции алгебры логики. Таблицы истинности. Формулы.

Исчисление высказываний. Определение языка формул. Интерпретация.

Истинность. Тавтологии. Выполнимые формулы. Модели.

Лекция 3. Язык исчисления предикатов
Исчисление предикатов 1-го порядка (узкого исчисления предикатов -

УИП). Предметная область. Предметные константы, переменные,

функциональные константы, предикатные константы, вместимость (число

аргументов, размерность). Неформальные понятия функции и отношения.

Понятие интерпретации. Понятие истинности формулы на

заданной интерпретации. Выполнимость и общезначимость формулы 1-го

порядка. Понятие модели.

Лекция 4. Логико-предметные языки
Использование языков, построенных на основе языка узкого исчисления

предикатов. Примеры: язык арифметики натуральных чисел, язык теории

слов в конечном алфавите, языки других математических теорий.

Лекция 5. Логический вывод
Общее понятие логического вывода и выводимой (доказуемой) формулы.

Структура логического вывода в естественной форме записи. Другие виды

логического вывода. Системы аксиом и правила вывода. Правила вывода

исчисления высказываний для естественной формы записи. Правила введения

и правила удаления. Теорема о полноте исчисления высказываний. Правила

вывода для исчисления предикатов. Введение и удаление кванторов.

Полнота исчисления предикатов.

Лекции 6. Аксиоматика формальных предметных теорий
Узкое исчисление предикатов с равенством. Логико-предметные теории с

равенством. Аксиомы и схемы аксиом равенства. Примеры и использование

аксиом арифметики и других математических теорий. Схема аксиом

математической индукции и ее использование.

Лекция 7. Язык теории множеств
Понятие класса абстрактных множеств как предметной области теории

множеств. Константы, предикаты и функции теории множеств:

пустое множество, возможность введения других постоянных множеств,

предикат принадлежности, выразимость равенства через принадлежность

(принцип экстенсиональности) функции пары, объединения, канторовой

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

выделения подмножеств элементов, обладающих заданными свойствами.

Лекция 8. Наивная теория множеств и ее парадоксы
Обозначение множества элементов, обладающих заданными свойствами.

Парадокс Рассела и другие аналогичные парадоксы. Способы избавления от

парадоксов. Ограничения на операцию выделения. Операция

параметрического объединения.

Лекция 9. Аксиомы теории множеств
Аксиома экстенсиональности. Аксиома пустого множества. Аксиома пары.

Аксиома объединения (и ее виды). Виды аксиомы бесконечности. Аксиома

выделения и ее виды.

Лекция 10. Отношения и функции в теории множеств
Упорядоченная пара. Декартовы произведения. Декартова степень.

Бинарное отношение. Однозначность отношения. Функция. Обратное

отношение. Взаимно-однозначное соответствие. Суперпозиция и итерация

отношений. Понятие инъекции, сюръекции, и биекции. Область

определения, множество значений. Примеры функций.

Лекция 11. Упорядочения
Строгие и нестрогие порядки. Свойства порядков. Линейные порядки.

Максимальный и минимальный, наименьший и наибольший элементы. Полные

порядки. Предпорядки. Конечные полные порядки.

Лекция 12. Эквивалентности и разбиения
Свойства отношений эквивалентности. Классы смежности отношений, классы

эквивалентности, факторизация, фактор-множество, разбиение на классы

эквивалентности. Примеры отношений эквивалентности и разбиений на

классы эквивалентности. Восстановление отношения эквивалентности по

разбиению на классы эквивалентности.

Лекция 13. Алгебры и алгебраические системы
Понятие алгебры и алгебраической системы. Примеры алгебраических

систем. Гомоморфизм, эндоморфизм, эпиморфизм, изоморфизм алгебраических

систем. Примеры алгебраических систем. Модель натуральных чисел с

операцией следования в теории множеств как алгебраическая система,

изоморфные ей системы.

Лекция 14. Натуральные и целые числа в теории множеств
Натуральные числа в теории множеств, ординальное моделирование

натуральных чисел. Рекурсивные определения функций в теории множеств.

Натуральные числа со сложением и умножением как алгебраическая система.

Моделирование целых чисел в теории множеств. Кольцо целых чисел со

сложением, вычитанием и умножением как алгебраическая система.

Лекция 15. Рациональные и вещественные числа и их функции в теории

множеств
Моделирование рациональных чисел в теории множеств. Несократимые

дроби, классы эквивалентных дробей. Поле рациональных чисел как

алгебраическая система. Моделирование вещественных чисел в теории

множеств. Сечения, классы эквивалентных фундаментальных

последовательностей. Поле вещественных чисел как алгебраическая

система.

Лекция 16. Бесконечные порядковые и количественные числа
Ординалы. Равномощность. Мощность. Кардиналы. Примеры ординалов и

кардиналов.

Лекция 17. Рекурсивные функции натуральных чисел
Понятие примитивной рекурсии. Операция нахождения наименьшего корня

(минимизации). Операция многоместной суперпозиции. Исходные

функциональные константы для порождения рекурсивных функций. Примитивно

рекурсивные, частично-рекурсивные и общерекурсивные функции.

Лекция 18. Математическое понятие алгоритма
Машины Тьюринга. Операции над машинами Тьюринга. Тезис Тьюринга. Связь

класса рекурсивных функций с классом вычислимых функций. Тезис Черча.

Лекция 19. Вычислимые и невычислимые функции
Модели вычислимых функций. Нормальные алгоритмы. Универсальные

алгоритмы (универсальные машины). Универсальные функции. Неразрешимые

проблемы.
Лекция 20. Разрешимые и неразрешимые, перечислимые и неперечислимые

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

множеств.

Лекция 21. Подклассы множества вычислимых функций
Примитивно рекурсивные, автоматные и элементарные функции, множества и

отношения

Лекция 22. Основы теории графов
Основные понятия и задачи теории графов. Типы графов, способы

задания графов. Изоморфизм графов. Связность. Планарность. Критерии

планарности. Виды и свойства деревьев. Алгоритмы обхода вершин графа.

Алгоритм разбиения графа на подграфы заданного типа. Примеры

применения.

Лекция 23. Основы комбинаторики
Перестановки, размещения, сочетания, сочетания с повторениями,

разбиения, покрытия. Рекуррентные соотношения. Понятие о производящих

функциях. Бином Ньютона.

Лекция 24. Перечисление дискретных объектов
Алгоритмы генерирования комбинаторных объектов: перестановок,

размещений, сочетаний, сочетаний с повторениями, покрытий.

Лекция 25. Построение логических функций.
Реализация функций формулами, эквивалентность формул. Свойства

элементарных функций. Принцип двойственности. Разложение функций

алгебры логики по переменным.
Лекция 26. Дизъюнктивные нормальные

формы.
Совершенная дизъюнктивная нормальная

форма. Полнота и замкнутость, примеры полных систем. Важнейшие

замкнутые классы, теорема о полноте.
Лекция 27. Схемы из функциональных элементов
Построение логических формул по схемам из функциональных элементов.

Построение схем из функциональных элементов по формулам.

Лекция 28. Коды для сжатия информации.
Проблематика теории кодирования. Алфавитное кодирование. Критерии

однозначности декодирования. Методы сжатия информации с помощью

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

Лекция 29. Коды повышенной надежности

передачи и хранения информации.
Помехоустойчивое кодирование. Коды Хемминга.

Лекция 30. Коды для защиты информации
Применение кодирования для защиты информации. Криптография.

Коды с секретным и открытым ключом.


1   2   3

Похожие:

Рабочая программа по дисциплине «дискретная математика» для специальности iconРабочая программа по дисциплине «дискретная математика» для специальности
Рабочая программа составлена на основании гос впо 010200 – Прикладная математика и информатика, утвержденного в 2000 г
Рабочая программа по дисциплине «дискретная математика» для специальности iconРабочая учебная программа по дисциплине «Дискретная математика» для специальности «050201 Математика»
Рабочая учебная программа обсуждена на заседании кафедры алгебры и теории чисел Ургпу
Рабочая программа по дисциплине «дискретная математика» для специальности iconУчебная программа для специальности: (рабочий вариант) 1-310301-02 Математика
Рабочая программа составлена на основе учебной программы по дисциплине “Дискретная математика”, утверждённой 05. 09. 2008
Рабочая программа по дисциплине «дискретная математика» для специальности iconРабочая учебная программа по дисциплине «Дискретная математика» для ооп «010400 Прикладная математика и информатика»

Рабочая программа по дисциплине «дискретная математика» для специальности iconРабочая учебная программа по дисциплине «Элементарная математика» для специальности «050201 Математика» по циклу дпп. Ф. 13 -дисциплины предметной подготовки
Рабочая программа обсуждена на заседании кафедры методики преподавания математики
Рабочая программа по дисциплине «дискретная математика» для специальности iconРабочая учебная программа по дисциплине «Геометрия» для специальности «050201 Математика»
Программа предназначена для работы со студентами, обучающимися по специальности «050201 Математика». Программа составлена на основе...
Рабочая программа по дисциплине «дискретная математика» для специальности iconРабочая программа по дисциплине «Дискретная математика»

Рабочая программа по дисциплине «дискретная математика» для специальности iconРабочая программа по дисциплине «Математика» для специальности
Рабочая программа составлена на основании Государственного образовательного стандарта высшего профессионального образования по специальности:...
Рабочая программа по дисциплине «дискретная математика» для специальности iconРабочая программа по дисциплине "Дискретная математика" для специальности 230105 (220400)
Гос во по направлению 654600 Информатика и вычислительная техника (специальность 230105 (220400) – “Программное обеспечение вычислительной...
Рабочая программа по дисциплине «дискретная математика» для специальности iconРабочая программа по математике для специальности 270800
Рабочая программа по дисциплине “Математика” составлена для студентов специальности 270800 в соответствии с требованиями государственного...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org