Лекция №15. Тема: метод математической индукции.

Математическая индукция – это общий способ математического доказательства, определение которого свойства для всех натуральных чисел основанного на доказательстве первоначального элемента с последующей гипотезой справедливости для n элемента, доказательством справедливости гипотезы для n+1. Таким образом, справедливость утверждения (теоремы) применяется для всего множества.

 

Пример:

1) 6²ⁿ - 1 кратко 35, доказать.

а) n = 1, 35:35

б) допустим 6²ⁿ – 1 кратко 35 – верно

в) доказать: 6²⁽ⁿ⁺¹⁾ – 1 кратно 35

6²⁽ⁿ⁺¹⁾ – 1 = 6²ⁿ * 6ⁿ – 1= 6²ⁿ * 6ⁿ + 6² - 6² – 1 = (6²ⁿ * 6² - 6²) + 35 = 36*(6²ⁿ– 1)+35 – кратно 35.

 

Теория кодирования.

 

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

 

Направления теории кодирования:

Ø статическое кодирование

Ø помехоустойчивое кодирование

Ø корректирующие коды

Ø циклические коды

Ø арифметические коды

 

Требования к шифру:

ü он должен быть несложным

ü должен быть надежен

ü должен быть скрытен

 

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

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

 

Пример кодирования:

- азбука Морза

- разнообразные шифры

- системы счисления

 

Кодирование является центральным вопросом при решении всех задач программирования:

v представление данных произвольной формы памяти компьютера

v обеспечение помехоустойчивости при передачи данных по каналу связи

v сжатие информации в базах данных

v защиты информации от несанкционированного доступа.

 

Алфавитное кодирование определяется следующим образом:

- в множестве А выбираются некоторым образом n слов J₁, J₂, J₃, …, называемых элементарными кодами.

Пусть f(B_i) = J_i, причем i = 1, 2, 3,…, n, тогда код любого слова а = B_i1, B_i2, …, B_in? B, есть J(а) = J₁, J₂, J₃, …J_n

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

J1	J2	…Jn-1	Jn
B1	B2	…Jn-1	Bn

 

 

Лекция №16. Тема: основы теории графов.

Теория графов – область дискретной математики, особенностью которой является геометрический подход к изучению объектов исследования.

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

Во многих прикладных задачах изучаются системы связи между различными объектами. Объекты называются вершинами, а связи между вершинами - отрезками, соединяющие пару точек и называются они ребрами.

Понятие графа опирается на понятие множества. Граф представляет собой непустое конечное множество вершин V и множества дуг (ребер) R, оба конца которых принадлежат множеству V. Элементы множества V и R называют вершинами и дугами (ребрами графа).

Примеры графов

1) 3)

 

2)

 

4)

 

5) 6)

Пусть на плоскости задано некоторое множество вершин V и дуг R. Графом называют бинарное отношение множеством V и R или иначе f V → R. Здесь f отображение инциденции.

 

Граф называется ориентированным, если указано направление дуг и неориентированным, если такое направление не указано.

Граф называется петлёй, если его начало и конец совпадают.

Под графом G_a графа G называется граф, который входит в лишь часть вершин графа G вместе с дугами их соединяющими.

Частным графом G_в графа G называется граф, который входит в лишь часть дуг графа G вместе с вершинами их соединяющими. (Карта шоссейных дорог – это граф. Дороги Саратовской области – это подграф, а главные дороги – это частный граф, где вершины называются смежными, если существует соединяющая их дуга. Два смежных ребра имеют общую вершину).

Степенью (валентностью) вершины называется число инцидентных ей рёбер.

Кратностью пары вершин называется число соединяющих их ребер или дуг.

Граф, состоящий из изолированных вершин, называется нульграф.

Теорема

В графе G(V, R) сумма степеней всех его вершин – число четное равное удвоенному

n

числу ребер графа: deg(V_i) = 2m, где n =│V│ - число вершин,

i= 1 m =│R│ - число ребер графа

 

Вершина называется четной/нечетной, если её степень – четная/нечетная.

Ориентированные графы изображаются так:

V₂ V₂

V₁ V₃ V₁ V₃

 

Неориентированный граф – ребро, цепь, цикл;

Ориентированный граф – дуга, путь, контур.

 

Ребро (дуга) – отрезок, соединяющий две вершины.

Цель (путь) – последовательность ребер (дуг).

Цикло (контур) – конечной длины цель (путь), у которой начальная и конечная вершины совпадают.

 

Граф называется связанным, если любые две его вершины можно соединить цепью.

Граф сильно связан, если для любых двух вершин х_i ≠ х_j существует путь, идущий из х_i и х_j.

Граф, который не является связанным, может быть разбит на конечное число связанных графов, называемых компонентами связанности.

 

V₃ V₃

- G(V, R) – граф V₂ V₄ - G_а(V, R) – подграф

V₁ V₅ графа G

У графа может быть несколько подграфов.

Граф G называется полным, если любые две его различные вершины напрямую соединены как минимум одним и ребром.

V₃

V₁ V₅ _

Дополнением графа G(V, R) называется граф G(V, R) с теми же вершинами V, что и граф G и имеющие те и только те ребра R, которые необходимо добавить в графу G, чтоб он стал полным.

Граф с кратными ребрами не имеет дополнения.

 

G(V, R)

V₂ V₃

- граф _

G(V,R) -

V₁ V₄

Маршрут – это последовательность ребер неориентированного графа, когда вершина предыдущего ребра совпадает с следующего ребра.

Число ребер маршрута называется его длиной.

В маршруте одно и тоже ребро может встретиться несколько раз; если ребра встречаются один раз, то маршрут называется цепью.

В ориентированном графе маршрут называется путь – упорядоченная последовательность дуг ориентированного графа, соединенных последовательно.

§ Направление каждой дуги должно совпадать с направлением пути. Путь навстречу дуги невозможен.

§ Не одна дуга пути не должна встречаться дважды.