Российский государственный университет им. И. Канта Факультет информатики и

математики
Кафедра компьютерного моделирования и информационных систем
ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ИНФОРМАТИКИ
Александр Васильевич Колесников
доктор

Калининград, 2010

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

самостоятельные научные дисциплины.
Теоретическая информатика - часть информатики, включающая математические

Вычислительная техника - раздел, в котором разрабатываются общие принципы построения архитектур вычислительных систем. Примеры классических решений – фон-Неймановская архитектура компьютеров первых поколений, шинная архитектура ЭВМ старших поколений, архитектура параллельной (многопроцессорной) обработки информации.

(алгоритмические языки и компиляторы, интерфейсы, ОС) и прикладного (редакторы текстов,

Информационные системы - раздел информатики, связанный с анализом потоков информации в сложных системах, их оптимизацией, структурированием, принципами хранения и поиска информации.

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

термин информатики. Впервые введен в книге Н.Винера «Кибернетика». В узком

Информация - это содержание сообщения, сигнала, памяти, а также сведения, содержащиеся в сообщении, сигнале или памяти.

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

определять информацию с точки зрения обмена данными между источником и

Клод Элвуд Шеннон, американский математик, инженер, доктор наук, профессор, основатель теории информации

Данные (от лат. data) — представление фактов и идей в формализованном виде, пригодном для передачи и обработки в некотором  информационном процессе.

фильтр «работает» на прием сообщений из канала связи. Синтаксис –

из канала связи. Семантика – это установленное людьми, договорное соответствие

Дверь — проём в стене для входа и выхода из помещения, или проём во внутреннее пространство чего-либо а также створ или несколько створов, закрывающие этот проём.

данных. Прагматика – значимость, ценность данных для чего либо. Например,

Источник

Канал связи

Синтаксический фильтр

Семантический фильтр

Прагматический фильтр

Приемник

Принято

Понято

Оценено

Синтаксический шум

Семантический шум

Прагматический шум

Сообщения Данные

оценены как полезные (прагматика).

информацию
Знания о знаниях
Способность использовать знания наилучшим образом
«Чтобы тратить деньги с

разнообразию, сложности, структурированности (упорядоченности), определенности, выбору состояний отображаемой системы.
Меры информации
Мера

Точная наука невозможна без измерений. Для измерений необходимы опорные метки — меры. Чтобы стать общепринятыми, они должны быть простыми, понятными и общедоступными.

содержащем ФИО, год, месяц, дату рождения: Иван Петрович Семенов 1983

Ральф Хартли, американский ученый, пионер теории информации

информации. Это положительная сторона формулы. Но имеется и минус: формула

Вероя́тность — численная мера возможности наступления события. На практике вероятность события — это отношение количества тех наблюдений, при которых рассматриваемое событие наступило, к общему количеству наблюдений. Такая трактовка допустима при достаточно большого количества наблюдений.

символа в сообщении.


Повседневный опыт подсказывает, что часто происходящие события, дают

Мало информации

Много информации

Вывод: частые, ожидаемые события несут мало информации и, наоборот, редкие, т.е. неожиданные события, обладают высоким информационным содержанием.

Следовательно, информация (I) и вероятность (p) находятся в обратно пропорциональной зависимости.

Мера К.Шеннона

отрицательная величина. Объясняется это тем, что вероятность р, согласно определению, меньше

где , - число сигналов i – го типа

Меры информации

удельную информативность источника, нужно это число разделить на N. При

Мера Шеннона

Меры информации

ФИО, год, месяц, дату плюс пробел. Десятичных цифр – 10.

Мера Шеннона

Таблица вероятностей появления букв русского алфавита в сообщениях

Меры информации

в качестве представителя (заместителя) какого-то другого объекта.

Знаковая ситуация

Это мощный инструмент решения задач. Чтобы задать знаковую систему необходимо:

Язык. Система счисления. Музыка. Религия. Мода .

Знаковая система

Примеры знаковых систем

и предложил её название.


Представление информации Семиотика
Чарльз Пирс,
американский философ, логик,

Системы средств, используемые человеком для обмена информацией - знаковые или семиотическими, т. е. системами знаков и правил их потребления. Наука, изучающая знаковые системы называется СЕМИОТИКОЙ или семиологией ( от греч. слова sema — знак).

Современная фрактальная семиотика

объект, обладающий синтаксисом, семантикой и прагматикой
Треугольник Фреге – основа современной

Готлоб Фреге,
немецкий логик, философ и математик

– множество знаков; U - универсуум, т.е. множество денотатов; Z

Модель знаковой системы

процессы познания - это естественный язык.


Естественный язык — это любой

Естественный язык как знаковая система

различными моделями внешнего мира.
«Зло – это плохо»
«Списывать на экзамене

«Зло – это хорошо»
«Списывать на экзамене – это плохо»

словосочетания. В немногих случаях в этих словах содержится прямая информация

«Он увидел на воде прекрасно пахнущую алую розу».

Текст на естественном языке

— большой, гладкий.
Астра — яркий.
Баобаб

Василек — светлый.
Гвоздика — яркий.
Дуб — большой, сильный, красивый, могучий.
Дубрава — большой, красивый, величественный.
Ель — красивый.

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

Звуковая форма слова женщина получила компьютерные оценки, явно противоречащие признаковому значению: «темный», «отталкивающий», «тяжелый», «устрашающий», «низменный», «злой».

Звук. Текст. Смысл.

Из работ профессора А.П. Журавлева

обработки информации с помощью ЭВМ. Например, язык программирования Паскаль и

некоторым образом специализированных языковых средств с (более или менее) точно

цепочки символов.
Алфавит (иногда говорят – словарь) – непустое множество

в ней символов:

Основные объекты теории формальных языков

символов, принадлежащих данному языку.

Алгебраическое описание – указание, как с помощью

. Все цепочки из

Формальный язык - средство более точного представления знаний, чем естественный

описания. Различают порождающие и распознающие грамматики, в зависимости от того,

с пустой правой частью вида .

в

D - алфавит, как рекурсивно перечислимый набор произвольных

алфавит {1,2,3,4,5,6,7,8,9,0,(,),+,-,*,/}
‹Цифра› ::= 1|2|3|4|5|6|7|8|9|0
‹ПоложительноеЧисло› ::= ‹Цифра›|‹Цифра›‹ПоложительноеЧисло›
‹ОтрицательноеЧисло› ::= - ‹ПоложительноеЧисло›
‹Число› ::=

‹Формула› ::= а|b|#
‹Формула› ::= ‹Формула›‹Формула›

Аксиома: а#а

Продукционные правила: x#y

z, pp, рq, … zz, ppp, …}
A2 = { ,

Аксиомы




Продукционное правило (правило заключения)

Теоремы : (правило силлогизма)
(правило перестановки)

применения продукционного правила к теореме (или теоремам).


Доказательством называется граф-дерево, корневая

правил P = {C → aC | bB;
A → aA

них помечены
нетерминальными символами C, A, B. Четвертая вершина, помеченная символом

Таблица переходов

Состояния

Символы
алфавита

C - в начальном состоянии при поступлении на вход терминального

e
a / a
+ / e
- / e
- / e
a /

- / e

- / e

a /+a

- / e

a /-a

Y

S

S \ X

a

+

-

-

+

a

Граф переходов

Таблица переходов

– а − а + а

– a + − а − + − а

состояния и

Автомат Мили

S, X, Y, f, h > ,

где S -

алгоритмов
Стивен Клини, американский логик, математик, основоположник теории рекурсивных функций
Алонзо Черч,

Основоположники теории алгоритмов

систем ы Поста
Андрей Андреевич Марков,
член-корреспондент АН СССР, математик, существенный вклад

Алан Тьюринг, английский математик, криптограф, основоположник теории алгоритмов, машины Тьюринга

Основоположники теории алгоритмов

формальные модели их представления.


Задачи теории алгоритмов: формальное доказательство алгоритмической

Понятие теории алгоритмов

о неполноте формальных систем, включающих арифметику, первая из которых была

до появления ЭВМ. На протяжении многих веков люди пользовались интуитивным

Рене Декарт,
французский математик, физик

Давид Гильберт,
выдающийся немецкий математик

Готфрид фон Лейбниц,
немецкий математик, философ

следуя которым можно по входным данным определенного вида получать на

Примеры.
Алгоритм сложения чисел в столбик. Если два натуральных числа в десятичной записи, то, следуя известному алгоритму, изучаемому в начальной школе, можно получить десятичную запись их суммы.
Алгоритмы построения циркулем и линейкой, изучаемые в средней школе. Например, алгоритм нахождения середины отрезка или алгоритм построения биссектрисы заданного угла.
Алгоритм решения квадратных уравнений. Подставляя в известную со школы формулу коэффициенты уравнения, можно вычислить количество его корней и сами корни (если они есть).

подчиняется таким-то и таким-то законам. Дайте мне формулу, я подставлю

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

Дело сделано. А зачем мне нужен был математик? Ах да. Он дал мне алгоритм !

набором алгоритмов «на все случаи жизни».



Сегодняшняя математика – это

Алгоритмы и математика

абстракции, строил гипотезы, доказал пару теорем, а в результате выдал

Буду думать еще.
Я тут провел исследования и доказал, что алгоритма

Еще два варианта ответа математика артиллеристу.

алгоритма их решения. Бывают ситуации, когда алгоритм, возможно, и есть,

при помощи циркуля и линейки: удвоение куба, трисекция угла и

Задача удвоения куба. Это классическая задача древности о построении куба, имеющего объем вдвое больший, чем данный куб. Эту задачу называют еще и делийской (делосской), так как по преданию, для избавления от чумы на острове Делос в Эгейском море, оракул потребовал вдвое увеличить кубической формы жертвенник не меняя его формы. Задача сводится к построению отрезка, численно равного , что , как было доказано в 19 веке, не может быть выполнено при помощи циркуля и линейки. При построении подобного отрезка объем полученного куба будет превышать объем исходного ровно в два раза, так как

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



Трисекция угла. Это задача выделения

и выходными. Данные как объекты, с которыми могут работать алгоритмы,

элементы:
Набор объектов, составляющих совокупность данных: исходных, промежуточных и конечных.

в абстрактных алфавитах.
Алгоритм – четкая конечная система правил для преобразования

Четыре основных универсальных алгоритмических модели (системы) :
Рекурсивные функции. Исторически первая формализация понятия алгоритма. Она связывает понятие алгоритма с математическими объектами: вычислениями и числовыми функциями.
Машины Тьюринга. Алгоритм представляется как детерминированное устройство, способное выполнять в каждый отдельный момент некоторые примитивные операции или инструкции. Это автоматная модель алгоритмов.
Нормальные алгоритмы А.А. Маркова. Алгоритм представляется как преобразователь слов в произвольных алфавитах с использованием операции подстановки, т.е. замены части слова на другое слово.
Лямбда-исчисление. Это класс лямбда-определяемых функций, который в точности характеризует понятие эффективной вычислимости и тем самым формализует понятие алгоритма.

они должны быть индексированы

обозначаются как

Суть упорядоченного использования правил из схемы состоит в том, что каждое переработанное слово вновь поступает в начало алгоритма и вновь проверяется на возможность подстановки. Так будет до тех пор, пока ни одно из правил подстановки не может быть использовано, а заключительной подстановкой будет дано указание об окончании работы алгоритма.
Если окажется, что ни одно из правил не применимо, то это означает ситуацию «тупик».

вхождения соединяются последовательно в соответствии с нумерацией правил в схеме.

единиц. Получить на выходе строку, в которой единицы заменены нулями,

Нормальные алгоритмы Маркова
Задача № 1.

Ниже приведена схема нормального алгоритма. При этом .

Схема:
* 0 → 1 *
* 1 → 0 *
* → .
→ *

Работник « * » двигается вдоль строки и выполняет работу меняя 0→1, 1→0

Уничтожение работника. Останов

Включение работника в строку (замена пустой строки на *)

Маркова
Задача № 1
*

* 1 → 0 *
3) * → .
4)

