Алгоритмы. Понятия. Свойства алгоритмов презентация

Содержание

Тема 1. Алгоритмы. Понятия. Свойства алгоритмов. Теория алгоритмов

Слайд 1Математическая логика Теория алгоритмов

Слайд 2Тема 1. Алгоритмы. Понятия. Свойства алгоритмов.
Теория алгоритмов

Слайд 33
Определения
Родоначальник термина «алгоритм»
Великий ученый средневекового Востока
Мухаммед ибн Мусса ал-Хорезми
(Мухаммед

сын Муссы из Хорезма)
783 – 850 гг.

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

Известен как математик, астроном и географ.
В девятом веке он переселился в Багдад, где с 815 года возглавлял «Дом мудрости» – хранилище рукописей, созданное арабскими халифами.

Автор двух знаменитых трактатов: по арифметике и алгебре.
«Dixit algorizmi» – «Сказал Алгоризми».

Слайд 44
Определения
Алгоритм - это строгая, четкая последовательность математических и логических операций, приводящая

к решению задачи.

В Толковом словаре по информатике (1991г.) дано общепринятое понятие: Алгоритм - точное предписание, определяющее вычислительный процесс, ведущий от варьируемых начальных данных к искомому результату.

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

Запись алгоритма на языке программирования называется программой.

Слайд 55
Определения
Математические определения:

«В математике принято понимать под «алгоритмом» точное пред-писание, определяющее вычислительный

процесс, ведущих от варьируемых исходных данных к исходному результату».

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

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

Слайд 66
Свойства алгоритмов
Описание основных свойств помогает углубить само понятие алгоритма.
Каждый алгоритм должен

обладать следующими свойствами:

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

Детерминированность (определённость). В каждый момент времени следующий шаг работы однозначно определяется состоянием системы. Таким образом, алгоритм выдаёт один и тот же результат (ответ) для одних и тех же исходных данных.
С другой стороны, существуют вероятностные алгоритмы, в которых следующий шаг работы зависит от текущего состояния системы и генерируемого случайного числа. Однако, при включении метода генерации случайных чисел в список «исходных данных» вероятностный алгоритм становится подвидом обычного.

Слайд 77
Свойства алгоритмов
Понятность — алгоритм должен включать только те команды, которые доступны исполнителю

и входят в его систему команд.

Завершаемость (конечность) — в более узком понимании алгоритма как математической функции, при корректно заданных исходных данных алгоритм должен завершать работу и выдавать результат за конечное число шагов. С другой стороны, вероятностный алгоритм может и никогда не выдать результат, но вероятность этого равна 0.

Массовость (универсальность). Алгоритм должен быть применим к разным наборам исходных данных.

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

Слайд 88

Способы задания алгоритмов
На практике наиболее распространены следующие формы представления алгоритмов:
Словесная 
(запись на

естественном языке);
 
Например.
Записать алгоритм нахождения наибольшего общего делителя (НОД) двух натуральных чисел (алгоритм Эвклида). 

Алгоритм может быть записан следующим образом:
задать два числа;
если числа равны, то взять любое из них в качестве ответа и остановиться, в противном случае продолжить выполнение алгоритма;
определить большее из чисел;
заменить большее из чисел разностью большего и меньшего из чисел;
повторить алгоритм с шага 2.

Слайд 99

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

включающие в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.);

Пример записи алгоритма на школьном АЯ :
алг Сумма квадратов (арг цел n, рез цел S)
дано | n > 0
надо | S = 1*1 + 2*2 + 3*3 + ... + n*n
нач цел i
ввод n; S:=0
нц для i от 1 до n
S:=S+i*i
кц
вывод "S = ", S
кон

3. Программный (тексты на языках программирования).

Слайд 1010


Блок-схемы алгоритмов
4. Графическая (изображения из графических символов);

На территории Российской Федерации действует единая

система программной документации (ЕСПД), частью которой является Государственный стандарт — ГОСТ 19.701-90 «Схемы алгоритмов программ, данных и систем» [1].
Не смотря на то, что описанные в стандарте обозначения могут использоваться для изображения схем ресурсов системы, схем взаимодействия программ и т.п., в настоящей статье описана лишь разработка схем алгоритмов программ.

Рассматриваемый ГОСТ практически полностью соответствует международному стандарту ISO 5807:1985.

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

Слайд 1111


Блок-схемы алгоритмов
4.2.4. линии должны подходить к символу слева, либо сверху, а

исходить снизу, либо справа К ЦЕНТРУ СИМВОЛА.





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

4.2.3. Две или более входящие линии могут объединяться в одну исходящую линию. Если две или более линии объединяются в одну линию, место объединения должно быть смещено.

Пример:
 

Слайд 1212


Блок-схемы алгоритмов

Слайд 1313



Блок-схемы алгоритмов

Слайд 1414



Блок-схемы алгоритмов

Слайд 1515



Блок-схемы алгоритмов

Слайд 1616




Блок-схемы алгоритмов
Блок-схема алгоритма Евклида
поиска НОД :

Слайд 1717




