Дискретная математика (2 часть из 2) Специальность: 230115 Программирование в компьютерных системах



Скачать 35.77 Kb.
Дата04.07.2013
Размер35.77 Kb.
ТипЗадача
МОСКОВСКИЙ ФИНАНСОВО-ЮРИДИЧЕСКИЙ УНИВЕРСИТЕТ
Согласовано

Начальник УМО СПО

______________ О. Ю. Якубовская

« ____» ________________ 2011 г.
Дисциплина: Дискретная математика (2 часть из 2)

Специальность: 230115 Программирование в компьютерных системах

Форма обучения: очная

Форма отчетности: зачет

Форма аттестации: традиционно

Оценка знаний: балл
Вопросы для подготовки к зачету


  1. Понятие неориентированного графа. Способы задания графа. Матрицы смежности. Путь в графе. Цикл в графе. Связный граф. Компоненты связности графа. Степень вершины. Теорема о сумме степеней вершин графа. Полный граф, формула количества ребер в полном графе.

  2. Методика выделения компонент связности в графе. Мосты и разделяющие вершины. Расстояние между вершинами в графе: определение, свойства, методика нахождения.

  3. Изоморфные графы. Методика проверки пары графов на изоморфность.

  4. Эйлеровы графы. Теорема Эйлера. Методика нахождения эйлерова цикла в эйлеровом графе. Гамильтоновы графы.

  5. Плоские графы. Соотношение между количествами вершин, ребер и граней в плоском графе.

  6. Деревья и их свойства. Задача выделения минимального графа-дерева.

  7. Алгоритм Краскала.

  8. Понятие ориентированного графа (орграфа). Способы задания орграфа. Матрица смежности для орграфа. Степень входа и степень выхода вершины. Источник. Сток. Ориентированный путь. Ориентированный цикл (контур). Матрицы смежности и инциденций для орграфа.

  9. Понятие достижимости одной вершины из другой вершины в орграфе. Множество достижимости вершины. Матрица достижимости. Эквивалентность (взаимодостижимость) вершин в орграфе.

  10. Задача о пути минимальной длины между вершинами орграфа. Алгоритм Форда.

  11. Эйлеровы орграфы. Критерий эйлеровости орграфа. Гамильтоновы орграфы.

  12. Понятие ориентированного дерева. Понятие бинарного дерева. Дисбаланс вершины в бинарном дереве. Кодирование бинарных деревьев.


Контрольные задания


  1. Выполнять операции над множествами.

  2. Решать задачи на подсчет количества элементов с использованием формулы количества элементов в объединении нескольких конечных множеств.

  3. Строить таблицы истинности для формул логики;

  4. Упрощать формулы логики с помощью равносильных преобразований;

  5. Проверять равносильность 2-х формул логики.

  6. Представлять булеву функцию в виде совершенной ДНФ.

  7. Представлять булеву функцию в виде совершенной КНФ.

  8. Моделировать булеву функцию с помощью релейно-контактной схемы.

  9. Записывать область истинности предиката.

  10. Определять логическое значение для высказываний типов gif" name="object1" align=absmiddle width=67 height=19>; ; ; .

  11. Выделять в предикатной формуле свободные и связанные переменные.

  12. Строить отрицания к предикатам, содержащим кванторные операции.

  13. Формализовывать предложения с помощью логики предикатов.

  14. Выполнять операции над отображениями, подстановками и вычетами по модулю N.

  15. Выделять структурные особенности отображений и подстановок.

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

  17. Генерировать двоичные слова заданной длины.

  18. Генерировать элементы декартова произведения множеств.

  19. Генерировать перестановки заданной длины.

  20. Генерировать k-элементные подмножества заданного множества.

  21. Генерировать все подмножества заданного множества.

  22. Записывать матрицу смежности для графа.

  23. Находить количество ребер в графе (с помощью теоремы о сумме степеней вершин графа).

  24. Выделять компоненты связности в графе.

  25. Определять, является ли данное ребро мостом или является ли данная вершина разделяющей.

  26. Находить расстояние между двумя вершинами в графе.

  27. Выделять из данного графа граф-дерево с минимальной суммарной длиной ребер.

  28. Проверять, является ли данный граф эйлеровым, находить эйлеров цикл в эйлеровом графе.

  29. Записывать матрицу смежности для орграфа, находить степени входа и выхода вершин, выделять в орграфе источники и стоки.

  30. Находить множество достижимости вершины в орграфе, записывать матрицу достижимости орграфа.

  31. Проверять, является ли данный орграф эйлеровым.

  32. Находить путь минимальной длины между источником и стоком в орграфе.


