Паспорт
Фонда оценочных средств
По дисциплине «Дискретная математика»
Таблица 1
| № п/п | Наименование раздела дисциплины | Код контролируемой компетенции (или ее части) | Наименование оценочного средства |
| Комбинаторика. Производящие функции и рекуррентные уравнения | ПК-1, ПК-11 | Обсуждение изученного материала на практических занятиях. | |
| Теория графов | ПК-1, ПК-11 | Обсуждение изученного материала на практических занятиях. Анализ ответов обучающихся. Типовые задания. |
Формируемые компетенции
Таблица 2
| Перечень формируемых компетенций | Формируемые элементы компетенций |
| готовность реализовать образовательные программы по учебным предметам в соответствии с требованиями образовательных стандартов стандарта (ПК-1) | Знает: - основные дискретные объекты (таблицы, графы, производящие функции), появляющиеся в комбинаторных исследованиях или возникшие к настоящему времени в других разделах математики в процессе её развития. Умеет: - использовать подходящие методы дискретной математики при решении базовых комбинаторных задач алгебры, теории чисел, геометрии, математической логики, теории вероятностей. Владеет: - основными понятиями базовых разделов дискретной математики, иерархией этих понятий; замечательными соотношениями в при перечислении комбинаторных и графических объектов; геометрическими интерпретациями объектов дискретной математики, и геометрическим смыслом операций над такими объектами. |
| готовность использовать систематизированные теоретические и практические знания для постановки и решения исследовательских задач в области образования (ПК-11). . | Знает: основные понятия, методы и инструменты дискретной математики и соответствующие прикладные аспекты дисциплины Умеет: – осуществлять выбор надлежащих инструментальных средств для использования в поставленной задаче, анализировать полученные результаты и обосновывать их – осуществлять поиск информации по стоящей задаче и осуществлять ее анализ информации для решения поставленной задачи Владеет: – навыками самостоятельной работы и самоорганизации для выполнения требуемой работы |
Шкала оценивания
В соответствии с балльно-рейтинговой системой ГОУ ВО МО «ГСГУ» в каждом семестре обучающийся может набрать за работу в семестре максимум 70 баллов и может получить на экзамене максимум 30 баллов.
В таблице 3 приведены критерии оценивания экзамена:
Таблица 3
| Сумма всех баллов, набранных обучающимся по дисциплине | Рейтинговая шкала (оценка) |
| ≤ 50 | Неудовлетворительно |
| 51 – 66 | Удовлетворительно |
| 67 – 84 | Хорошо |
| ³ 85 | Отлично |
Уровень сформированности компетенции
Таблица 4
| № п/п | Уровень сформированности компетенции или ее части данной дисциплиной | Cумма всех баллов |
| Пороговый | 51 – 66 | |
| Средний | 67 – 84 | |
| Повышенный | ³ 85 |
Накопление баллов за работу в течение семестра
Таблица 5
| № п/п | Вид работы (общее количество) | Максимальный балл (за одну единицу) | Максимум баллов |
| Работа на лекциях (7). | |||
| Работа на практических занятиях (13). | |||
| Самостоятельная работа обучающихся (участие в научной работе, освоение дополнительного материала) (2). | |||
| Типовые ситуационные задания (3). | 3 | ||
| Экзамен (1) | |||
| Всего баллов |
Типовые задания или иные материалы, необходимые для оценки знаний, умений, навыков и (или) опыта деятельности
Цель выполнения: проверить уровень знаний в области сопровождения научно-методического или научного исследования.
1. Сколькими способами можно разложить девять монет разного достоинства в два кармана? (компетентностный вопрос).
2. Сколькими способами могут сесть за большой круглый стол десять человек так, чтобы трое друзей сидели рядом? (компетентностный вопрос).
3. Сколькими способами можно написать в строку 6 плюсов и 4 минуса? (компетентностный вопрос).
Критерии оценивания
Каждое верно выполненное задание оценивается в 3 балла.
3 балла — задание решено абсолютно правильно.
2 балла — задание решено правильно, но получен неверный ответ из-за арифметической ошибки, и имеется один недостаточно обоснованный момент.
1 балл — ход решениязадания неправильный, но в решении содержатся верные отсылки к необходимым свойствам и/или соотношениям, решение может быть не доведено до конечного ответа.
0 баллов — задание решено абсолютно неправильно или решение отсутствует вовсе.
Образец схемы выполнения ситуационных заданий
Задание 1. Сколькими способами можно разложить девять монет разного достоинства в два кармана?
Решение.
Обозначим один карман символом 0, а второй карман символом 1. Раскладывание монет по карманам – это выборка длины девяти из символов 0 и 1. Все такие выборки реализуются при раскладывании. Число выборок длины девять из множества, состоящего из двух символов, равно 2⁹=512.
Задание 2. Сколькими способами могут сесть за круглый стол на десять мест десять человек так, чтобы трое друзей сидели рядом?
Решение.
Места за круглым столом мы будем различать, считая, например, что они пронумерованы. Тогда рассадка людей за круглым столом будеи перестановкой десяти элементов. Всего таких рассадок 10!. Если считать троих друзей единым целым (Например, один полный человек, который занимает три места),
то задача сводится к рассадке восьми человек на восемь мест. Получим 8! рассадок.
Учтем рассадки друзей внутри своей тройки. Этих рассадок 3!. По правилу произведения всего рассадок будет 8!· 3!=41320.
Задание 3.
Сколькими способами можно написать в строку 6 плюсов и 4 минуса?
Решение.
Выбор шести мест в строке из десяти мест, где мы поставим
«плюсы» (на оставшихся местах будут поставлены «минусы»), будут сочетаниями
из десяти по шесть, так как мы плюсы не различаем и порядок плюсов несущественен. Число расстановок будет равно С₁₀⁶= С₁₀⁴=(10·9·8·7)/4!=210.
Вопросы для обсуждения на практических занятиях
№№ 1,2. Отличиеупорядоченных наборов от неупорядоченных.Пары, тройки и другие упорядоченные наборы и правило произведения. Подмножества и неупорядоченные наборы. Выборки, размещения, перестановки и упорядоченные наборы. Сочетания и подмножества.
№3. Формулы перечисления выборок, размещений, перестановок и метод их доказательства. Ликвидация порядка и действие группы подстановок. Доказательства формул для перечисления перестановок с повторениями и для разбиений.
Бином Ньютона, полиномиальная формула и комбинаторные тождества. Идея производящих функций.
№№ 4,5. Простейшие свойства производящих функций. Простые последовательности и их производящие функции. Экспоненциальные производящие функции и их свойства. Дзета-функция Римана. Функция Мёбиуса. Производящие функции Дирихле. Произведение производящих функций Дирихле для некоторых последовательностей. Производящая функция Дирихле для функции Мебиуса. Производящие функции для перечисления комбинаторных схем.
№6. Рекуррентные уравнения. Пример чисел Фибоначчи и рекуррентное уравнение для них. Решение рекуррентных уравнений: общая схема с использованием производящих функций. Решение линейных рекуррентных уравнений с постоянными коэффициентами.
№№ 7-9. Изоморфизм графов. Подграфы. Геометрическое изображение графа. Теорема о геометрической реализации графа в трехмерном евклидовом пространстве без пересечения ребер. Понятие степени вершины. Теоремы о сумме степеней вершин графа и количестве нечетных вершин. Путь, цепь, цикл графа. Простые цепи и циклы. Связные графы. Достаточное условие связности графа. Теоремы об оценке числа компонент связности графа. Двудольные графы. Теорема Кёнига. Понятие эйлерова графа. Критерий эйлеровости графа. Задача о кёнигсбергских мостах. Гамильтоновы графы. Теорема Эйлера (формула эйлеровой характеристики).
№№ 10,11. Укладка графа на поверхность. Планарные и плоские графы. Непланарность графов К_5 и К_3,3. Род графа. Формулы для рода полных графов и полных двудольных графов. Теорема Куратовского-Понтрягина о планарности графа.
№№ 12,13. Раскраска вершин и ребер графа. Хроматическое число графа и поверхности. Формулы для оценки хроматического числа графа. Теорема Хивуда о хроматическом числе поверхности. Теоремы о четырех и пяти красках для планарных графов.
Критерии оценивания
Содержание ответа и активность обучающихся на каждом практическом занятии оценивается максимум в 2 балла. Если обучающийся не участвовал в решении практических заданий и в обсуждении теоретических вопросов, то за данное практическое занятие он получает 0 баллов.