Проблема уточнения понятия алгоритма
30 гг. XX века
количество исследований перешло на качественно

новый уровень

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

Свести алгоритм к функции можно так:
Говорят, что функция f(x) вычислима, если существует алгоритм, вычисляющий ее значения f, по каждому аргументу x из области определения.

Основные направления по уточнению понятия «алгоритма» и их авторы:
1) Общерекурсивные функции (К. Гёделя, С. Клини, Ю. Эрбран)
2) λ - рекурсивные функции (Л. Гёделя, С. Клини)
3) λ - определение функции (А. Чёрч, С. Клини)
4) Машины Тьюринга-Поста (А. Тьюринг, Е. Пост)
5) Марковские алгоритмы (А. А. Марков)
6) Графические схемы (Р. Петер)

Слайд 18Тема 2. Машины Тьюринга – Поста.
Теория алгоритмов

Слайд 1919




Машины Тьюринга - Поста
английский математик Алан Мэтисон Тьюринг
Американский математик
Польского (русского)

происхождения
Эмиль Леон Пост

А.М. Тьюринг опубликовал первую свою работу в журнале Лондонского матема-тического сообщества (London Mathematical Society (LMS)), том. 58, за 1936 г. (рукопись подана в редакцию – 19.04.1935 г.) под названием «О вычислимых чис-лах, с применением к проблеме невычислимости».

Статья Поста вышла в свет в журнале символической логики (Jornal of Sym-bolic Logic) в третьем номере, за сентябрь 1936 г. Она насчитывает 3 страницы и носит более общий характер.

Слайд 2020




Машины Тьюринга - Поста
Определение алгоритма через понятие вычислительной машины основано на

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

Чтобы решить проблему интерпретации (понимания) правил необходимо установить:

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

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

Слайд 2121




Машины Тьюринга - Поста
Определение алгоритма через понятие вычислительной машины основано на

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

Чтобы решить проблему интерпретации (понимания) правил необходимо установить:

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

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

Слайд 2222




Машины Тьюринга - Поста
Машина Тьюринга - абстрактная (воображаемая) "вычислительная машина" некоторого

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

С помощью машины Тьюринга можно доказать существование или не существование алгоритмов решения различных задач.

Так как машина выполняет определенный алгоритм, то к машине предъявляются требования, вытекающие из свойств алгоритмов.

Во-первых, машина должна быть полностью детерминированной (вычисления должны быть точные и общепонятные) и действовать в соответствии с заданной системой правил.
Во-вторых, она должна допускать ввод различных “начальных данных” (соответствующих различным задачам из данного класса задач).
В-третьих, заданная система правил работы машины и класс решаемых задач должны быть согласованы так, чтобы всегда можно было “прочитать” результат работы машины.

Слайд 2323




Одноленточная Машина Тьюринга
Классической моделью считается одноленточная машина Тьюринга.
Под одноленточной машиной

Тьюринга понимают кибернетическое устройство, состоящее из следующих элементов:
• бесконечной ленты, разделенной на ячейки,
• управляющей головки, способной читать символы, содержащиеся в ячейках ленты, и записывать символы в эти ячейки,
• выделенной ячейки памяти, содержащей символ внутреннего алфавита, задающий состояние машины Тьюринга,
• механического устройства управления, обеспечивающего перемещение головки относительно ленты,
• функциональной схемы — области памяти, содержащей команды (программу) машины Тьюринга (эта область доступна только для чтения).

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

Слайд 2424




Одноленточная Машина Тьюринга
Лента
Поскольку бесконечную ленту физически смоделировать затруднительно, обычно предполагается что

она конечная. В процессе работы к существующим ячейкам машина может пристраивать новые ячейки, так что лента может считаться потенциально неограниченной в обе стороны. Каждая ячейка ленты может находиться в одном из конечного множества состояний. Эти состояния будем обозначать символами a0, a1, …, am или другими символами. Совокупность таких символов называется внешним алфавитом машины, а сама лента часто называется внешней памятью машины. Если ячейка пустая, будем считать, что в ней
записан условный символ λ.
Без ограничения общности ленту можно считать бесконечной лишь с одной стороны. В этом случае для удобства введем специальный символ ∂, обозначающий начало ленты. Этот символ имеет строго определенное место, его нельзя ни стирать, ни сдвигать. Тогда ленту можно считать однонаправленной (бесконечной вправо) и ее ячейки удобно просматривать слева направо.

Слайд 2525




Одноленточная Машина Тьюринга
Управляющая головка
Управляющая головка – это некоторое устройство, которое может

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

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

Внутренняя память
Внутренняя память машины – это выделенная ячейка памяти, которая в каждый рассматриваемый момент находится в некотором «состоянии».
Предполагается, что число возможных состояний внутренней памяти конечное и для каждой машины фиксированное. Состояние внутренней памяти мы будем обозначать символами S0, S1, …, Sn или любыми другими символами, не входящими во внешний алфавит машины. Совокупность символов, обозначающих состояния внутренней памяти, называется внутренним алфавитом машины или внутренними состояниями машины.