чисел в унарном коде». Даны два десятичных числа, представленные в

Понятие унарного кода

y.
В унарном коде (без нуля) они запишутся как

Алфавит .

Схема:
e | → e * |
* | → | *
* + → | *
| * e → . e

|
2) * | → | *
3) * + → |

y = 3 .Тогда имеем вычислительный процесс
преобразования исходного слова

Схема:
1) e | → e * |
2) * | → | *
3) * + → | *
4) | * e → . e

Удалить из непустого слова P его последний символ.
Протокол:

*a →a*
*b →b*
*c

исходного слова P в заключительное Q:

Нормальные алгоритмы Маркова
Задача № 3

1) *a →a*
2) *b →b*
3) *c →c*
4) a* → .
5) b* → .
6) c* → .
7) → *

входных слов и операторов подстановки, граф-схемы которых удовлетворяют следующим условиям:

любого алгоритма (конструктивно задаваемого алфавитного отображения) в произвольном конечном алфавите

Иногда не удается построить нормальный алгоритм, эквивалентный данному алгоритму в алфавите A . Однако можно построить требуемый нормальный алгоритм, добавив к алфавиту некоторое количество букв.
Если нормальный алгоритм задан в расширенном алфавите А, то говорят, что нормальный алгоритм задан над алфавитом.

