В наше время роль комбинаторики существенно изменилась. Если раньше комбинаторика часто воспринималась только как занимательная часть математической науки, то после появления ЭВМ и связанного с этим расцветом конечной математики комбинаторные методы стали значительно более востребованными, они применяются сегодня в теории случайных процессов, в вычислительной математике, в планировании экспериментов. Теория графов с практической точки зрения также один из наиболее востребованных сегодня разделов дискретной математики. Она используется при проектировании интегральных схем и систем управления, исследовании автоматов и логических цепей, при системном анализе, автоматизированном управлении производством, при разработке вычислительных и информационных сетей. Обширное применение теория графов находит также в вычислительной технике и кибернетике в теоретическом программировании, при проектировании ЭВМ и баз данных. Графы также успешно применяются для решения задач планирования выбора оптимальных маршрутов, решения некоторых проблем, имеющих место в биологии и психологии.
Отметим, что избранные разделы дискретной математики являются не только востребованными в науке и практике, но и наиболее доступными для изучения старшеклассниками. Кроме того, материал этих разделов достаточно удачен для формирования универсальных учебных действий, особенно действия моделирования.
Весь отобранный материал по комбинаторике и основам теории графов разделен на 15 тем, перечень вопросов, изучаемых в рамках каждой из которых, приведен ниже.
Тема 1. Множества, кортежи, отображения. Введение в комбинаторику. Множество. Кортеж. Отображение.
Тема 2. Основные законы комбинаторики. Правила суммы и произведения.
Тема 3. Основные комбинаторные соединения. Факториал. Размещения, сочетания, перестановки с повторениями и без повторений. Формулы для числа основных комбинаторных соединений.
Тема 4. Применение элементов комбинаторики к нахождению вероятностей. Классическое определение вероятности. Вероятностные задачи, в которых применяются элементы комбинаторики.
Тема 5. Сочетания и биномиальные коэффициенты. Треугольник Паскаля. Бином Ньютона.
Тема 6. Рекуррентные соотношения. Рекуррентное соотношение. Примеры рекуррентных соотношений. Арифметическая и геометрическая прогрессии как рекуррентные соотношения. Числа Фибоначчи.
Тема 7. Основные понятия теории графов. Граф. Смежные вершины. Дополнение к графу. Мультиграф. Псевдограф. Степень вершины. Висячие и изолированные вершины. Лемма о рукопожатиях. Теоремы о вершинах графа. Изоморфные графы.
Тема 8. Полный граф и нуль-граф. Путь, цикл. Связный граф. Нуль-граф. Полный граф. Теорема о числе ребер полного графа на п вершинах. Маршрут. Путь. Связанные вершины. Связный граф. Теорема о связности графа либо его дополнения.
Тема 9. Деревья. Регулярные графы. Дерево. Каркас графа. Лес. Теорема о числе вершин и ребер дерева. Регулярный граф. Теорема о существовании к-регулярного графа на п вершинах.
Тема 10. Двудольные графы. Двудольный, полный двудольный граф. Теоремы о вершинах и ребрах двудольного графа. Теорема Кенига.
Тема 11. Ориентированные графы. Ориентированный, смешанный, полный ориентированный граф. Турнир. Полустепени захода и исхода вершины. Теорема о числе ребер орграфа. Корневое дерево. Теоремы о существовании ориентированного цикла и пути в орграфе.
Тема 12. Способы представления графов. Необходимость различных способов представления графов. Нагруженный (взвешенный) граф. Матрицы смежности и расстояний. Применение матричных способов представления графов в программировании.
Статьи по теме:
Сравнительная характеристика грамматических явлений русского и немецкого
языков
грамматика немецкий язык обучение сказка В лингвистической литературе, рассматривающей вопросы типологического сопоставления грамматического строя русского и немецкого языков, выделяются с одной стороны, сходные черты, а с другой – различия на всех уровнях (морфемно-морфологическом и синтаксическом ...
Элементы занимательности на уроке иностранного языка и вне его
Роль практических целей на уроках иностранного языка определяет и практическую целевую установку во внеурочной работе. Важно для каждого ученика найти задания, выполнение которых вызывает у них чувство удовлетворения, удовольствия. В предлагаемых нами заданиях на уроках и вне его учащиеся привлекае ...
Рекомендации педагогам для повышения уровня коммуникативной культуры
1. Отношения с людьми – главное в любой деятельности, а тем более в педагогической. Все ваши знания и идеи останутся невостребованными, если ученики не потянутся к вам сердцем. Отношения с людьми нужно строить на взаимопонимании и доверии. 2. Не нужно превращаться в чиновника, для которого главное ...