Слайд 2626




Одноленточная Машина Тьюринга
Одно из этих состояний называется начальным, с него начинает

работу любая машина, пусть это будет состояние S0. В процессе работы машина может какое-то количество шагов оставаться в состоянии S0 или возвращаться в него позднее. Еще одно специальное состояние – заключительное. Символ, обозначающий заключительное состояние, будет называться стоп-символом. Роль стоп-символа далее будет играть символ Ω.













Устройство машины Тьюринга

Слайд 2727




Работа Машины Тьюринга
Конфигурация машины Тьюринга – совокупность, образованная содержимым текущей обозреваемой

ячейки aj и состоянием внутренней памяти Si.
Работа машины состоит в том, что она из данного «состояния» по истечении одного такта работы механического устройства переходит в следующее «состояние», затем из этого состояния по истечении такта работы переходит в новое состояние и так далее.
Таким образом, если машина, имея внутреннее состояние Si и воспринимая ячейку ленты с символом aj, изменяет свое внутреннее состояние на Sq и одновременно содержимое воспринимаемой ячейки заменяет символом ar, а управляющая головка сдвинется на одну ячейку вправо (R), то говорят, что
машина выполняет команду соответственно Si aj→ak R Sl.
Если управляющая головка сдвинется влево (L) или останется
неподвижной (Н), то команды записываются соответственно: Si aj→ak L Sl
Si aj→ak H Sl

Слайд 2828




Работа Машины Тьюринга
Программа машины Тьюринга – совокупность команд установленного формата.

Программа машины

с символами {a0, a1, …, an } и состояниями {S0, S1, …, Sm } содержит максимум n·m команд.

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

Тезис Тьюринга – любой алгоритм можно преобразовать в машину Тьюринга.

Эту гипотезу невозможно доказать, потому что она оперирует неформальным понятием алгоритма. Однако обоснование гипотезы есть: все алгоритмы, придуманные в течение столетий, могут быть реализованы на машине Тьюринга. Чтобы опровергнуть основную гипотезу, необходимо придумать такой алгоритм, который невозможно было бы реализовать на машине Тьюринга, но пока такого алгоритма нет.

Слайд 2929




Приеры работы Машины Тьюринга
Пример 1 Зададим машину Т1, которая копирует начальную

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

Допустим, что информация на ленте задана в виде конечной последовательности из единиц, а символ * означает, пустую ячейку. Кроме того, нам понадобится вспомогательный при вычислениях символ 0. Итак, А1={1,*,0}. Пусть S={s0,s1,s2,s3,s4,s5} внутренние состояния машины. Программу Т1 определим в виде следующей таблицы

Слайд 3030




Приеры работы Машины Тьюринга
Пример 3.1.1
В таблице машины имеются незаполненные клетки (прочерк).

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

Слайд 3131




Приеры работы Машины Тьюринга
Пример 3.1.1











В описаниях ситуаций на ленте положение

считывающей головки отмечено над обозреваемым символом в виде внутреннего состояния машины.
Так, в первом такте машина Т1 обозревает в ячейке ленты символ 1 в состоянии s2 . При этом она идет вправо, не меняя своего внутреннего состояния и символа в ячейке.
В такте шесть она имеет состояние s3 и обозревает пустую ячейку. В этой ситуации, согласно программе, она печатает 1, переходит в состояние s4 и передвигает головку на одну ячейку влево.

Слайд 3232




Приеры работы Машины Тьюринга
Пример 2 Рассмотрим машину Т2 с внутренними состояниями

s0, s1, s2, s3 и с внешним алфавитом {1,*} , программа которой задана следующей таблицей:










Машина Т2 к заданной группе единиц добавляет справа одну единицу, воз- вращается в исходное положение и останавливается.

Слайд 3333




Приеры работы Машины Тьюринга
Пример 3 Пусть А3={1, *}, S={s0,s1,s2,s3,s4}.












Машина Т3

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

Слайд 3434




Универсальная Машина Тьюринга (УМТ)
Универсальные машины
Тьюринг показал возможность построения определённой вычислительной машины

U, универсальной в том смысле, что на U можно выполнить любое вычисление.
Универсальная машина – машина Тьюринга, обладающая способностью путём подходящего кодирования выполнить любое вычисление.
Однако к этому, несомненно, надо присоединить то условие, что кодирование должно быть в некотором смысле простым.
Пусть машина А имеет m символов aj и n внутренних состояний Si . Закодируем знаки, используемые при написании программы работы такой машины следующим образом:
aj = 1…1 (a1=1, a2=11, a3=111 и т.д.) R = 3
Si = 2…2 (S1=2, S2=22, S3=222 и т.д.) L = 33
H = 333
В этом случае всю программу работы машины можно записать неким числом, причем возможны два варианта записи:
1. С разделителем команд, допустим Х, которые можно закодировать числом 4. В этом случае классическая запись S old a old→a new R S new,
2. Без разделителя команд. В этом случае команды следует писать в формате a old S old a new R S new, тогда две команды, записанные непосредственно друг за другом, будут явно различаться элементарным анализатором.

