Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

'Документ'
1. Назначается из числа заместителей директора и педагогических работников школы; подчиняется непосредственно директору школы; дежурит по графику, утв...полностью>>
'Урок'
Реализация межпредметных связей в учебном процессе создает условия для целостного восприятия единой научной картины мира. Их знание помогает учителю о...полностью>>
'Документ'
В.-председатель Лешукова А.Э. Маковецкая О.Ю. 8. ИСТОРИЯ ( -11 класс) ОБЩЕСТВОЗНАНИЕ (8-11класс) КУБАНОВЕДЕНИЕ(8-11 класс) Право (8-11 ) Строева Л....полностью>>
'Документ'
Сыйлыктары, конференцияларга катышканы, коомдук уюмдарга мүчөлүгү – Сизге ыйгарылган сыйлыктарды, медалдарды, гранттарды, мелдештерге, конференцияларг...полностью>>

Главная > Методические рекомендации

Сохрани ссылку в одной из сетей:
Информация о документе
Дата добавления:
Размер:
Доступные форматы для скачивания:

Методические рекомендации по курсу

Б2.Б.2 Дискретная математика

подготовки бакалавриата 080500.62 «Бизнес-информатика»

Автор: Большакова Н.С., ст. преподаватель кафедры М и ММЭ

1. Цели и задачи курса, место дисциплины в структуре ООП ВПО, компетенции обучающегося, формируемые в результате освоения дисциплины.

Целями освоения дисциплины «дискретная математика» являются формирование систематизированных знаний в области высшей математики и основ информатики, о ее месте и роли в системе математических наук.

В результате освоения дисциплины обучающийся должен:

1) Знать:

- основные понятия дискретной математики;

- основные свойства графов и булевых функций, теоремы курса;

2) Уметь:

- строить матрицы смежности и инцидентности для графов, таблицы истинности булевых функций, сднф и скнф;

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

3) Владеть

- современными знаниями о дискретной математике и ее приложениях;

- основными понятиями дискретной математики.

Дисциплина «Дискретная математика» относится к базовой части профессионального цикла (Б2.Б.2).

Для освоения дисциплины «Дискретная математика» студенты используют знания, умения и виды деятельности, сформированные в процессе изучения предмета «Математика» и «Информатика» на предыдущем уровне образования.

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

Формируются компетенции:

  • Владением культурой мышления, способностью к обобщению, анализу, восприятию информации, постановке цели и выбору путей её достижения (ОК-1);

  • способностью использовать знания о современной естественнонаучной картине мира в образовательной и профессиональной деятельности, применять методы математической обработки информации, теоретического и экспериментального исследования (ОК-4);

  • готовностью использовать основные методы, способы и средства получения, хранения, переработки информации, готовностью работать с компьютером как средством управления информацией (ОК-8);

  • способностью работать с информацией в глобальных компьютерных сетях (ОК-9);

  • способностью понимать сущность и значение информации в развитии современного информационного общества, сознавать опасности и угрозы, возникающие в этом процессе, соблюдать основные требования информационной безопасности, в том числе защиты государственной тайны (ОК-12);

  • осознанием социальной значимости своей будущей профессии, обладанием мотивацией к осуществлению профессиональной деятельности (ОПК-1).

2. Структура курса.

Теория графов. Понятие графов. Операции с графами. Степени вершин графов. Способы задания графов. Маршруты, цепи, циклы. Эйлеровы графы. Гамильтоновы графы. Двудольные графы и жесткость ферм. Деревья. Коды Прюфера. Задача об остове минимального веса. Мультиграфы. Расстояния в графах.

Булевы функции. Функции алгебры логики. Формулы. Реализация функций формулами.

Эквивалентность формул. Свойства элементарных функций. Принцип двойственности. Разложение булевых функций по переменным. СДНФ и СКНФ.

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

№ п/п

Наименование
раздела, темы

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

Семестр,

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

Всего ауд.ч./в интеракт.ф.

ЛК

ПР/

СМ

ЛБ

Часов на СРС

1

Теория графов

21/13

8

13

21

1 семестр

зачет

2

Булевы функции

21/13

8

13

21

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

