Программа по формированию навыков безопасного поведения на дорогах и улицах «Добрая дорога детства» 2
Скачать 1.97 Mb.
|
| Тема 6.1 Принцип метода математической индукции. Индукцией называется метод ведущий от частных примеров к некоторому общему выводу. Будем складывать нечетные числа:  - называется гипотезой (или предположением).Гипотеза может быть либо истинной, либо ложной - это доказывается методом математической индукции, то есть заключается в следующем:
При n=1 – гипотеза выполняется: А(1) – верно.
Взять n=k+1 и доказать, что А(k+1) – верно, используя пункт 2. Замечание. Чтобы показать, что эта формулировка следует из предыдущей, достаточно рассмотреть множество A={x  N | P верно для x}. Для доказательства в обратную сторону, множеству A N можно сопоставить свойство P «быть элементом множества A».О доказательствах, основанных на аксиоме индукции, говорят, что они проведены методом математической индукции. Такие доказательства имеют следующую структуру:
Примеры. Проведем два доказательства методом математической индукции. 1) Сумма первых натуральных чисел от 0 до n включительно равна 0,5n(n+1): 0+1+…+n = 0,5n(n+1). Доказательство. Утверждение верно при n=0: имеем 0=0,5Е0Е(0+1) (посылка индукции). Предположим, что доказываемое утверждение верно для n=k (индуктивное предположение), то есть 0+1+…+k = 0,5k(k+1). Покажем, что тогда оно верно и для n=k+1, то есть 0+1+…+k+(k+1) = 0,5(k+1)(k+2) (индуктивный шаг). Сумма во втором равенстве отличается от суммы из первого равенства слагаемым k+1. Поэтому, в силу индуктивного предположения, получаем 0+1+…+k+(k+1) = 0,5k(k+1)+k+1 = 0,5(k+1)(k+2), что и требовалось доказать. В соответствии с принципом математической индукции, доказываемое утверждение верно для всех n. 2) Число подмножеств множества, содержащего n элементов, равно 2n. Доказательство. Утверждение верно при n=0: пустое множество (единственное множество, содержащее 0 элементов) имеет ровно одно подмножество . Предположим теперь, что всякое множество с n=k элементами имеет 2k подмножеств, и покажем , что множество с n=k+1 элементами имеет 2k+1 подмножеств. Пусть A – произвольное множество с n=k+1 элементами. Так как k+1>0, то A не пусто и содержит хотя бы один элемент. Пусть a A. Разобьем совокупность всех подмножеств множества A на два класса. В класс U входят все подмножества, содержащие a, в класс V входят все подмножества, не содержащие a: U={X⊂A | a∈X}; V={Y⊂A | a Y}. Положим A’=A\{a}. Множество A’ содержит k элементов, так что по индуктивному предположению, число его подмножеств равно 2k. Но подмножества множества A’ – это в точности подмножества множества A, не содержащие a. Следовательно, |V|=2k. Пара взаимно обратных отображений U→V, X→X\{a} и V→U, Y→Y∪{a} устанавливает между U и V взаимно однозначное соответствие, так что |U|=|V|=2k. Поэтому общее число подмножеств множества A составляет |U|+|V|=2k +2k =2k+1, что и требовалось доказать. Иногда принцип полной индукции применяется в следующей форме. Пусть P – утверждение относительно натуральных чисел n такое, что 1) P верно для n=n0; 2) из справедливости P(n) для n= n0, n0+1, …, n0+k следует справедливость P(n) для n= n0+k+1. Тогда P верно для всех n≥ n0. Принцип полной индукции в этой форме может быть сведен к предыдущей формулировке заменой утверждения P утверждением P’: утверждение P имеет место для всех t, таких, что n0≤t≤n. Возможны и другие модификации принципа полной индукции Теорема. Всякое непустое подмножество натурального ряда содержит наименьший элемент. Доказательство. Пусть A N – непустое подмножество. Возможны два случая: 0A и 0 A. В первом случае 0 является наименьшим элементом множества A. Рассмотрим второй случай. Предположим, что в A нет наименьшего элемента. Пусть A’ – это множество всех таких n, что ни одно число t из промежутка от 0 до n не содержится в A. Так как 0 A, то 0A’. Далее, если kA’, то и k+1A’. В самом деле, в противном случае мы имели бы 0,1,…,k A, но k+1A – а это означает, что k+1 – наименьший элемент множества A в противоречие с предположением об отсутствии такового. По аксиоме индукции множество A’ совпадает с N. Но это находится в противоречии с предположением о том, что множество A не пусто.Раздел 7. ОСНОВЫ ТЕОРИИ ГРАФОВ. Тема 7.1 Понятие неориентированный граф. Основные определения. Графом (Г) называется не пустое множество точек и множество отрезков, оба конца которых принадлежат данному множеству. При изображении графа расположение точек, длина отрезков не играют роли, не имеют значения, более того не важно являются ли выбранные обрезки прямыми или кривыми. Точки называются вершинами, отрезки – ребрами. Вершина, не принадлежащая ни одному из ребер называется изолированной.
A Теоремой называется необходимое и достаточное условие, что два рисунка изображают один и тот же граф. Теорема: Для того, чтобы два рисунка изобразили один и тот же граф необходимо и достаточно, чтобы между вершинами на этих рисунках существовало такое взаимно-однозначное соответствие, при котором выполнялись бы два условия:
Графом Г называется не пустое множество М и множество отношений на нем. Г=(M,Q) Лабораторная работа № 1. Основные характеристики графа Цель работы:
Литература:
Порядок выполнения работы: I Разработать схему алгоритмов основной программы и подпрограмм. II Написать и отладить программу на языке Turbo Pascal. Задание: Задача Прима-Краскала. Дана плоская страна и в ней n-городов. Нужно соединить все города телефонной связью так, чтобы общая длина телефонных линий была минимальной. Другими словами, дан граф с n-вершинами; длины рёбер заданы матрицей { }, i,j=1,2,3, ,n. Найти дерево минимальной длины.Краткие теоретические сведения: Граф представляет собой непустое множество точек и множество отрезков, оба конца которых принадлежат заданному множеству точек. Ребро, ведущее из вершины в неё же, называется петлей. Граф без кратных ребер и петель называется простым. Цепью между вершинами u и v называется последовательность ребер, соединяющих u и v. Связный граф - это граф, где существует цепь между любой парой вершин u и v; иногда такой граф называют односвязанным. Циклом называется цепь из V в V. Деревом называется граф без циклов. Дерево с n -вершинами имеет n-1 ребер. Поэтому краткое описание поставленной задачи выглядит следующим образом: в цикле n-1 раз делай: Выбрать самое короткое ещё не выбранное ребро при условии, что оно не образует цикла с уже выбранными. Выбранные таким образом ребра образуют искомое дерево. Кроме того, при проверки того, что новое ребро не образовывает цикла со старыми, используйте следующее: до построения дерена окрасим каждую вершину i в отличный от других цвет i. При выборе очередного ребра, скажем (i, j), где i и j имеют разные цвета, вершина j и все окрашенные в её цвет (т.е. ранее соединенные с ней) перекрашиваются в цвет i. Таким образом, выбор вершин разного цвета обеспечивает отсутствие циклов. После выбора n-1 ребер все вершины получают один цвет. В заключении анализа алгоритма надо оценить требуемую память и требуемое число операций. С памятью здесь все ясно: в решении удобно хранить n-1 ребер ответа. Всего требуется память 0(n2), т.е. порядка ≈  , что учитывая реальные величины n, необременительно. Для нахождения текущего минимального ребра надо просмотреть 0() чисел и сделать это n-1 раз, так что временная сложность алгоритма 0( ). Это тоже реально.Содержание отчета;
Контрольные вопросы:
Тема 7.2 Теорема о сумме степеней вершин графа. Полный граф, его свойства. Граф Г называется полным, если каждые две его вершины соединены одним и только одним ребром. А В С Д - не полный граф А В С Д - полный граф Только для неориентированного графа существует дополнение: Г  – дополнениеДополнением графа Г называется новый граф , состоящий из всех тех же вершин, что и граф Г и тех и только тех ребер, которые надо добавить, чтобы граф Г стал полным.Степенью вершины называется количество ребер ей принадлежащих В Д Е А С Степень А=1, степень В=2, степень С=2, степень Д=1, степень Е=0 Степень каждой вершины полного графа на единицу меньше числа вершин. Теорема: Сумма степеней всех вершин графа есть число четное и равное удвоенному количеству ребер  При большом количестве вершин схема теряет свою наглядность и поэтому используют другой способ задания графов в виде матрицы смежностей.  где каждое  М – симметричная на главной диагонали – 0 М(Г)=  Лабораторная работа № 2. Задание графа матрицей смежности Цель работы:
Литература:
Порядок выполнения работы: I Разработать схему алгоритмов основной программы и подпрограмм. II Написать и отладить программу на языке Turbo Pascal. Задача Граф задан матрицей смежности М=  Изобразить граф, исходя из внешнего вида данной матрицы. Краткие теоретические сведения: Матричный эквивалент графа широко используется в работе с графами на ЭВМ. Граф называется полным, если каждые две его вершины соединены одним и только одним ребром. -полный граф  от граф не является полным Граф, не являющийся полным, можно преобразовать в полный граф с теми же вершинами, добавив недостающие ребра. Вершины графа Г и ребра, которые добавлены, также образуют граф, такой граф называется дополнением и обозначается  .Каждой вершине графа  можно поставить в соответствие строку и столбец с номером i, причем{ 1, если   { 0, если  Тогда матрица  называется матрицей смежностей графа Г и обозначается М(Г).Содержание отчета:
Контрольные вопросы:
Тема 7.3 Метрические характеристики графа. Пусть дан граф: А3 Как от вершины А1 дойти до А5? Существуют следующие пути: Путем от вершина А1 до вершины Аn называется такая последовательность ребер, ведущая от А1 до Аn, что любые два соседних ребра имеют общую вершину и ни одного ребра не встречается дважды. Путь, в котором начальные и конечные вершины совпадают называют циклом. Путь от вершины А1 до Аn называется простым, если он не проходит ни через одну из вершин графа более одного раза. Цикл называется простым, если он не проходит ни через одну из вершин графа более одного раза. Длиной пути (цикла) называется количество ребер его составляющих. Дан граф. Найти пути от А1 до А6 и определить их длину Расстоянием от вершины А до вершины В называется длина наименьшего пути, если не существует пути от А до В, то считают что расстояние равно бесконечности. S(A1,A6)=1 S(A1, A7)=∞ Вершины А и В называются связными, если не существует пути связывающего их. Вершины:
Лабораторная работа № 3. Полный граф, его свойства. Теорема о сумме степеней вершин графа Цель работы:
Литература:
Порядок выполнения работы: I Разработать схему алгоритмов основной программы и подпрограмм. II Написать и отладить программу на языке Turbo Pascal. Задание: Граф задан матрицей смежности М =  Для графа, заданного своей матрицей смежности, определить степени всех его вершин. Краткие теоретические сведения: Граф называется полным, если каждые две его вершины соединены одним и только одним ребром. Степенью вершины называется число ребер графа, которым принадлежит эта вершина. Е Степ. А=1 Степ. В=2 Степ. С=2 Степ. D=l Стен. Е=0 Вершина называется нечетной, если её степень - число нечетное. Вершима называется четной, если её степень - число четное. Степень каждой вершины полного графа на единицу меньше числа его вершин. Теорема о сумме степеней графа В графе Г - сумма степеней всех его вершин, есть число четное, равное удвоенному числу его ребер, т.е. где р - число ребер графа, n- число вершин. Содержание отчета:
Контрольные вопросы:
|