Слайд 3534




Универсальная Машина Тьюринга (УМТ)
Пример машины Тьюринга, которая на пустой ленте бесконечно

много раз печатает последовательность 001.
Из соображений удобства формат записи будет следующим aSi → a'{R,L,H}Sj. При такой записи обозначение символа указывается ранее обозначения состояния. Цель данной перестановки довольно банальная: избежать наличия лишнего разделителя.
Программа такой машины выглядит следующим образом (λ-пустой знак):
λ A 0 R B Закодируем символы и состояния: λ=1 A=2
λ B 0 R C 0=11 B=22
λ C 1 R A 1=111 C=222
Тогда запись программы машины будет выглядеть так (пробелы поставлены для повышения читаемости, в реальности их нет):
1 2 11 3 22 1 22 11 3 222 1 222 111 3 2
В итоге каждая МТ представлена числом – это дескриптивное (описательное) число машины. Вместе с тем оно является кодом для входного слова.
Таким образом решается проблема унификации записи программы машины Тьюринга и входного слова на её ленте.

Несмотря на это, построение реально работающей универсальной машины Тьюринга представляет собой довольно сложный процесс.

Слайд 36Тема 3. Нормальные алгоритмы Маркова.
Теория алгоритмов

Слайд 3736




Андрей Андреевич Марков
Андрей Андреевич Марков
(22.09.1903 - 11.10.1979 гг.)
Выдающийся советский

математик и логик, член-корреспондент АН СССР, заведующий кафедрой математической логики Московского государственного университета.

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

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

Слайд 3837




Идея нормальный алгорифмов Маркова
Если попытаться уйти от наличия самого управляющего механизма

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

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

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

Таким образом, формируется идея нормального алгоритма переработки входного слова, называемого в литературе алгоритмом Маркова.

Слайд 3938





Определение
Нормальный алгоритм Маркова – математическое построение, предназначенное для уточнения понятия алгоритм,

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

Нормальные алгоритмы можно рассматривать как обобщение машины Тьюринга. В свою очередь работу машин Тьюринга можно рассматривать как переработку начального слова некоторого нормального алгоритма. Этот алгоритм получается сразу же из таблицы машины.

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

Слайд 4039





Формат команды
Формат команды (строки) следующий: {ai} → {bj} [•],
где
{ai} -

последовательность символов, которая ищется в слове,
→ - знак перехода к операции записи,
{bj} - последовательность символов, которая записывается вместо найденной последовательности,
[•] - знак принудительного окончания алгоритма (необязательный параметр).
Λ – служебный знак, обозначающий пустой символ, присутствует везде: изначально на ленте (если она пустая), справа и слева от каждого символа (если на ленте записано слово).

Программа (алгоритм) представляет собой совокупность строк указанного вида, причем порядок строк имеет важнейшее значение.

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

Слайд 4140





Примеры
Пример 1 Пусть в алфавите A2={a,b,c} задана система ориентированных подстановок:
1.

cb → cc
2. cca → ab
3. ab → bca
4. ca →Λ
Этот алгоритм, будучи применен к слову cabc, никогда не обрывается:
cabc → cbcac→ cccab→ cabc (3,1,2 правила) – получилось первоначальное слово, т.е.

Если же брать слово baaacca, то после нескольких шагов процесс оборвется на слове bb:

baaacca → baaabca → baabcaca → babcacaca → bbcacacaca → …→ bb.
2 3 3 3 4

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

Слайд 4241






Примеры
Пример 2 Пусть в одном и том же алфавите заданы два

нормальных алгоритма I1 и I2 , отличающиеся друг от друга только порядком подстановок:
I1: I2:
1. ab→bac 1. bc→bb
2. ac→ca 2. ab→bac
3. aa→Λ 3. ac→ca
4. bc →bb 4. aa→Λ
5. bb→Λ 5. bb→Λ

Покажем, что I1(abbc)≠I2(abbc):

I1(abbc) 1 → bacbc 2 → bcabc 1 → bcbacc 2 → bcbcac 2 → bcbcca 4 → bbbcca 4 → bbbbca 4 → 4 → bbbbba 5 → …5 → ba.

I2(abbc)1 → abbb 2 → bacbb 3 → bcabb 1 → bbabb 2 → bbbacb 3 → bbbcab 1 → bbbab 2 → bbbbbac 3 → bbbbbca 1 → bb bb bba → 5 ... → a.

Этот пример показывает, что в нормальных алгоритмах имеет значение
не только сами подстановки, но и их порядок.

Слайд 4342






Вычисление арифметических функций
Определение
Функция y=F(x1,x2,…,xn) называется арифметической функцией, если аргументы xi

и значение y принимают только натуральные значения из N*={0, 1, 2, 3,…}.

Положительные натуральные числа зададим как слова в однобуквенном алфавите А={1}: пусть число n задается в виде слова из n «палочек».

Далее примеры на доске…

Слайд 44Тема 1. Основные определения
Теория графов