Основная

  1. Белов В. В. и др. Теория графов. – М.: Высш. Школа, 1976.

  2. Басакер Р., Саати Т. Конечные графы и сети. – М.: Наука, 1974.

  3. Судоплатов С. В., Овчинникова Е. В. Дискретная математика: Учебник. – М.: ИНФРА – М; Новосибирск: НГТУ, 2005.

  4. Берж К. Теория графов и ее применения. – М.: ИЛ, 1962.

  5. Зыков А. А. Теория конечных графов. – Новосибирск: Наука, 1969.

  6. Оре О. Теория графов. – М.: Наука,1968.

  7. Кузнецов О. П., Адельсон – Вельский Г. М. Дискретная математика для инженера. – М.: Энергия, 1980.

  8. Татт У. Теория графов: Пер. с англ. – М.: Мир,1988.

  9. Харари Ф. Теория графов. – М.: Мир, 1973.

  10. Яблонский С.В. Введение в дискретную математику. – М.: Наука, 1979.

  11. Игошин В. И. Задачник практикум по математической логике. – М.: Просвещение, 1986.

Дополнительная

  1. Оре. О. Графы и их применение. – М.: Мир, 1965.

  2. Уилсон Р. Введение в теорию графов. – М.: Мир, 1977.

  3. Березина Л. Ю. Графы и их применение: Пособие для учителей. – М.: Просвещение, 1979.

Электронные образовательные ресурсы (ЭОР)

1. /ru/library.htm — Электронная библиотека сайта EqWorld.

2.

3.

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

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

  1. Понятия теории графов.

  2. Операции с графами.

  3. Степени вершин графов.

  4. Способы задания графов.

  5. Маршруты, цепи, циклы.

  6. Эйлеровы графы.

  7. Гамильтоновы графы.

  8. Двудольные графы и жесткость ферм.

  9. Деревья.

  10. Коды Прюфера.

  11. Задача об остове минимального веса.

  12. Мультиграфы

  13. Понятие булевой функции.

  14. Понятие фиктивной переменной.

  15. Основные булевы функции от 1-ой и 2-х переменных.

  16. Понятие формулы над Р.

  17. Операция суперпозиции.

  18. Эквивалентность формул.

  19. Свойства элементарных функций.

  20. Принцип двойственности.

  21. Разложение булевых функций по переменным.

  22. СДНФ.

  23. СКНФ.

6. Примерная тематика практических занятий.

тема «Графы, их вершины, рёбра и дуги».

№1. Подбирается экипаж космического корабля из 3-х человек: командира, инженера и врача. Имеются 4 кандидата на должность командира к1, к2, к3, к4, 3 кандидата на должность инженера и1, и2, и3 и 3 кандидата на должность врача в1, в2, в3. Известно, что

  • к1 психологически совместим с и1, и3, в2, в3; к2  с и1, и2, в1, в2, в3;

  • к3  с и1, и2, в1, в3; к4  с и1, и2, и3, в2.

Кроме того, и1 психологически несовместим с в3, и2  с в1, и3  с в2.

Сколькими способами можно составить экипаж?

№2.Лист бумаги Плюшкин разрезает на три части. Некоторые из полученных листов он также разрезает на три части. Несколько новых листочков он вновь разрезает на три более мелких и т.д. сколько Плюшкин получает листочков бумаги, если разрезает к листов?

№3. Утверждают, что в одной компании из пяти человек каждый знаком с двумя и только с двумя другими. Возможна ли такая компания?

тема «Изоморфные графы».

1. Доказать, что графы изоморфные, построить изоморфизм графов.

2. Нарисуйте диаграммы всех неизоморфных неориентированных графов

а) с 3 вершинами (их четыре);

б) с 4 вершинами (их 11).

тема «Операции над графами »

Построить дополнение графа, объединение, соединение, композицию и произведение двух графов.

тема «Эйлеровы и гамильтоновы графы»

Построение эйлеровых и гамильтоновых циклов и цепей, применение их для решения прикладных задач (задача коммивояжёра).

тема «Способы задания псевдографов »

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

тема «Деревья и их свойства. »

1. Сколько ребер в деревьях:

а) с 6 и 12 вершинами;

б) с 7 и 15 вершинами.

2. Сколько рёбер следует удалить из связного графа F, имеющего т рёбер и n вершин, чтобы получить дерево, содержащее все вершины F?

3. Привести пример графа, из которого нельзя выделить дерево, содержащее все вершины графа.

4. С помощью алгоритма Прюфера восстановите по вектору дерево. Сделать проверку.

а) (3, 3, 7, 1, 1, 1); в) (7, 11, 11, 6, 6, 6, 2, 2, 10, 1);