массовости и результативности позволяют представить процесс вычисления какой-либо числовой функции

головки и управляющего устройства.

передает информацию о ее содержимом в управляющее устройство, и по

устройства называют внутренней памятью машины Тьюринга.

Машины Тьюринга

алфавит D = {П, Л, С}, где П — означает

в одну сторону, т. е. существуют левые и правые полуленты.

представление;
Табличное представление;
Графовое представление
При протокольной записи все команды должны быть

Протокольное представление

имя текущего состояния машины, а столбец–имя символа внешней памяти. Тогда

состояния машины Тьюринга, а дугами — переходы в те состояния,

вычисление значений функции следования V(x) = x + 1 на

Граф-схема

Таблица переходов

имеем следующий вычислительный процесс:
Реализация на машине Тьюринга примитивно-рекурсивных функций
Протокол

«Удаление из слова символа». А = {a,b}. Удалить из слова

е

Однако в выходном слове Q не должно быть пустых клеток. Поэтому после удаления 2-го символа надо «сжать» слово, перенеся первый символ на одну клетку вправо. Для этого головку нужно вернуть к первому символу, запомнить его и стереть, а затем, снова сдвинувшись вправо, записать его в клетку, где был 2-ой символ. Однако начальный «поход» вправо ко второму символу, чтобы его стереть, и последующий возврат к первому символу - лишние действия. Поэтому сразу запоминаем первый символ, стираем его и записываем вместо второго символа. Остановить перемещение головки при достижении конечного состояния.