Слайд 45 Леона́рд Э́йлер (4 апреля 1707, Базель, Швейцария —


7 сентября 1783, Санкт-Петербург, Российская империя)

— швейцарский, немецкий и российский математик, внёсший значительный вклад
в развитие математики, а также
механики, физики, астрономии
и ряда прикладных наук.

Почти полжизни провёл в России, где внёс существенный вклад в становление российской науки.

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

История возникновения теории графов

Слайд 46 Бывший Кёнигсберг (ныне Калининград) расположен на реке Прегель.

В пределах города река омывает два острова. С берегов на острова были перекинуты мосты. Старые мосты не сохранились, но осталась карта города, где они изображены.
Вопрос: можно ли пройти по всем мостам и вернуться в начальный пункт, побывав на каждом мосту только один раз?




Задача о Кёнигсбергских мостах

История возникновения теории графов

Слайд 47Задача о Кёнигсбергских мостах

КАРТА ГОРОДА И СООТВЕТСТВУЮЩИЙ ЕЙ ГРАФ
Граф

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

вершины

рёбра

f

a

b

e

g

c

d

A, B, C, D

a, b, c, d, e, f, g

История возникновения теории графов

Слайд 48
если все вершины графа четные, то

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

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

граф с более чем двумя нечетными вершинами невозможно начертить одним росчерком.

История возникновения теории графов

Решая задачу про кенигсбергские мосты, Эйлер установил следующие свойства графа:

Слайд 49 Решение задачи Эйлера: нельзя пройти по всем мостам

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

История возникновения теории графов

Слайд 50Определения
Граф – это набор вершин (узлов) и соединяющих их ребер (дуг).






Направленный граф (ориентированный, орграф) – это граф, в котором все дуги имеют направления.

Цепь – это последовательность ребер, соединяющих две вершины (в орграфе – путь).

Цикл – это цепь из какой-то вершины в нее саму.

Взвешенный граф (сеть) – это граф, в котором каждому ребру приписывается вес (длина).

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

парой вершин.
k-cвязный граф – это граф, который можно разбить на k связных частей.



Полный граф – это граф, в котором проведены все возможные ребра (n вершин → n(n-1)/2 ребер).


Слайд 52________________________________________________________________________
Основные понятия теории графов
Плоский граф – который можно

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

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

плоский граф, изоморфный (равный) графу,
изображённому на рисунке а)

Слайд 53________________________________________________________________________
Основные понятия теории графов
Грань - многоугольник плоского графа, не

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

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

грань

Слайд 54________________________________________________________________________
Основные понятия теории графов
Дерево — это связный ациклический граф

(то есть граф, не содержащий циклов, между любой парой вершин которого существует ровно один путь).

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

Слайд 55________________________________________________________________________
Основные понятия теории графов
При изображении графов на рисунках

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

=

=

Все три фигуры на рисунке изображают один и тот же граф.

Слайд 56Операции над графами
Объединением графов и называется

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















Слайд 57
х3


х4
х6
G1




V2
V1
V3
V4


V5
х3
х1
х5
G=G1UG2


х6



х4
х4
х3
V3
V2
V1
G=G1∩G2

х2
х2





V2
V1
V3
V4
х7

V5


х1
G=G1 G2


V4
х7
х5
х6

Слайд 58Подграфом графа называется граф , все

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







Слайд 59 Цикломатическим числом неориентированного графа G называется число ,

где - число

его рёбер;
- число связных компонент графа;
- число вершин.
Цикломатическое число показывает, сколько рёбер нужно удалить из графа, чтобы в нём не стало циклов.





Цикломатическое число графа

Слайд 60________________________________________________________________________
Задачи на графы. Идея чётности. Раскраска.
Задача №1.
Аркадий, Борис,

Владимир, Григорий и Дмитрий при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу). Сколько всего рукопожатий было сделано?

Решение.

Пусть каждому из пяти молодых людей соответствует определенная точка на плоскости, названная первой буквой его имени, а — отрезок – производимое рукопожатие.

Слайд 61________________________________________________________________________
Задачи на графы. Идея чётности. Раскраска.
Задача №1.
Аркадий, Борис,

Владимир, Григорий и Дмитрий при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу). Сколько всего рукопожатий было сделано?

Решение.


Если полный граф имеет n вершин, то количество ребер будет равно
n(n-1)/2.

Ответ: было совершено 10 рукопожатий.

Слайд 62________________________________________________________________________
Задачи на графы. Идея чётности. Раскраска.
Задача №2.
Какую из

фигур можно нарисовать одним росчерком, не отрывая карандаша от бумаги?

Ответ: фигуры 1, 2, 4, 5 – можно, фигуру 3 – нельзя, т.к. только
у этой фигуры количество нечётных вершин больше двух.

Слайд 63________________________________________________________________________
Задачи на графы. Идея чётности. Раскраска.
Задача №3.
Алёша, Боря