Вопросы обсуждены и одобрены на заседании предметной (цикловой) комиссии «Математических, информационных, технических дисциплин»

Протокол №1 от «28» августа 2009 г.

Председатель ПЦК _____________________________ Н. Е. Саввушкина

Похожие:

Дискретная математика (2 часть из 2) Специальность: 230115 Программирование в компьютерных системах iconРезультаты Изучения Рынка труда гоу спо профессиональным колледжем г. Новокузнецка
Информатика и вычислительная техника (230115 Программирование в компьютерных системах)
Дискретная математика (2 часть из 2) Специальность: 230115 Программирование в компьютерных системах iconСписок абитуриентов Учебный год: 2012 / 2013 Волна: 1 Организация: Пермский филиал На дату: 13 августа 2012
Специальность: Программирование в компьютерных системах. Программа обучения: На базе 9 классов
Дискретная математика (2 часть из 2) Специальность: 230115 Программирование в компьютерных системах iconСписок абитуриентов Учебный год: 2012 / 2013 Волна: 1 Организация: Пермский филиал На дату: 13 августа 2012
Специальность: Программирование в компьютерных системах. Программа обучения: На базе 9 классов
Дискретная математика (2 часть из 2) Специальность: 230115 Программирование в компьютерных системах iconПрограмма наименование дисциплины: Дискретная математика, математическая логика и их приложения в информатике и компьютерных науках
Наименование дисциплины: Дискретная математика, математическая логика и их приложения в информатике и компьютерных науках
Дискретная математика (2 часть из 2) Специальность: 230115 Программирование в компьютерных системах iconПрограммирование в компьютерных системах
Очную бюджетную форму обучения по программам среднего профессионального образования
Дискретная математика (2 часть из 2) Специальность: 230115 Программирование в компьютерных системах iconПрограммирование в компьютерных системах
Книги по программированию, исходники, компоненты, статьи и обзоры по всем языкам программирования
Дискретная математика (2 часть из 2) Специальность: 230115 Программирование в компьютерных системах iconРабочая учебная программа По дисциплине: Криптографические методы защиты информации в компьютерных системах и сетях По направлению: 010900 «Прикладные математика и физика»
По дисциплине: Криптографические методы защиты информации в компьютерных системах и сетях
Дискретная математика (2 часть из 2) Специальность: 230115 Программирование в компьютерных системах iconДискретная математика
Ф50 Дискретная математика: сборник задач / Сост. И. В. Тимофеев. Красноярск: ипц кгту, 2003. 35 с
Дискретная математика (2 часть из 2) Специальность: 230115 Программирование в компьютерных системах iconС. Б. Дискретная математика. Изд-во мгту им. Н. Э. Баумана, 2004. Бородин О. В. Дискретная математика: Учебное Пособие
Белоусов А. И., Ткачев С. Б. Дискретная математика. Изд-во мгту им. Н. Э. Баумана, 2004
Дискретная математика (2 часть из 2) Специальность: 230115 Программирование в компьютерных системах iconПрограмма дисциплины «Дискретная математика»
...
Разместите кнопку на своём сайте:
ru.convdocs.org


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