b C ,
b →

Реализация на машине Тьюринга алгоритмов обработки символьной информации

Удаление из слова символа

символа
а →

P = eaabbae

Имеем следующий вычислительный процесс:

P = ebbe
e b b e  e e b e  e e b e
  

«Формирование слова на новом месте». А = {a,b,с}. Удалить из

3. Переносим в цикле все символы входного слова, кроме a , вправо за знак « = » в формируемое выходное слово. Для этого анализируем первый символ входного слова. Если это a , тогда стираем его и переходим к следующему символу. Если же первый символ – это b или c, тогда стираем его и «бежим» вправо до первой пустой клетки, куда и записываем этот символ – действия 3 - 5.

входном слове, и повторяем те же самые действия, но уже

4. Этот цикл завершается, когда при возврате налево увидим в качестве первого символа знак « = ». Это признак полного просмотра входного слова и переноса всех его символов, отличных от a , в выходное слово. Надо этот знак стереть, сдвинуться вправо под выходное слово и остановиться – действие 10.

Реализация на машине Тьюринга алгоритмов обработки символьной информации

записи чисел. В любой системе счисления для представления чисел выбираются

Запись произвольного числа x в P-ичной позиционной системе счисления основывается на представлении этого числа в виде многочлена

основывается на представлении этого числа в виде многочлена:

в другую

Выполнение арифметических действий в системах счисления

теоретической точки зрения двоичная система счисления выделяется тем, что ее

Двоичная система счисления была придумана математиками и философами ещё до появления компьютеров (XVII — XIX вв.). Выдающийся математик Лейбниц говорил: "Вычисление с помощью двоек... является для науки основным и порождает новые открытия... При сведении чисел к простейшим началам, каковы 0 и 1, везде появляется чудесный порядок". Позже двоичная система была забыта, и только в 1936 — 1938 годах американский инженер и математик Клод Шеннон нашёл замечательные применения двоичной системы при конструировании электронных схем.

разряд двоичного числа называется бит (англ. «маленький»)
Для обозначения какого-нибудь

Хранение данных в памяти компьютера

представлять только 256 уникальных символов. 

UNICODE - 16-разрядная кодировка, что

Стандарты кодировки

в компьютерной науке из-за легкости перевода в нее двоичных чисел.

Шестнадцатеричная система счисления

- это FF:

При переводе двоичного числа в шестнадцатеричное, первое разбивается на группы по четыре разряда, начиная с конца. В случае, если количество разрядов не делится нацело, то первая четверка дописывается нулями впереди. Каждой четверке соответствует цифра шестнадцатеричной системе счисления:

Например: 10001100101 = 0100 1100 0101 = 4 C 5 = 4C5

Если потребуется, то число 4C5 можно перевести в десятичную систему счисления следующим образом (C следует заменить на соответствующее данному символу число в десятичной системе счисления – это 12):

4C5 = 4 * 162 + 12 * 161 + 5 * 160 = 4 * 256 + 192 + 5 = 1221

Шестнадцатеричная система счисления

числа в десятичное необходимо его записать в виде многочлена, состоящего

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

Переводы из одной системы счисления в другую

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

Переводы из одной системы счисления в другую

последовательно делить на 2 до тех пор, пока не останется

Переводы из одной системы счисления в другую

последовательно делить на 8 до тех пор, пока не останется

Переводы из одной системы счисления в другую

последовательно делить на 16 до тех пор, пока не останется

Переводы из одной системы счисления в другую

нужно разбить на триады (тройки цифр), начиная с младшего разряда,

Переводы из одной системы счисления в другую

разбить на тетрады (четверки цифр), начиная с младшего разряда, в

9.Для перевода восьмеричного числа в двоичное необходимо каждую цифру заменить эквивалентной ей двоичной триадой.

10.Для перевода шестнадцатеричного числа в двоичное необходимо каждую цифру заменить эквивалентной ей двоичной тетрадой.

11. При переходе из восьмеричной системы счисления в шестнадцатеричную и обратно, необходим промежуточный перевод чисел в двоичную систему.

Переводы из одной системы счисления в другую

производится сложение 1+1, происходит перенос в старший разряд. В старший

Кодирование источников. Примеры: кодирование связанного текста кодом Морзе, оцифровка аудио

К. Шеннон дал определение понятий современной теории информации и заложил

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

Перфокарты впервые начали применяться в ткацких станках Жаккарда (1808) для управления узорами на тканях. Существовало много разных форматов перфокарт; наиболее распространённым был «формат IBM», введённый в 1928 г. 

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

Перфокарта – носитель информации