и Витя учатся в одном классе. Один ездит домой из школы на автобусе, другой – на трамвае, третий – на троллейбусе. Однажды после уроков Алёша пошёл проводить друга до остановки автобуса. Когда мимо них проходил троллейбус, третий друг крикнул из окна: «Боря, ты забыл в школе тетрадь!» Кто на чём ездит домой?

Решение.

Ответ:

Алёша ездит домой на трамвае,
Боря - на автобусе,
Витя – на троллейбусе.

Слайд 64________________________________________________________________________
Задачи на графы. Идея чётности. Раскраска.
Задача №4.
Между девятью

планетами солнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам: Земля – Меркурий; Плутон – Венера; Земля – Плутон; Плутон – Меркурий; Меркурий – Венера; Уран – Нептун; Нептун – Сатурн; Сатурн – Юпитер; Юпитер – Марс и Марс – Уран. Можно ли долететь на рейсовых ракетах с Земли до Марса?

Решение.

Ответ: очевидно, что долететь с Земли до Марса нельзя.

Слайд 65________________________________________________________________________
Задачи на графы. Идея чётности. Раскраска.
Задача №5.
Доска имеет

форму двойного креста, который получается, если из квадрата 4x4 убрать угловые клетки. Можно ли обойти ее ходом шахматного коня и вернуться на исходную клетку, побывав на всех клетках ровно по одному разу?

Решение.

Ответ: да, можно.

Слайд 66________________________________________________________________________
Задачи на графы. Идея чётности. Раскраска.

Задача №6.
Раскрасить вершины графа

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


Это число называется хроматическим (цветным) числом графа.

В данной задаче хроматическое число равно 3.

Слайд 67 Известно, что в настоящий момент:
Ваня сыграл шесть партий;
Толя сыграл

пять партий;
Леша и Дима сыграли по три партии;
Семен и Илья сыграли по две партии;
Женя сыграл одну партию.

Требуется определить:
с кем сыграл Леша.

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

Задача №7.

Слайд 68









Число в скобках называют степенью вершины, оно показывает сколько ребер выходит

из данной вершины

Ваня (6)

Толя (5)

Леша (3)

Дима (3)

Семен (2)

Илья (2)

Женя (1)

Изобразим участников турнира точками
Для каждой точки укажем ее имя
(по первой букве имени игрока)
и количество партий, сыгранные этим игроком

Слайд 69







Начать построение ребер следует с вершины В, так как это единственная

вершина,
которая соединяется со всеми другими вершинами графа

Ваня (6)

Толя (5)

Леша (3)

Дима (3)

Семен (2)

Илья (2)

Женя (1)

Будем строить ребра графа с учетом степеней вершин

Слайд 70









Для вершин В и Ж построены все возможные ребра
Ваня (6)
Толя (5)
Леша

(3)

Дима (3)

Семен (2)

Илья (2)

Женя (1)

Сделаем первые выводы:

Слайд 71









Теперь однозначно определяются ребра вершины Т.
С учетом ребра ВТ надо

построить четыре ребра

Ваня (6)

Толя (5)

Леша (3)

Дима (3)

Семен (2)

Илья (2)

Женя (1)

Построим следующие ребра


Слайд 72












Все возможные ребра теперь построены для вершин Ж, В,

Т, а также для вершин С и И

Ваня (6)

Толя (5)

Леша (3)

Дима (3)

Семен (2)

Илья (2)

Женя (1)

Пора делать новые выводы


Слайд 73














ОТВЕТ: Леша играл с Толей, Ваней и Димой
Ваня (6)
Толя (5)
Леша

(3)

Дима (3)

Семен (2)

Илья (2)

Женя (1)


Требовалось определить: с кем сыграл Леша.

Граф к задаче построен

Слайд 74В одном дворе живут четыре друга.
Вадим и шофер старше Сергея,
Николай

и слесарь занимаются боксом,
Электрик-младший из друзей.
По вечерам Андрей и токарь играют в домино против Сергея и электрика.
Определите профессию каждого из друзей.

Задача №8.

Слайд 75Вадим
Коля
Сергей
Андрей
слесарь
токарь
электрик
шофер
Начинаем анализировать полученную схему.
От каждого верхнего кружка должно исходить 4 линии

к кружкам нижнего ряда,одна из которых сплошная(прочная связь) ,три-пунктирные. (разрывная связь). И от кружков нижнего ряда-аналогично.

От Сергея отходит 3 разрывные связи, значит, четвертая- прочная связь

Ответ готов:
Вадим-токарь, Сергей-слесарь, Коля-электрик, Андрей-шофер


Слайд 76Описание графа
Матрица смежности – это матрица, элемент M[i][j] которой равен 1,

если существует ребро из вершины i в вершину j, и равен 0, если такого ребра нет.

Список смежности

Слайд 77Матрицей инцидентности называется таблица, состоящая из n строк (вершины) и т

столбцов (рёбра), в которой:
для неориентированного графа:
, если вершина инцидентна ребру ;
, если вершина не инцидентна ребру ;
для ориентированного графа:
, если вершина является началом дуги ;
, если вершина не инцидентна дуге ;
, если вершина является концом дуги.





