Рабочая программа "Дискретная математика"
рабочая программа
Дискретная математика
Скачать:
| Вложение | Размер |
|---|---|
 rabochaya_programma_op.08_diskretnaya_matematika_2019-2020_goda.docx | 65.99 КБ |
Предварительный просмотр:
РОССОШАНСКИЙ ФИЛИАЛ ГОСУДАРСТВЕННОГО БЮДЖЕТНОГО
ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАТЕЛЬНОГО УЧРЕЖДЕНИЯ
ВОРОНЕЖСКОЙ ОБЛАСТИ
« ГУБЕРНСКИЙ ПЕДАГОГИЧЕСКИЙ КОЛЛЕДЖ»
«Утверждаю»
Зам. директора по учебной работе
ГБПОУ ВО «ГПК»
___________________/О.В. Даниленко/
«___» ________________20___ г.
Рабочая программа
учебной дисциплины
ОП.08 Дискретная математика
по специальности СПО
09.02.01 Компьютерные системы и комплексы
(базовый уровень подготовки для специальности СПО)
Россошь
2019
Рабочая программа учебной дисциплины разработана на основе Федерального государственного образовательного стандарта (далее – ФГОС) по специальности среднего профессионального образования (далее СПО) 09.02.01 Компьютерные системы и комплексы
Организация-разработчик: Россошанский филиал ГБПОУ ВО «Губернский педагогический колледж».
Разработчик: Воронько Пётр Владимирович преподаватель математики.
СОДЕРЖАНИЕ
- ПАСПОРТ ПРОГРАММЫ УЧЕБНОЙ ДИСЦИПЛИНЫ
стр. 4
- СТРУКТУРА И СОДЕРЖАНИЕ УЧЕБНОЙ 5
ДИСЦИПЛИНЫ
- УСЛОВИЯ РЕАЛИЗАЦИИ ПРОГРАММЫ 10
УЧЕБНОЙ ДИСЦИПЛИНЫ
- КОНТРОЛЬ И ОЦЕНКА РЕЗУЛЬТАТОВ 11
ОСВОЕНИЯ УЧЕБНОЙ ДИСЦИПЛИНЫ
1. ПАСПОРТ ПРОГРАММЫ УЧЕБНОЙ ДИСЦИПЛИНЫ
Дискретная математика
1.1. Область применения рабочей программы
Рабочая программа дисциплины является частью основной профессиональной образовательной программы в соответствии с ФГОС по специальности (специальностям) СПО 09.02.01 Компьютерные системы и комплексы.
1.2. Место дисциплины в структуре основной профессиональной образовательной программы:
дисциплина ОП Дискретная математика входит в математический и общий естественнонаучный цикл.
Дисциплина «Дискретная математика» относится к циклу Математический и естественнонаучный цикл, Базовая часть. Входные знания, умения и компетенции студентов должны соответствовать школьному уровню и знаниям и компетенциям, полученными после изучения дисциплин «Математика», «Математический анализ» и «Теория вероятностей и математическая статистика». Дисциплина «Дискретная математика» является предшествующей для следующих дисциплин:
«Системы поддержки принятия решений», «Вычислительные системы, сети и коммуникации», «Информационные системы и технологии», «Проектирование информационных систем».
1.3. Цели и задачи дисциплины – требования к результатам освоения дисциплины:
Накопление необходимого запаса сведений по математике (основные определения, теоремы, правила), а также освоение математического аппарата, помогающего моделировать, анализировать и решать задачи, связанные с информатикой, помощь в усвоении математических методов, дающих возможность изучать и прогнозировать процессы и явления из области будущей деятельности студентов; развитие логического и алгоритмического мышления, способствование формированию умений и навыков самостоятельного анализа исследования проблем информатики, развитию стремления к научному поиску путей совершенствования своей работы.
В результате изучения дисциплины студент должен знать:
- основные понятия и факты теории множеств, комбинаторного анализа, общей алгебры, теории графов, математической логики, сетевого планирования, теории потоков в сетях;
- уметь:
- разрабатывать эффективные алгоритмы и отлаживать программы с использованием современных компьютерных технологий;
- применять методы анализа прикладной области на концептуальном, логическом, математическом и алгоритмическом уровнях;
- иметь навыки:
- моделирования прикладных задач методами дискретной математики.
В результате освоения дисциплины обучающийся должен обладать компетенциями:
ОК 1. Понимать сущность и социальную значимость своей будущей профессии, проявлять к ней устойчивый интерес.
ОК 2. Организовывать собственную деятельность, выбирать типовые методы и способы выполнения профессиональных задач, оценивать их эффективность и качество.
ОК 3. Принимать решения в стандартных и нестандартных ситуациях и нести за них ответственность.
ОК 4. Осуществлять поиск и использование информации, необходимой для эффективного выполнения профессиональных задач, профессионального и личностного развития.
ОК 5. Использовать информационно-коммуникационные технологии в профессиональной деятельности.
ОК 6. Работать в коллективе и команде, эффективно общаться с коллегами, руководством, потребителями.
ОК 7. Брать на себя ответственность за работу членов команды (подчиненных), результат выполнения заданий.
ОК 8. Самостоятельно определять задачи профессионального и личностного развития, заниматься самообразованием, осознанно планировать повышение квалификации.
ОК 9. Ориентироваться в условиях частой смены технологий в профессиональной деятельности.
ПК 1.1. Разрабатывать схемы цифровых устройств на основе интегральных схем разной степени интеграции.
ПК 1.3. Использовать средства и методы автоматизированного проектирования при разработке цифровых устройств.
1.4. Рекомендуемое количество часов на освоение программы учебной дисциплины:
максимальной учебной нагрузки обучающегося 135 часов, в том числе:
- обязательной аудиторной учебной нагрузки обучающегося 90 часа;
- самостоятельной работы обучающегося 45 часов.
- СТРУКТУРА И ПРИМЕРНОЕ СОДЕРЖАНИЕ УЧЕБНОЙ ДИСЦИПЛИНЫ
- Объем учебной дисциплины и виды учебной работы
Вид учебной работы | Объем часов |
Максимальная учебная нагрузка (всего) | 135 |
Обязательная аудиторная учебная нагрузка (всего) | 90 |
в том числе: | |
лабораторные занятия | - |
практические занятия | 44 |
контрольные работы | - |
курсовая работа (проект) (не предусмотрено) | - |
Самостоятельная работа обучающегося (всего) | 45 |
в том числе: | |
самостоятельная работа над курсовой работой (проектом) (не предусмотрено) | - |
Итоговая аттестация в форме дифференцированного зачета | |
- Примерный тематический план и содержание учебной дисциплины «Дискретная математика»
Наименование разделов и тем | Содержание учебного материала, лабораторные и практические работы, самостоятельная работа обучающихся, курсовая работ (проект) (если предусмотрены) | Объем часов | |
1 | 2 | 3 | |
Введение | Содержание учебного материала | 2 | |
Предмет, цели и задачи учебной дисциплины. Межпредметные связи. Роль учебной дисциплины в профессиональной деятельности. Основные понятия и приемы дискретной математики. | |||
Раздел 1. Формулы логики | 15 | ||
Тема 1.1 Логические операции. Формулы логики. | Содержание учебного материала | 6 | |
1 | Понятие высказывания. Основные логические операции (дизъюнкция, произведение (конъюнкция), импликация, эквиваленция, отрицание). Понятие формулы логики. Таблица истинности и методика ее построения. Тождественно-истинные формулы. Понятие элементарного произведения; понятие дизъюнктивной нормальной формы (ДНФ). Методика построения таблицы истинности для ДНФ упрощенным методом. Понятия элементарной дизъюнкции и конъюнктивной нормальной формы (КНФ). | ||
Лабораторные и практические работы (не предусмотрены) | - | ||
Самостоятельная работа обучающихся Построение таблицы истинности для формулы логики. | 5 | ||
Тема 1.2. Законы логики. Равносильные преобразования | Содержание учебного материала | 4 | |
1 | Равносильные формулы. Законы логики. Методика упрощения формул логики с помощью равносильных преобразований. | ||
Лабораторные и практические работы (не предусмотрены) | - | ||
Практические занятия Упрощение формул логики с помощью равносильных преобразований. | 4 | ||
Контрольные работы | 1 | ||
Самостоятельная работа обучающихся(не предусмотрены) | - | ||
Раздел 2. Булевы функции | 20 | ||
Тема 2.1. Функции алгебры логики. Операция двоичного сложения. | Содержание учебного материала | 4 | ||
Понятие булева вектора (двоичного вектора). Соседние векторы. Противоположные векторы. Единичный N-мерный куб. Понятие булевой функции (функции алгебры логики). Способы задания булевой функции. Проблема представления булевой функции в виде формулы логики. Понятие совершенной ДНФ. Методика представления булевой функции в виде совершенной ДНФ. Понятие совершенной КНФ. Методика представления булевой функции в виде совершенной КНФ. Понятие минимальной ДНФ. Операция двоичного сложения и ее свойства. Многочлен Жегалкина. | ||||
Лабораторные работы (не предусмотрены) | - | |||
Практические занятия Представление булевой функции в виде совершенной ДНФ, совершенной КНФ, минимальной ДНФ. | 6 | |||
Контрольные работы (не предусмотрены) | - | |||
Самостоятельная работа обучающихся (не предусмотрены) | - | |||
Тема 2.2. Полнота множества функций. Важнейшие замкнутые классы. | Содержание учебного материала | 5 | ||
1 | Понятие выражения одних булевых функций через другие. Проблема возможности выражения одних булевых функций через другие. Полнота множества функций. Замыкание множества функций. Понятие замкнутого класса функций. Важнейшие замкнутые классы: Т0 (класс функций, сохраняющих константу 0), Т1 (класс функций, сохраняющих константу 1), S (класс самодвойственных функций), L (класс линейных функций), M (класс монотонных функций). Теорема Поста. Шефферовские функции. Функция Шеффера и функция Пирса как простейшие шефферовские функции. | |||
Лабораторные работы (не предусмотрены) | - | |||
Практические занятия Проверка булевой функции на принадлежность к классам Т0, Т1, S, L, M; проверка множества булевых функций на полноту. | 4 | |||
Контрольные работы | 1 | |||
Самостоятельная работа обучающихся Представление булевой функции в виде многочлена Жегалкина. | 5 | |||
Раздел 3. Основы теории множеств | 10 | |||
Тема 3.1. Основы теории множеств | Содержание учебного материала | 5 | |||
1 | Понятие множества. Конечные и бесконечные множества, пустое множество. Подмножество; количество подмножеств конечного множества. Теоретико-множественные диаграммы. Операции над множествами (объединение, пересечение, дополнение, теоретико-множественная разность) и их свойства. Соответствующая формула для трех множеств. Декартово произведение множеств. Декартова степень множества. Соответствие между теоретико-множественными и логическими операциями. Методика проверки теоретико-множественных соотношений с помощью формул логики. | ||||
Лабораторные работы (не предусмотрены) | - | ||||
Практические занятия Решение задач на выполнение теоретико-множественных операций и на подсчет количества элементов. | 4 | ||||
Контрольные работы | 1 | ||||
Самостоятельная работа обучающихся. Выполнение теоретико-множественных операций. | 7 | ||||
Раздел 4. Предикаты. Бинарные отношения | 12 | ||||
Тема 4.1. Предикаты. Бинарные отношения | Содержание учебного материала | 5 | |||
1 | Понятие предиката. Область определения и область истинности предиката. Обычные логические операции над предикатами. Кванторные операции над предикатами. Понятие предикатной формулы; свободные и связанные переменные. Построение отрицаний к предикатам, содержащим кванторные операции. Формализация предложений с помощью логики предикатов. Понятие бинарного отношения; примеры бинарных отношений. Диаграмма бинарного отношения. Рефлексивные, симметричные, транзитивные бинарные отношения. Отношение эквивалентности; теорема о разбиении множества на классы эквивалентности. | ||||
Лабораторные работы (не предусмотрены) | - | ||||
Практические занятия Определение логического значения для высказываний типов построение отрицаний к предикатам; формализация предложений с помощью логики предикатов. | 6 | ||||
Контрольные работы | 1 | ||||
Самостоятельная работа обучающихся Построение диаграммы бинарного отношения | 10 | ||||
Раздел 5. Основы теории графов | 14 | ||||
Тема 5.1. Неориентированные и ориентированные графы | Содержание учебного материала | 5 | |||
1 | Понятие неориентированного графа. Способы задания графа. Матрица смежности. Путь в графе. Цикл в графе. Связный граф. Компоненты связности графа. Степень вершины. Теорема о сумме степеней вершин графа. Полный граф; формула количества рёбер в полном графе. Мосты и разделяющие вершины (точки сочленения). Расстояние между вершинами в графе: определение, свойства, методика нахождения. Эксцентриситет вершины. Радиус и диаметр графа. Центральные вершины. Изоморфные графы. Методика проверки пары графов на изоморфность. Эйлеровы графы. Теорема Эйлера (критерий эйлеровости графа). Методика нахождения эйлерова цикла в эйлеровом графе. Плоские графы. Грани плоской укладки плоского графа. Соотношения между количествами вершин, рёбер и граней в плоском графе. Примеры неплоских графов. Деревья и их свойства. Понятие ориентированного графа (орграфа). Способы задания орграфа. Матрица | ||||
смежности для орграфа. Степень входа и степень выхода вершины. Источник. Сток. Ориентированный путь. Ориентированный цикл (контур). Понятие достижимости одной вершины из другой вершины в орграфе. Множество достижимости вершины. Матрица достижимости. Эквивалентность (взаимодостижимость) вершин в орграфе. Классы эквивалентных вершин. Диаграмма Герца. Бесконтурные орграфы. Теорема о существовании источника и стока в бесконтурном орграфе. Эйлеровы орграфы. Критерий эйлеровости орграфа. Гамильтоновы орграфы. Понятие ориентированного дерева. Понятие бинарного дерева. Дисбаланс вершины в бинарном дереве. Кодирование бинарных деревьев. | |||||
Лабораторные работы (не предусмотрены) | - | ||||
Практические занятия Проверка графа на эйлеровость, гамильтоновость, плоскость. Запись матрицы достижимости и построение диаграммы Герца для ориентированного графа; решение задач на бинарные деревья. | 8 | ||||
Контрольные работы | 1 | ||||
Самостоятельная работа обучающихся. Понятие бинарного дерева сортировки, методика его построения для заданной последовательности поступающих элементов, использование его для организации хранения и поиска информации. | 8 | ||||
Примерная тематика курсовой работы (проекта) (не предусмотрены) | - | ||||
Самостоятельная работа обучающихся над курсовой работой (проектом) (не предусмотрены) | - | ||||
Раздел 6. Элементы теории конечных автоматов | 17 | ||||
Тема 4.1. Теория конечных автоматов и ее применение. | Содержание учебного материала | 4 | |||
1 | Алгебраическая теория конечных автоматов. Распознающие автоматы. Минимизация конечных автоматов. Структурная теория конечных автоматов. Декомпозиция конечных автоматов. Применение теории конечных автоматов. Определение основной модели. | ||||
Лабораторные работы (не предусмотрены) | - | ||||
Практические занятия «Решение задач по теории конечных автоматов. Алгебраическая теория конечных автоматов». «Решение задач по теории конечных автоматов. Структурная теория конечных автоматов». «Решение задач по теории конечных автоматов. Основная модель» «Алгоритмическая система Поста». «Способы представления автоматов». | 12 | ||||
Контрольные работы | 1 | ||||
Самостоятельная работа обучающихся Автоматы Миля и Мура и их эквивалентность. Декомпозиция конечных автоматов. Дизъюнктивные нормальные формы. Таблицы, графы и матрицы переходов. | 10 | ||||
- УСЛОВИЯ РЕАЛИЗАЦИИ ПРОГРАММЫ ДИСЦИПЛИНЫ
- Требования к минимальному материально-техническому обеспечению
Реализация программы модуля предполагает наличие учебного кабинета «Математика», кабинета «Информатики», библиотеки с читальным залом с выходом в сеть Интернет.
Оборудование учебного кабинета «Математика»: стенды, плакаты, раздаточный материал.
Технические средства обучения: вычислительная техника, ПК, проектор, CD/DVD, аудиотехника.
- Информационное обеспечение обучения
Перечень рекомендуемых учебных изданий, Интернет-ресурсов, дополнительной литературы
Литература
Основные источники:
- Валуцэ И.И. Математика для техникумов. – М.: Наука, 1990
- Григорьев В.П. Элементы высшей математики. Учебник. - М.: Академия, 2010. Допущено МО РФ
- Григорьев В.П., Сабурова Т.Н. Сборник задач по высшей математике 1-е изд. – М. : «Академия», 2010. Допущено МО РФ
- Омельченко В.П. Математика. Учебное пособие. Ростов-н/Д: Феникс, 2008. Допущено МО РФ
- Пехлецкий И.Д. Математика: учебник. – М., 2003.
- Спирина М.С., Спирин П.А. Дискретная математика. Учебник для ССУЗов, 6-е изд., стер. «Академия»,2010. Допущено МО РФ в качестве учебника
Дополнительные источники:
- Афанасьева О.В. Математика для техникумов на базе среднего образ.: Уч.пос. 2005
- Богомолов Н.В. Математика: Учебник для ссузов. - М.: Дрофа, 2010
- Выгодский М.Я. Справочник по высшей математике. –М.: Наука,2005.
- Выгодский М.Я. Справочник по элементарной математике. –М.: Наука,2005.
- Данко П.Е., Попов А.Г., Кожевников Т.Я. Высшая математика в упражнениях и задачах. ( В 2-х частях ) Учебное пособие для студентов втузов. – 6-е изд. – М. : «Мир и образование», 2007.
- Ерусалимский Я.М. Дискретная математика: теория, задачи, приложения.
–М.: Вузовская книга, 2000
- Колягин Ю.М., Ткачева М.В, Федерова Н.Е. и др. под ред. Жижченко А.Б. Алгебра и начала математического анализа (базовый и профильный уровни). 10 кл. – М., 2005.
- Лисичкин В.Т., Соловейчик И.Л. Математика. – М.: Высшая школа, 1991.
- Редькин Н. П. Дискретная математика. – СПб.: Лань, 2003. Допущено МО РФ
10.Соболь Б.В. Практикум по высшей математике. Ростов н/Д, Феникс, 2007г. Допущено МО РФ
11.Филимонова Е.В. Математика для ссуз Ростов-н/Д, 2005 гриф: Рекомендовано МО РФ
Интернет-ресурсы:
- Собрание книг и публикаций по различным разделам математике, форум по решению задач(требуется регистрации) − http://e-science.ru/math/
- Образовательный сайт по математике. Представляет собой сборник часто встречаемых задач по математике (алгебре, геометрии, математическому анализу, теории вероятностей и т.д.) и решений этих задач. Цель сайта - помочь учащимся решить задачи, проверить свое решение − http://www.math.by/
- Собрание оригинальных исследовательских работ, обзорных научных статей, кратких сообщений из всех областей фундаментальной и прикладной математики − http://mech.math.msu.su/
- Практический сайт содержит этюды, выполненные с использованием современной компьютерной 3D-графики, увлекательно и интересно рассказывающие о математике и ее приложениях − http://www.etudes.ru/
4. КОНТРОЛЬ И ОЦЕНКА РЕЗУЛЬТАТОВ ОСВОЕНИЯ ДИСЦИПЛИНЫ
Контроль и оценка результатов освоения дисциплины осуществляется преподавателем в процессе проведения практических занятий и лабораторных работ, тестирования, а также выполнения обучающимися индивидуальных заданий, проектов, исследований.
Результаты обучения (освоенные умения, усвоенные знания) | Формы и методы контроля и оценки результатов обучения |
Знать основные логические операции; понятия: формулы логики, таблицы истинности формулы логики и методику ее построения, тождественно-истинной формулы; дизъюнктивной нормальной формы (ДНФ), упрощенную методику построения таблицы истинности для ДНФ; понятие конъюнктивной нормальной формы (КНФ). | Тестирование, фронтальный (индивидуальный) опрос, самостоятельная работа |
Знать понятие равносильности двух формул логики; законы логики; методику упрощения формул логики с помощью равносильных преобразований. | Тестирование, фронтальный (индивидуальный) опрос, самостоятельная работа |
Уметь упрощать формулу логики с помощью равносильных преобразований. | Письменная работа, тестирование, практическая работа |
Знать понятия булева вектора, соседних и противоположных булевых векторов; единичного N- мерного куба; булевой функции (функции алгебры логики) и способы ее задания; совершенной ДНФ, методику представления булевой функции в виде совершенной ДНФ; понятие совершенной КНФ, | Тестирование, фронтальный (индивидуальный) опрос, самостоятельная работа |
методику представления булевой функции в виде совершенной КНФ; минимальной ДНФ, методику представления булевой функции (N 3) в виде минимальной ДНФ графическим методом; | |
Уметь изображать единичный N-мерный куб (с разметкой вершин булевыми векторами) в случаях N = 1, 2, 3; представлять булеву функцию в виде: совершенной ДНФ, совершенной КНФ, минимальной ДНФ графическим методом. | Тестирование, практическая работа, письменная работа |
Знать операцию двоичного сложения и ее свойства; методику представления булевой функции в виде многочлена Жегалкина. | Тестирование, фронтальный (индивидуальный) опрос, самостоятельная работа |
Знать понятия: выражения одних булевых функций через другие, полноты множества функций, замкнутого класса, важнейшие замкнутые классы: Т0, Т1, S, L, М (определения этих классов, методику проверки булевой функции на принадлежность к этим классам); теорему Поста; понятие шефферовской функции; условие того, что функция является шефферовской; функции Шеффера и Пирса. | Тестирование, фронтальный (индивидуальный) опрос, самостоятельная работа |
Уметь проверять булеву функцию на принадлежность к классам Т0, Т1, S, L, М; проверять множество булевых функций на полноту (с помощью теоремы Поста); проверять, является ли функция шефферовской. | Письменная работа, тестирование, практическая работа |
Знать понятия множества и подмножества; формулу количества подмножеств конечного множества; операции над множествами (объединение, пересечение, дополнение, разность, декартово произведение, декартова степень) и их свойства; формулу количества элементов в объединении нескольких (двух, трех) конечных множеств; соответствие между теоретико- множественными и логическими операциями; методику проверки теоретико-множественных соотношений с помощью формул логики. | Тестирование, фронтальный (индивидуальный) опрос, самостоятельная работа |
Уметь применять теоретико-множественные диаграммы; выполнять операции над множествами; решать задачи на подсчет количества элементов с использованием формулы количества элементов в объединении нескольких конечных множеств; проверять теоретико- множественные соотношения с помощью формул логики. | Тестирование, фронтальный (индивидуальный) опрос, самостоятельная работа |
Знать понятия предиката, области определения и области истинности предиката; операции над предикатами (обычные логические и кванторные); понятие предикатной формулы, понятия свободной переменной и связанной переменной; методику построения отрицаний к предикатам, содержащим кванторные операции; понятия рефлексивного бинарного отношения, симметричного бинарного отношения, транзитивного бинарного отношения, отношения эквивалентности, теорему о разбиении множества на классы эквивалентности. | Тестирование, фронтальный (индивидуальный) опрос, самостоятельная работа |
Уметь записывать область истинности предиката; определять логическое значение для высказываний типов x P(x), x P(x), x y P(x, y), x y P(x, y); выделять в предикатной формуле свободные переменные | Письменная работа, практическая работа, индивидуальный опрос |
и связанные переменные; строить отрицания к предикатам, содержащим кванторные операции; формализовывать предложения с помощью логики предикатов. | |
Знать понятие неориентированного графа и основные определения, связанные с ним; теорему о сумме степеней вершин графа; формулу количества ребер в полном графе; алгоритм фронта волны в графе; методику выделения компонент связности в графе; понятие моста и разделяющей вершины; понятие расстояния между вершинами в графе и методику его нахождения; понятия эксцентриситета вершины, радиуса графа, диаметра графа, центральной вершины; понятие двудольного графа, методику проверки графа на двудольность, понятие полного двудольного графа; понятие изоморфности двух графов, методику проверки пары графов на изоморфность; понятие эйлерова графа, теорему Эйлера, методику нахождения эйлерова цикла в эйлеровом графе; понятие гамильтонова графа, плоского графа; соотношения между количествами вершин, рёбер и граней в плоском графе; простейшие примеры неплоских графов; понятие дерева, свойства деревьев. | Тестирование, фронтальный (индивидуальный) опрос, самостоятельная работа |
Уметь записывать матрицу смежности для графа; находить количество рёбер в графе (с помощью теоремы о сумме степеней вершин графа); выделять компоненты связности в графе; определять, является ли данное ребро мостом или является ли данная вершина разделяющей; находить расстояние между двумя вершинами в графе; находить эксцентриситеты вершин, радиус и диаметр графа; проверять, является ли данный граф двудольным; проверять, являются ли два данных графа изоморфными (в простейших случаях); проверять, является ли данный граф эйлеровым; находить эйлеров цикл в эйлеровом графе; проверять, является ли данный граф гамильтоновым (в простейших случаях); проверять, является ли данный граф плоским (в простейших случаях); записывать для дерева с пронумерованными вершинами его код Пруфера; восстанавливать по коду Пруфера дерево с пронумерованными вершинами. | Письменная работа, тестирование, практическая работа |
Знать понятие ориентированного графа (орграфа) и основные определения, связанные с ним; понятие достижимости вершин в орграфе, методику записи матрицы достижимости орграфа; понятие эквивалентности вершин в орграфе, методику построения диаграммы Герца для орграфа, понятие сильносвязного орграфа; понятие бесконтурного орграфа, теорему о существовании источника и стока в бесконтурном орграфе; понятие эйлерова орграфа, критерий эйлеровости орграфа; понятие гамильтонова орграфа; понятие ориентированного дерева; понятие бинарного дерева, понятие дисбаланса вершины в бинарном дереве; кодирование бинарных деревьев; понятие бинарного дерева сортировки, методику его построения, использование его для организации хранения и поиска информации. | Тестирование, фронтальный (индивидуальный) опрос, самостоятельная работа |
Уметь записывать матрицу смежности для орграфа, находить степени входа и выхода вершин, выделять в орграфе источники и стоки; находить множество достижимости вершины в орграфе, записывать матрицу достижимости орграфа; выделять классы эквивалентных вершин в орграфе, строить для орграфа его диаграмму Герца; проверять, является ли данный орграф эйлеровым; проверять, является ли данный орграф гамильтоновым (в простейших случаях); находить дисбаланс вершины в бинарном дереве; записывать код бинарного дерева; по коду восстанавливать бинарное дерево; строить бинарное дерево сортировки для заданной последовательности поступающих элементов. | Письменная работа, тестирование, практическая работа |
По теме: методические разработки, презентации и конспекты
Рабочая программа по математике для 1-3 курса
Данная рабочая программа может быть применена для специальностей: повар, парикмахер и другие...
рабочая программа по математике для 1 курса НПО
Рабочая программа создана с учетом ФГОС второго поколения, содержит КИМ и учебно-тематический план...
РАБОЧАЯ ПРОГРАММА ПО МАТЕМАТИКЕ НПО "ЭЛЕКТРИК СУДОВОЙ"
Рабочая программа по математике на 2 курса, разработанная в соответствии с государственными стандартами для начального профессионального образования....
Рабочая программа по математике в коррекционной группе
Пояснительная записка Рабочая программа по математике для учащихся коррекционной группы составлена на основе Программы специальны...
Рабочая программа по математике на 290 часов для группы социально-экономического профиля 101101 Гостиничный сервис.
Рабочая программа ФГОС 3 поколения составлена для изучения математики на 1 курсе и охватывает материал 10-11 класса общеобразовательной школы...
Рабочая программа Дискретная математика с элементами математической логики
Рабочая программа Дискретная математика с элементами математической логики для специальности 09.02.07 Информационные системы и программирование...