Учебная программа курса или дисциплины «Дискретные структуры»




Скачать 46.72 Kb.
НазваниеУчебная программа курса или дисциплины «Дискретные структуры»
Дата публикации23.06.2013
Размер46.72 Kb.
ТипУчебная программа курса
lit-yaz.ru > Математика > Учебная программа курса
Учебная программа курса или дисциплины
«Дискретные структуры»
Цель и задачи курса:

Ознакомить слушателей с фундаментальными понятиями, методами и алгоритмами дискретной математики, которые составляют теоретический и методический базис информационных технологий
Тема 1. Логика высказываний, высказывание, связки, истинность, тавтология и противоречие, эквивалентность пропозициональных форм, законы Де Моргана, полные системы связок. Понятие исчисления высказываний, понятие формальной аксиоматической теории; логический вывод, аксиомы и правила вывода

Тема 2. Булевы функции (функция, порождаемая пропозициональной формой; построение формы, порождающей заданную функцию). Цифровые логические схемы (типы вентилей, синтез схем по таблицам истинности, дизъюнктивные нормальные формы).

Тема 3. Логика предикатов (высказывания с кванторами, истинность,отрицание высказываний с кванторами). Понятие исчисления предикатов (понятие формальной аксиоматической теории; логический вывод, аксиомы и правила вывода).

Тема 4. Методы доказательств. Структура формальных доказательств. Прямое доказательство. Доказательство с помощью контрпримеров. Доказательство от противного. Доказательство посредством контрапозиции.

Тема 5. Математическая индукция. Использование принципа математической индукции (провести доказательство какого-нибудь утверждения с использованием индукции).

Тема 6. Теория множеств (принадлежность, включение, операции над множествами, тождества, законы Де Моргана). Понятие булевой алгебры, примеры.

Тема 7. Отношения, бинарные отношения. Отношение эквивалентности на множестве. Порождаемое им разбиение на смежные классы, их свойства. Отношение порядка.

Тема 8. Формальные языки. Понятие конечного автомата, распознающего язык.

Тема 9. Комбинаторика (размещения, перестановки, сочетания, сочетания с повторениями). Бином Ньютона

Тема 10. Графы (ориентированные/неориентированные, подграфы, степень вершины, теоремы о сумме степеней и о кол-ве нечетных вершин в графе).

Тема 11. Пути, цепи и контуры (определения, эйлеровы и гамильтоновы контуры — теоремы и следствия существования в ориентированных и неориентированных графах). Связность графов. Представление графов с помощью матриц инцидентности. Теорема о степени матрицы инцидентности.

Тема 12. Деревья и их свойства, каркасы (остовные деревья). Графы с весами. Алгоритм построения каркаса минимального веса (алгоритм Kruskal’а).

Тема 13. Бинарные деревья, полные бинарные деревья и их свойства. Организация хранения упорядоченных данных в виде бинарного дерева. Алгоритмы поиска, вставки и удаления узлов в деревьях.

Тема 14. Сбалансированные деревья (определение, преимущества организации хранения упорядоченных данных в виде бинарного / сбалансированного/ дерева). Алгоритм балансировки
Литература.

  1. Н.К. Верещагин, А. Шень. Начала теории множеств. 2-е издание, испр.- М.: МЦНМО, 2002.

  2. С.В. Судоплатов, Е.В. Овчинникова. Элементы дискретной математики: Учебник. М.: ИНФРА-М, Новосибирск: Изд-во НГТУ, 2003. - 280 с. (Серия "Высшее образование").

  3. Б.Н. Иванов. Дискретная математика. Алгоритмы и программы: Учеб. пособие.- М.: Лаборатория Базовых Знаний, 2002 - 288 с.

  4. С.В. Яблонский. Введение в дискретную математику: Учеб. пособие для вузов. 2-е изд, перераб. и доп.- М.: Наука, Гл. ред. физ.-мат. лит., 1986.-384 с.

  5. А. Шень. Программирование: теоремы и задачи.- М.: МЦНМО, 1995.

  6. Э. Мендельсон. Введение в математическую логику.- М.: Наука, 1976.

  7. А.Н.Колмогоров, А.Г.Драгалин. Математическая логика.- М.:УРСС, 2004.