Слайд 78Задача. Пусть граф G задан матрицей смежности А. Построить диаграмму этого

графа, если
Решение. Поскольку матрица А несимметрична (например ), то она может задавать только ориентиро- ванный граф.











V1

V2

V3

V4

V5

V6


Слайд 79Задача. Пусть граф G задан матрицей смежности А. Построить диаграмму этого

графа, если
Решение. Диаграмму графа, имеющего шесть вершин, можно представить следующим образом

V5

V1

V4

V6

V2

V3









Слайд 80Матрица и список смежности

Слайд 81Построения графа по матрице смежности

Слайд 82Как обнаружить цепи и циклы?
Задача: определить, существует ли цепь длины k

из вершины i в вершину j (или цикл длиной k из вершины i в нее саму).

M2[i][j]=1, если M[i][1]=1 и M[1][j]=1

или

M[i][2]=1 и M[2][j]=1

или

M[i][3]=1 и M[3][j]=1



строка i

логическое умножение

столбец j

логическое сложение

M =

или

M[i][4]=1 и M[4][j]=1

Слайд 83Как обнаружить цепи и циклы?
M2 = M ⊗ M
Логическое умножение матрицы

на себя:

матрица путей длины 2

M2 =

⊗

=

M2[3][1] = 0·0 + 1·1 + 0·0 + 1·1 = 1



маршрут 3-2-1

маршрут 3-4-1

Слайд 84Как обнаружить цепи и циклы?
M3 = M2 ⊗ M
Матрица путей длины

3:

M3 =

⊗

=

на главной диагонали – циклы!

M4 =

⊗

=

Слайд 85Весовая матрица
Весовая матрица – это матрица, элемент W[i,j] которой равен весу

ребра из вершины i в вершину j (если оно есть), или равен ∞, если такого ребра нет.

Слайд 86Задача Прима-Краскала
Задача: соединить N городов телефонной сетью так, чтобы длина телефонных

линий была минимальная.

Та же задача: дан связный граф с N вершинами, веса ребер заданы весовой матрицей W. Нужно найти набор ребер, соединяющий все вершины графа (остовное дерево) и имеющий наименьший вес.

Слайд 87Жадный алгоритм
Жадный алгоритм – это многошаговый алгоритм, в котором на каждом

шаге принимается решение, лучшее в данный момент.

Шаг в задаче Прима-Краскала – это выбор еще невыбранного ребра и добавление его к решению.

Слайд 88Реализация алгоритма Прима-Краскала
Проблема: как проверить, что 1) ребро не выбрано, и

2) ребро не образует цикла с выбранными ребрами.
Решение: присвоить каждой вершине свой цвет и перекрашивать вершины при добавлении ребра.

3

2

4

5

Алгоритм:
покрасить все вершины в разные цвета;
сделать N-1 раз в цикле:
выбрать ребро (i,j) минимальной длины из всех ребер, соединяющих вершины разного цвета;
перекрасить все вершины, имеющие цвет j, в цвет i.
вывести найденные ребра.

4

Слайд 89Реализация алгоритма Прима-Краскала
Структура «ребро»:
type rebro = record
i,

j: integer; { номера вершин }
end;

const N = 5;
var W: array[1..N,1..N] of integer;
Color: array[1..N] of integer;
i, j, k, min, col_i, col_j: integer;
Reb: array[1..N-1] of rebro;
begin
... { здесь надо ввести матрицу W }
for i:=1 to N do { раскрасить в разные цвета }
Color[i] := i;
... { основной алгоритм – заполнение массива Reb }
... { вывести найденные ребра (массив Reb)}
end.

Основная программа:

весовая матрица

цвета вершин

Слайд 90Реализация алгоритма Прима-Краскала
for k:=1 to N-1 do begin
min := MaxInt;

for i:=1 to N do
for j:=i+1 to N do
if (Color[i] <> Color[j]) and
(W[i,j] < min) then begin
min := W[i,j];
Reb[k].i := i;
Reb[k].j := j;
col_i := Color[i];
col_j := Color[j];
end;
for i:=1 to N do
if Color[i] = col_j then
Color[i] := col_i;
end;

Основной алгоритм:

нужно выбрать всего N-1 ребер

цикл по всем парам вершин

учитываем только пары с разным цветом вершин

запоминаем ребро и цвета вершин

перекрашиваем вершины цвета col_j

Слайд 91Сложность алгоритма
Основной цикл:
O(N3)
for k:=1 to N-1 do begin
...
for

i:=1 to N do
for j:=i+1 to N do
...
end;

три вложенных цикла, в каждом число шагов <=N

растет не быстрее, чем N3

Требуемая память:

var W: array[1..N,1..N] of integer;
Color: array[1..N] of integer;
Reb: array[1..N-1] of rebro;

O(N2)


Количество операций:

Слайд 92Кратчайшие пути (алгоритм Дейкстры)
Задача: задана сеть дорог между городами, часть которых

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

Та же задача: дан связный граф с N вершинами, веса ребер заданы матрицей W. Найти кратчайшие расстояния от заданной вершины до всех остальных.