использовались с середины X1X века в телеграфии, отверстия в них располагались

Перфолента – носитель информации

ASCII (англ. American Standard Code for Information Interchange) —американский стандартный код для обмена информацией

данных
Передатчик данных
Приемник данных
Получатель данных
Помехи
Данные
Сигнал
Принятый сигнал
Данные
Исходный пункт - источник информации. Его

природу - неотъемлемая частью нашей жизни. Норберт Виннер, один из

Формула Хартли

Формула Шеннона

H - энтропия системы, k - коэффициент Больцмана, известный в

и информацией:



или в дифференциальной форме




При переходе системы из состояния

в источнике, может быть разложе-
но на последовательности двоичных решений с

Рассмотрим три события a, b и с. которые происходят с вероятностями 1/2,1/3 и 1/6, соответственно.

1/2

1/3

1/6

a

b

c

1/2

b

1/2

a

1/6

1/3

Преобразование в двоичное дерево

Для того, чтобы выбрать одно из этих трех, мы можем ставить два независимых вопроса.

Да (1)

Нет (0)

Да (1)

Нет (0)

последовательность двоичных символов «0» или «1» . Такую последовательность будем

символов, требующихся для выражения одной буквы сообщения, что при отсутствии

где H(x) - энтропия источника; - средняя длина кодового слова; D – «ичность» кода (для двоичного кода D=2, для троичного кода D=3, для восьмеричного кода D=8, для шестнадцатеричного кода D=16).

Кодирование информации

кодов были даны впервые Шенноном и Фэно.
Алгоритм Шеннона-Фэно: буквы

Кодирование информации Код Шеннона-Фэно

и среднее число символов на букву

где - число символов в кодовой комбинации, соответствующей букве .

0 1
0 0 0 0 1
0 0 0 0 0
Энтропия

Кодирование информации Код Шеннона-Фэно

1

i

3

4

2

5

6

7

- шаги

однозначному построению кода. Ведь при разбиении на подгруппы можно сделать

Алгоритм Хаффмана для двоичного кода. Буквы алфавита сообщений выписываются в основной столбец в порядке убывания вероятностей. Две последние буквы объединяются в одну вспомогательную букву, которой приписывается суммарная вероятность. Вероятности букв, не участвовавших в объединении, и полученная суммарная вероятность снова располагаются в порядке убывания вероятностей в дополнительном столбце, а две последние объединяются. В случае, когда несколько знаков имеют одинаковые вероятности, объединяются те два из них, которые до этого имели наименьшее число объединений. Процесс продолжается до тех пор, пока не получим единственную вспомогательную букву с вероятностью, равной единице.

Коды Хаффмана принадлежат к семейству кодов с переменной длиной кодовых слов. Самый известный код переменной длины – азбука Морзе. Основная идея азбуки Морзе - передавать часто встречающиеся буквы кодовыми словами короткой длины и, наоборот, редко встречающиеся буквы длинными кодовыми словами. Такой способ кодирования называют так же кодированием с минимальной избыточностью.

перехода сообщения по строкам и столбцам таблицы.
Для наглядности строится кодовое

Кодирование информации
Код Хаффмана

0,22

0,20

буквы соответствующую ей кодовую комбинацию:

Кодирование информации
Код Хаффмана

Коды Хаффмана играют важнейшую роль в кодировании изображений. Они являются основной частью стандартов JPEG, MPEG.

0,58

1

1

0

1

1

1

0

0

1

0

0

0,42

0,32

0,26

0,16

0,10

0,10

0,06

0,02

0,04

0,16

0,16

0

1

0

0,22

0,20

те их обобщения (транспортные сети, гиперграфы и др.), на которые

отношений между каждой парой этих объектов может быть изображена на

Граф с ребрами

Граф с дугами

Вершины – города; ребра (дуги) - дороги

различных формах. Ниже приведена одна из них:


где X –

Неориентированный граф

Ориентированный граф

вершин графа ребру или дуге и, наоборот, ребер или дуг