Вариант письменного экзамена-теста
В каждом задании четыре варианта ответа, причем верными могут быть несколько вариантов!



  1. Для натурального n определим множество , являющееся подмножеством множества натуральных чисел N.
    Выберите верные утверждения:
    (а) ; (б) ; (в); (г).



  2. Среди группы из 200 человек:
    - 150 играют в боулинг или бильярд;
    - 85 играют в боулинг;
    - 60 играют в боулинг и бильярд;
    Сколько человек играют в бильярд?
    (а) 125;
    (б) 65;
    (в) 35;
    (г) 25.



  3. Отношение определено следующим образом:
    .
    Выберите верные утверждения:
    (а)  - рефлексивно;
    (б)  - симметрично;
    (в)  - транзитивно;
    (г)  - отношение эквивалентности.



  4. Сколькими способами можно группу из 20 студентов разделить на две группы по 7 студентов и одну группу из 6 студентов?
    Выберите верные утверждения:
    (а) ;
    (б) ;
    (в) ;
    (г) никакое из вышеперечисленных.



  5. Сколькими способами можно выбрать из полной колоды (52 карты) 10 карт, чтобы среди них был хотя бы один туз?
    Выберите верные утверждения:
    (а)  ;
    (б) ;
    (в) ;
    (г) никакое из вышеперечисленных.



  6. Дано дерево, n вершин (n>=3).
    Выберите верные утверждения:
    (а) в дереве (n-1) ребро;
    (б) есть хотя бы одна вершина степени 1;
    (в) есть хотя бы две вершины степени 2;
    (г) для любой пары вершин в дереве есть ровно один путь, их соединяющий.



  7. Дан связный граф без петель (петля – ребро, начинающееся и заканчивающееся в одной и той же вершине). В графе 11 вершин, причем все имеют степень 6. Если в этом графе существует гамильтонов контур, то какова его длина (сколько ребер графа он содержит)?
    (а) 66; (б) 11; (в) 33; (г) 10.



  8. ,
    Какие из следующих утверждений истинны:

  1. Г и совместны

  2. Г – выполнимо

  3. Г |–


(а) I и III;
(б) только II;
(в) I, II, III;
(г) I и II.



  1. Что означает свойство монотонности вывода?
    – формулы, – множества формул
    (а) |– |– ;
    (б) |– и , |– |– ;
    (в) |– и |– ;
    (г) |– , |– и |– |– .



  2. Какое минимальное число вентилей AND, OR, NOT требуется для построения схемы, поведение которой описывается следующей таблицей:


Входы

Выход

x

y

z

r

1

1

1

0

1

1

0

1

1

0

1

1

1

0

0

1

0

1

1

0

0

1

0

0

0

0

1

1

0

0

0

1


(а) 23;

(б) 14;

(в) 4;

(г) ни один из указанных выше вариантов не подходит

Добавить документ в свой блог или на сайт

Похожие:

Учебная программа курса или дисциплины «Дискретные структуры» iconУчебная программа курса или дисциплины «Основы программирования»
В частности, в курсе рассматриваются основные конструкции языков программирования, анализируются основные типы и структуры данных,...

Учебная программа курса или дисциплины «Дискретные структуры» iconУчебная программа курса или дисциплины «Компьютерные сети»
Тема html понятие языка разметки. Общая структура документа. Метаинформация. Составные документы

Учебная программа курса или дисциплины «Дискретные структуры» iconРабочая учебная программа дисциплины 4 Цели и задачи курса 4 Цель...
Автор учебного методического комплекса кандидат политических наук, доцент Евлампиева Екатерина Владимировна

Учебная программа курса или дисциплины «Дискретные структуры» iconРабочая учебная программа дисциплины > Цели и задачи курса Курс лекций «Психическая травма»
Методические указания студенту по изучению дисциплины и организации самостоятельной работы 6

Учебная программа курса или дисциплины «Дискретные структуры» iconРабочая учебная программа дисциплины > 1 Цели и задачи курса Курс...
Методические указания студенту по изучению дисциплины и организации самостоятельной работы 10

Учебная программа курса или дисциплины «Дискретные структуры» iconРабочая учебная программа дисциплины > 1 Цели и задачи курса Курс...
Методические указания студенту по изучению дисциплины и организации самостоятельной работы 9

Учебная программа курса или дисциплины «Дискретные структуры» iconУчебная программа курса или дисциплины «Технологии создания Интернет-узлов»
Тема Адресация в Internet. Адресация сетей, подсетей и устройств ("хостов"). Класс-ориентированная и бесклассовая адресация. Адресация...

Учебная программа курса или дисциплины «Дискретные структуры» iconУчебная программа курса или дисциплины «Технологии баз данных»
Цель дисциплины “Технологии баз данных” ознакомление слушателей с организацией, принципами построения и функционирования современных...

Учебная программа курса или дисциплины «Дискретные структуры» iconРабочая учебная программа дисциплины пс рупд рабочая Учебная программа дисциплины
Комплексное обеспечение информационной безопасности автоматизированных систем. 15

Учебная программа курса или дисциплины «Дискретные структуры» iconУчебная программа курса или дисциплины «Тестирование конформности и формальные языки»
Концепция тестирования конформности системы ит стандартам и профилям. Постановка задачи тестирования конформности системы в рамках...



Образовательный материал



При копировании материала укажите ссылку © 2013
контакты
lit-yaz.ru
главная страница