б) (1, 2, 2, 4, 9, 5, 5, 5); г) (2, 3, 1, 4, 4, 4, 1, 2, 6, 6).

тема «Функции алгебры логики»

№ 1. Какие из предложенных формул являются тавтологиями? Для ответа на вопрос постройте таблицу истинности. Назовите известные вам законы.

          1. .

№ 2. Составьте таблицы истинности для следующих формул и укажите, какие из формул являются выполнимыми, какие – тождественно ложными, какие тождественно истинными:

  1. ;

  2. ;

  3. ;

  4. ;

  5. ;

  6. .

№ 3. Следующие формулы преобразуйте равносильным образом так, чтобы они содержали операции отрицание, конъюнкцию и дизъюнкцию:

    1. ;

    2. ;

    3. ;

    4. .

№ 4. С помощью равносильных преобразований докажите, что следующие формулы являются тождественно ложными:

      1. ;

      2. ;

      3. ;

      4. .

№ 5. Преобразовать формулу так, чтобы она содержала только операции и :

        1. ;

        2. ;

        3. .

тема «Законы алгебры логики»

№1. Построить таблицу истинности следующих булевых функций.

а)  ;

б)  ;

в)  ;

г)  .

№2.  Выписать векторы значений булевых функций из предыдущего примера.

№3.  По векторам значений функций и найти вектор значений функции .

а)  , , ;

б)  , , .

№4.  Булева функция задана вектором своих значений. Найти вектор значений двойственной к ней булевой функции .

а)  ;

б)  ;

в)  .

№5. Найти функцию двойственную к данной.

а)  ;

б)  ;

в)  ;

г)  ;

д)  ;

е)  .

№6. Найти функцию двойственную к данной, пользуясь принципом двойственности.

а)  ;

б)  ;

в)  ;

г)  ;

д)  ;

е)  .

тема «Разложение функции по одной, двум и всем переменным»

№1. Построить ДНФ, КНФ, СДНФ, СКНФ булевой функции с помощью эквивалентных преобразований.

а)  ;

б)  ;

в)  ;

г)  ;

д)  ;

е)  .

№2. Найти СДНФ и СКНФ булевой функции , заданной вектором своих значений.

а)  ;

б)  ;

в)  ;

г)  .

№3. По СКНФ функции найти СДНФ функций и .

а)  ;

б)  .

№4.  По СДНФ функции найти СКНФ функций и .

а)  ;

б)  .



Похожие документы:

  1. Б 796 Болтнев, Валентин Егорович. Экология : учеб для студ вузов, обуч по напр.: "Автоматизация технол процессов и пр-ва", "Прикл информатика" / Болтнев

    Документ
    ... Станислав Михайлович.   Дискретная математика. Теория и практика решения задач по информатике : учебное ... методическое пособие содержит методические рекомендации по изучению дисциплины и выполнению письменных работ, планы-конспекты разделов курса ...
  2. Новые поступления из эбс «айбукс»

    Документ
    ... разделы дискретной математики и описаны важнейшие алгоритмы на дискретных структурах данных ... подготовки и самоподготовки к профессиональной деятельности. Даются рекомендации по проведению методических и практических занятий для студентов 1-4-х курсов ...
  3. Литература универсального содержания

    Литература
    ... Дискретная математика : учеб. пособие для студ. учреждений высш. образования по ... по их оформлению. Для студентов направления подготовки "Бизнес-информатика" (бакалавриат). ... Данный сборник содержит методические рекомендации по обработке, хранению, ...
  4. Адрес сайта унибц (Научной библиотеки): lib rudn ru Факультет физико-математический и естественных наук Полнотекстовые материалы в эбс рудн

    Документ
    ... методическое пособие для студентов бакалавриата направлений 080500 «Бизнес-информатика», 010300 «Фундаментальная информатика и информационные технологии», 010200 «Математика ... по дискретной математике. ... Методические рекомендации для практикума по курсу ...
  5. Къ БР-м и къэрал лъэпкъ библиотэкэ Кабардино-Балкарской Республики КъБР-м И ПЕЧАТЫМ И ТХЫДЭ КъМР-ни БАСМА ЛЕТОПИСИ Къэрал библиографическэ указатель (2)

    Документ
    ... налогообложение, 080500 – Менеджмент, 010101 – Математика, 080801 – Прикл. информатика в экономике /Федер. агентство по образованию; Гос ... методические рекомендации. Для спец.: 030401 – История и направления 030400 – История /Федер. агентство по ...

Другие похожие документы..