Вершина инцидентна ребрам

Ребро инцидентно вершинам

и т.д.

или дуге, всегда равно двум, так как они являются концевыми

смежными, если они различны и между ними существует ребро или

пример двух смежных вершин

изолированная вершина

пример смежных ребер

смежных вершин или дуг, соединяющих вершины

Эйлеров маршрут –
( )
Сколько эйлеровых маршрутов на графе? Ответ: 3 .

Гамильтонов маршрут –

Есть ли еще гамильтоновы маршруты на графе? Ответ: да, есть.

решена Эйлером в 1736 году. План расположения мостов в Кенигсберге

План расположения мостов в Кенигсберге в ХV111 веке

ребер, соединяющих вершины
и

Длина гамильтонова маршрута

равна пяти.

называют полным, если любые

называют пустым,

Пустой граф

Полный граф

вершины .

его ребра или вершины имеют дополнительные характеристики: продолжительность во времени,

Реберно-взвешенный граф

и сводится к поиску в неориентированном графе с весовыми значениями

Теорема Дирака. Граф гамильтонов, если степень любой его вершины v удовлетворяет неравенству .
Теорема О.Оре. Граф гамильтонов, если степени любых двух его смежных вершин v и u удовлетворяют неравенству .

В 1859 г. Уильям Гамильтон предложил математическую игру-головоломку с обходом вершин додекаэдра, положив начало одного из самых известных направлений теории графов.

Додекаэдр с n=20

Игрушка с додекаэдром

Додекаэдр имеет 12 граней (пятиугольных), 30 рёбер и 20 вершин (в каждой сходятся 3 ребра. 

доски шахматным конем (Леонард Эйлер, 1757). Найти последовательности ходов, которые

Основы теории графов
Задача коммивояжера

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

в ограниченных пределах.

Использовано цифровое изображение (10000 точек). Вершины графа

Основы теории графов
Задача коммивояжера

требуется найти наилучшее из конечного, но очень большого числа возможных

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

Неориентированный граф и его матрица инциденции

для ориентированного графа

Ориентированный граф и его матрица инциденции

– это бинарное отношение принадлежности элемента одного множества X другому

Неориентированный граф
и его матрица смежности

Ориентированный граф
и его матрица смежности

весов реберно-взвешенного

Неориентированный, реберно-взвешенный граф и его матрица смежности

Пример.

Красным показана окрестность вершины

достижимости связаны с представлением графа

где - множество вершин, достижимых из вершины за p шагов;

множество вершин, достижимых из вершины
за 2,…,p шагов;

Тогда для построения матрицы достижимости удобно воспользоваться матрицей смежности :

где - единичная матрица с единицами на главной диагонали.

Двухкомпонентный граф

к графу без циклов и петель, называют цикломатическим числом и

m - число ребер, n - число вершин, - число компонент связности.

Граф без циклов и петель

цветов называют разбиение множества вершин графа на попарно непересекающиеся

Хроматическое число графа G – наименьшее число , при котором никакие две смежные вершины графа не могут быть окрашены в один цвет.
Нахождение хроматического числа трудоемкая задача, имеющая сложный алгоритм и требующая большого объема вычислений.
Оценку можно дать, используя два эвристических правила.
Правило 1 определяет : хроматическое число полного n- вершинного графа равно n ; пустого графа – 1; графа с циклом четной длины – 2; графа с циклом нечетной длины – 3; графа типа дерево – 2.
Правило 2 определяет :

графа G - наибольшее число вершин полного

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

Плотные графы являются менее «уязвимыми».

графа G - наибольшее число вершин полного

Очевидно, что

расставить на шахматной доске наибольшее число ферзей, чтобы они не

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

Военные операции, политика

графа G – число вершин в наибольшем

на шахматной доске наименьшее число ферзей так, чтобы каждая клетка

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

Размещение магазинов на сети населенных пунктов

графа G – наименьшее число вершин смежных