присвоить всем вершинам метку ∞;
среди нерассмотренных вершин найти вершину j с наименьшей меткой;
для каждой необработанной вершины i: если путь к вершине i через вершину j меньше существующей метки, заменить метку на новое расстояние;
если остались необработанны вершины, перейти к шагу 2;
метка = минимальное расстояние.

Алгоритм Дейкстры (E.W. Dijkstra, 1959)

Слайд 93Алгоритм Дейкстры

Слайд 94Реализация алгоритма Дейкстры
Массивы:
массив a, такой что a[i]=1, если вершина уже рассмотрена,

и a[i]=0, если нет.
массив b, такой что b[i] – длина текущего кратчайшего пути из заданной вершины x в вершину i;
массив c, такой что c[i] – номер вершины, из которой нужно идти в вершину i в текущем кратчайшем пути.
Инициализация:
заполнить массив a нулями (вершины не обработаны);
записать в b[i] значение W[x][i];
заполнить массив c значением x;
записать a[x]=1.

Слайд 95Реализация алгоритма Дейкстры
Основной цикл:
если все вершины рассмотрены, то стоп.
среди всех нерассмотренных

вершин (a[i]=0) найти вершину j, для которой b[i] – минимальное;
записать a[j]:=1;
для всех вершин k: если путь в вершину k через вершину j короче, чем найденный ранее кратчайший путь, запомнить его: записать b[k]:=b[j]+W[j,k] и c[k]=j.

Шаг 1:

Слайд 96Реализация алгоритма Дейкстры
Шаг 2:
Шаг 3:

Слайд 97Как вывести маршрут?
Результат работа алгоритма Дейкстры:
длины путей
Маршрут из вершины 0 в

вершину 4:

4



5

2

0




Сложность алгоритма Дейкстры:

O(N2)

два вложенных цикла по N шагов

Вывод маршрута в вершину i (использование массива c):
установить z:=i;
пока c[i]<>x присвоить z:=c[z] и вывести z.

Слайд 98Алгоритм Флойда-Уоршелла
Задача: задана сеть дорог между городами, часть которых могут иметь

одностороннее движение. Найти все кратчайшие расстояния, от каждого города до всех остальных городов.

for k: =1 to N
for i: = 1 to N
for j: = 1 to N
if W[i,j] > W[i,k] + W[k,j] then
W[i,j] := W[i,k] + W[k,j];

Если из вершины i в вершину j короче ехать через вершину k, мы едем через вершину k!

Слайд 99Алгоритм Флойда-Уоршелла
Версия с запоминанием маршрута:
for i:= 1 to N
for j

:= 1 to N
c[i,j] := i;
...
for k: =1 to N
for i: = 1 to N
for j: = 1 to N
if W[i,j] > W[i,k] + W[k,j] then begin
W[i,j] := W[i,k] + W[k,j];
c[i,j] := c[k,j];
end;

i–ая строка строится так же, как массив c в алгоритме Дейкстры

в конце цикла c[i,j] – предпоследняя вершина в кратчайшем маршруте из вершины i в вершину j

c[i,j] := c[k,j];

O(N3)

Слайд 100Задача коммивояжера
Задача коммивояжера. Коммивояжер (бродячий торговец) должен выйти из первого города

и, посетив по разу в неизвестном порядке города 2,3,...N, вернуться обратно в первый город. В каком порядке надо обходить города, чтобы замкнутый путь (тур) коммивояжера был кратчайшим?

Точные методы:
простой перебор;
метод ветвей и границ;
метод Литтла;
…
Приближенные методы:
метод случайных перестановок (Matlab);
генетические алгоритмы;
метод муравьиных колоний;
…

большое время счета для больших N

O(N!)

не гарантируется оптимальное решение

Слайд 101Другие классические задачи
Задача на минимум суммы. Имеется N населенных пунктов, в

каждом из которых живет pi школьников (i=1,...,N). Надо разместить школу в одном из них так, чтобы общее расстояние, проходимое всеми учениками по дороге в школу, было минимальным.
Задача о наибольшем потоке. Есть система труб, которые имеют соединения в N узлах. Один узел S является источником, еще один – стоком T. Известны пропускные способности каждой трубы. Надо найти наибольший поток от источника к стоку.
Задача о наибольшем паросочетании. Есть M мужчин и N женщин. Каждый мужчина указывает несколько (от 0 до N) женщин, на которых он согласен жениться. Каждая женщина указывает несколько мужчин (от 0 до M), за которых она согласна выйти замуж. Требуется заключить наибольшее количество моногамных браков.

Слайд 102Конец презентации

Похожие презентации

Стохастические модели управления запасами 297
Лекция 14. Метод перевала 571
Таблица умножения и деления на 2 287
Понятие множества 356
Взаимное расположение прямой и окружности 478
Статистика уровня жизни населения. Макроэкономическая статистика 656

Обратная связь

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

Email: Нажмите что бы посмотреть 

Что такое ThePresentation.ru?

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

Для правообладателей

Яндекс.Метрика