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

Словарь – это Вселенная в алфавитном порядке.

М. Вольтер

ГЛОССАРИЙ К МОДУЛЮ 1

Глава 1.

Множество — это любое объединение в одно целое М определенных, вполне различимых объектов m из нашего восприятия или мысли, которые можно считать элементами из М. Существует неформальное определение: множество — это многое, мыслимое как единое.

Элементами множества являются предметы, его составляющие.

Принадлежность элемента х множеству А определяется записью х Î А. Непринадлежность элемента х множеству В определяется записью y Ï B.

Высказывание — это предположение (предложение), которое считается истинным или ложным.

Предикатом называется высказывание, содержащее переменные, принимающее значения 1 или 0 в зависимости от значения переменных.

Мощностьюмножества конечного множества называется количество его элементов.

Квантор общности [ ( "xÎX)B(x)] означает, что для любого элемента x из множества X истинно высказывание B(x) об этом элементе.

Квантор существования [($ хÎX)B(x)] означает, что существует хотя бы один элемент x из множества X, для которого истинно высказывание B(x) об этом элементе.

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

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

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

Равными множествами считаются множества, содержащие одни и те же элементы и имеющие равную мощность.

Неравные множества состоят из различных элементов.

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

Ординарными множествами называются множества, не относящиеся к экстраординарным.

Подмножеством множества А называется множество В, если любой элемент множества В принадлежит множеству А.

Множество В строго включается в множество А, если одновременно выполняются два условия (В Í А & А ¹ В).

Множество В нестрого включается в множество А, если выполняется одно из двух условий (В Í А Ú А = В).

Глава 2.

Семейством подмножеств множества М называется множество всех подмножеств множества М.

Объединением множеств А и В называют множество С, которое состоит из тех элементов, которые принадлежат или множеству А, или множеству В, или обоим множествам одновременно.

Пересечением множеств А и В называют множество С, состоящее из тех элементов, которые принадлежат одновременно и множеству А, и множеству В.

Разностью множеств А и В называется множество С, состоящее из тех элементов, которые принадлежат множеству А и не принадлежат множеству В.

Дополнением множества А до некоторого универсального множества E называется множество, состоящее из элементов, принадлежащих множеству E и не принадлежащих множеству А.

Записью считается выражение, содержащее буквы и знаки операций над множествами.

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

Метод двух включений (взаимного включения) доказательства равенства множеств основан на свойстве включения множеств

 

E = F ® E Í F & F Í E

            ­    ­

(необходимость) (достаточность)

Причем доказательство включения EÍF называется необходимостью, а доказательство включения F Í E - достаточностью.

 

Глава 3.

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

Степенью S множества M называется декартово произведение S - одинаковых множеств, равных М.

Проекцией кортежа a на i-тую ось называется i-тая компонента кортежа a.

Проекция множества М — это множество проекций кортежей из М.

График — это множество пар, т.е. множество, каждый элемент которого является парой или кортежем длины 2.

Инверсией кортежа a = <c, d> называется кортежb = <d, c>.

Композицией двух кортежей b = <x, z> и g = <z, y> называется кортеж a = <x, y>.

Инверсией графика называют множество инверсий его пар (элементов).

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

Диагональю множества X (|X| = n) называется график, содержащий пары вида <x₁, x₁>, <x₂, x₂>, …, <x_n, x_n>.

Композицией двух графиков P и Q называется график R тогда и только тогда, когда $z такое, что <x, z>ÎP & <z, y>ÎQ.

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

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

 

 

Глава 4.

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

Запись j = <Ф, М> называется отношением,, т.е. Ф Í М ´ М, где j — отношение; Ф — график отношения; М — область задания отношения, представляющая из себя неупорядоченное множество.

Отношение называется бинарным,если Ф Í М².

Отношение называется k -арным, если Ф Í М^k.

Отношение j = <Ф, М> называется полным отношением, если для любых элементов x, y, принадлежащих множеству М, истинно высказывание, что элементы x, y находятся в отношении j.

Отношение j = <Ф, М> называется пустым, если график Ф является пустым множеством.

Отношение j = <Ф, М> называется отношением равенства, если Ф = DМ.

Отношение j = <Ф, М> называется отношением неравенства, если Ф = М² \ DМ.

Инверсия отношения определяется через инверсию элементов его графика на заданном множестве.

Отношение j называется отношением рефлексивности, если для любого элемента х Î М истинно высказывание х j х.

Отношение j = <Ф, М> называется отношением антирефлексивности, если ("хÎМ)Ø(х j х), т.е. D М Ç Ф = Æ.

Отношение j = <Ф, М> называют отношением симметричности, если ("х,уÎМ)(х j у ® у j х).

Отношение j = <Ф, М> называется транзитивным, если ("х,у,zÎM)(х j у & у j z ® x j z).

Отношение j называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно.

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

Отношение j на множестве М и разбиение этого множества сопряжены, если "х,уÎМ х j у истина, тогда, когда х и у принадлежат одному и тому же блоку разбиения.

Отношение j = <Ф, М> называется связным, если выполняется условие М² \ DМ Í Ф È Ф^-1.

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

Отношение j называется отношением совершенно нестрогого порядка, если оно связно и является отношением нестрогого порядка.

Отношение j называется отношением совершенно строгого порядка, если оно связно и является отношением строгого порядка.

Отношение j называется отношением доминирования (х доминирует у) если х >> у, т.е. х в чем-то превосходит у.

Отношение j называется отношением квазипорядка, если оно транзитивно и рефлексивно.

Отношение j называется отношением толерантности, если оно рефлексивно и симметрично.

 

Глава 5.

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

Композиция соответствий определяется через композицию их графиков.

Образом множества А при соответствии Г называется подмножество тех элементов области прибытия, которые соответствуют элементам множества А.

Прообразом множества В при соответствии Г называется множество тех элементов области отправления, каждому из которых соответствует какой-нибудь элемент множества В.

Соответствие называется функциональным, если его график функционален.

Соответствие называется инъективным, если его график инъективен.

Соответствие называется всюду определенным, если его область определения совпадает с его областью отправления.

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

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

Отображением множества X в множество Y называется всюду определенное соответствие.

Функцией из множества X в множество Y называется соответствие, при котором каждый элемент множества Х связан с единственным элементом множества Y.

Функция F: X ® X называется тождественной, когда множество Х отображается само в себя.

Функция всюду определена, когда для любого элемента множества Х всегда существует как минимум одно отображение.

Функция тогда и только тогда биективна, когда она всюду определена, сюрьективна и инъективна.

Функция F называется константной, если существует такой элемент bÎY, что график Ф = X ´ {b}.

Принцип Дирихле. Пусть f: X ® Y – функция, причем X и Y – конечные множества. Если |X| > |Y|, то по крайней мере одно значение f встретится более одного раза.

 

Глава 6.

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

Интервалом (a, b) упорядоченного бесконечного множества Х называется множество всех элементов, лежащих между a и b.

C егментом [a, b] упорядоченного бесконечного множества называется интервал, включающий два его конца, т.е. элементы a и b.

Два элемента a и b множества Х называется соседними, если интервал (a, b) — пустой.

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

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

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

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

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

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

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

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

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

Антиномия - противоречия (парадоксы), возникающие в теории множеств.

 

Глава 7.

Мультимножество - это множество с повторяющимися элементами, где один и тот же элемент может присутствовать многократно.

Компонента мультимножества – это группа одинаковых элементов.

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

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

Принадлежность элемента мультимножеству определяется значением функции кратности.

Порождающим множеством или доменом называется мультимножество из элементов которого образуются все мультимножества некоторого семейства.

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

Размерность мультимножества - это общее число его различных элементов.

Высота (пиковое значение) мультимножества - максимальное значение его функции кратности.

Мультимножества А_М и В_М называются равными (А_М = В_М), если k_i (x_i) = k_j (x_j) для всех элементов x_i, x_j Î G, k_i (x_i) Î А_М, k_j (x_j) Î B _М.

Мультимножества А и В называют равномощными, если | А | = | В |.

Мультимножества А и В называют равноразмерными, если / A / = / B /.

Мультимножество В _M включено (содержится) в мультимножество А _M (В _M Í А _M), если k_jx_j £ k_ix_i, для каждого элемента x_i, x_j Î G, k_ix_i Î А_М, k_jx_j Î B _М.

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

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

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

Арифметической разностью мультимножеств А_М и В_М называется мультимножество, состоящее из тех элементов мультимножества А_М, кратность которых превышает кратность соответствующих элементов в мультимножестве В_М.

Симметрической разностью мультимножеств А_М и В_М называется мультимножество, состоящее из тех элементов мультимножеств А_М и В_М, кратности которых различны.

Универсум - некоторое мультимножество, такое, что все остальные мультимножества являются подмультимножествами данного множества.

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

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

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

 

Глава 8.

Множество   называется нечетким или расплывчатым множеством в непустом множестве Х = {x₁, x₂,..., x_n} и обозначается  = {<m_~А(x), x>}, xÎX.

Функция принадлежности - есть кортеж длины два, первая компонента которого обозначается m_~А(х) и задается на сегменте [0, 1]. Вторая компонента кортежа — элемент множества Х.

Нечеткое высказывание - предложение, относительно которого можно судить о степени его истинности или ложности.

Индифферентное нечеткое высказывание равно 0.5, оно истинно в той же степени, что и ложно.

Отрицанием нечеткого высказывания  называется высказывание не , степень истинности которого определяется по формуле ù  = 1 —  .

Конъюнкцией нечетких высказываний ,  называется высказывание, степень истинности которого определяется по формуле: Ù  = min ( Ù ).

Дизъюнкцией нечетких высказываний называется нечеткое высказывание, степень истинности которого определяется по формуле: Ú  = max ( Ú ).

Импликацией нечетких высказываний называется высказывание степень истинности не меньше, чем степень неистинности ее посылки или степень истинности ее следствия: ®  = max (1 — , ).

Эквивалентностью нечетких высказываний называется новое составное нечеткое высказывание обозначаемое: «  = min (max (1 - , ), max (1 - , )).

Степень включения нечеткого множества  в нечеткое множество  обозначается n(, ) и определяется по формуле n(, ) = Ù (m_~А(х) ® m_~В(х)).

Объединением нечетких множеств называется выражение  È  = { < m_~АÈ~B(х), x >, xÎX }, m_~АÈ~B = m_~А Ú m_~B.

Пересечение нечетких множеств называется выражение  Ç  = { < m_~АÇ~B(х), x >, xÎX }, m_~АÇ~B = m_~А Ù m_~B.

Разностью нечетких множеств называется выражение  \  = { < m_~А\~B(х), x >, xÎX }, m_~А\~B = m_~А Ù ùm_~B.

Симметрической разностью нечетких множеств  и  называется выражение  Q  = { < m_~АQ~B(х), x >, xÎX }, m_~АQ~B = m_~А\~В Ú ùm_~B\~А.

Нечетким графиком называется множество, состоящее из нечетких упорядоченных пар (кортежей).

Нечетким соответствием называют тройку множеств ~Г = < X, Y, ~F >, причем X и Y — это конечные четкие множества, а ~F — нечеткий график соответствия.

Инверсией нечеткого соответствия ~Г = < X, Y, ~F­ > называется соответствие ~Г^-1 = < Y, X, ~F­^-1 >, но Х в инвертируемом соответствии будет областью прибытия, а Y — областью отправления.

Композицией двух нечетких соответствий ~Г₁ = < X, Y, ~F₁ ­> и ~Г₂ = < Y, Z, ~F₂ ­> называется выражение ~Г₁•~Г₂ = < Х, Z, ~F₃ ­>.

Нечетким отношением на произвольном множестве Х называется выражение ~j = < X, ~Ф >, причем ~ФÍХхХ, ~ФÍХ², где Х — область задания отношения, а ~Ф — нечеткий график отношения.

Приближенным множеством называется множество пар { Q ₁, Q ₂,…, Q_l }.Упорядоченную пару Q = <j, X > называют пространством приближений. При этом на обучающем множестве X введено отношение эквивалентности j = < Ф, X >, Ф Í X ´ X. Здесь Ф – график отношения, X – область задания отношения.

 

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

Галилей

Модуль 2. ОСНОВЫ ТЕОРИИ АЛГОРИТМОВ         (1,5 кредита)

 

Комплексная цель и задачи изучения модуля

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

В результате освоения Модуля 2 студент должен быть готов продемонстрировать следующие компетенции и уровень подготовки:

1) знание основных понятий теории алгоритмов;

2) умение оценивать и определять временную сложность алгоритмов;

3) знание основных алгоритмических моделей и умение их самостоятельно строить;

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

Самостоятельная работа предусматривает проработку лекций (1,2 часа в неделю), тестирование, а также изучение литературы, формулировку цели работы, объекта и задач исследования, методов, источников и средств библиографического поиска, использованных для достижения поставленной цели.

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

Глава 9. Введение в теорию алгоритмов

Алгоритмы, определение и основные понятия алгоритмов, свойства алгоритмов, классификация алгоритмов

ЦЕЛИ

Освоив эту главу, учащиеся должны уметь и знать:

· определение и основные понятия алгоритмов;

· основные свойства алгоритмов;

· основные виды алгоритмов;

· строить схемы алгоритмов.

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

Понятие «алгоритм» давно стало привычным для специалистов различных отраслей науки и техники. Оно является концептуальной основой разнообразных процессов обработки информации. Наличие соответствующих алгоритмов обеспечивает возможность автоматизации любой деятельности человека. Термин «алгоритм» обязан своим происхождением ученому средневекового Востока, который жил приблизительно с 783 по 850 гг., чье имя – Мухаммад ибн Мусса аль-Хорезми, причем «аль-Хорезми», означает «происхождением из Хорезма». В латинских названиях, составленных в XVII веке, при изложении трудов аль-Хорезми его имя переводилось как алхоритм или алгоритм. Отсюда и пошло понятие «алгоритм», которое сначала использовалось для обозначения десятичной позиционной арифметики и алгоритмов цифровых вычислений (т.е. первых алгоритмических процедур, имеющих дело с символами), а затем для обозначения произвольных алгоритмов.

Дональд Эрвин Кнут в первой главе своей многотомной монографии «Искусство программирования» писал: «Понятие алгоритма является основным при составлении любого вида программ для ЭВМ… Современное значение слова «алгоритм» во многом аналогично таким понятиям, как рецепт, процесс, метод, способ, процедура, программа, но все-таки слово алгоритм имеет дополнительный смысловой оттенок. Алгоритм - это не просто набор конечного числа правил, задающих последовательность выполнения операций для решения задачи определенного типа. Помимо этого он имеет пять важных особенностей:

1) Конечность. Алгоритм всегда должен заканчиваться после выполнения конечного числа шагов.

2) Определенность. Каждый шаг алгоритма должен быть точно определен.

3) Ввод. Алгоритм имеет некоторое число входных данных, т.е. величин, которые задаются до начала его работы.

4) Вывод. У алгоритма есть одно или несколько выходных данных, т.е. величин, имеющих вполне определенную связь с входными данными.

5) Эффективность. Алгоритм считается эффективным, если все его операции можно точно выполнить в течение конечного промежутка времени».

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

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

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

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

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

Интуиция — это знание, полученное на основе опыта, но не подвергнутое научному анализу.

К алгоритмам не относятся запрещающие и разрешающие правила. Например: “Не курить! Не сорить!”

Особенность алгоритмов — это дискретный характер процесса, определяемого самим алгоритмом.

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

· входные (исходные) данные;

· промежуточные данные;

· выходные данные.

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

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

Рис. 9.1. Представление алгоритма

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

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

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

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

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

9.2. Основные свойства алгоритмов

Основными свойствами алгоритмов являются массовость и результативность.

Массовость — это свойство алгоритма быть применимым для множества исходных данных. Термин “массовость” является расплывчатым, т.к. существуют алгоритмы, имеющие единственный вариант исходных данных.

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

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

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

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

Часто используют рекурсивные определения. Они состоят из двух частей: 1-я — циклическая, 2-я — прямая часть определения. Она является входом в циклическую.

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

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

Для установления корректности алгоритмов используют три приема:

· конструирование новых алгоритмов путем комбинирования корректных алгоритмов;

· эквивалентные преобразования корректных алгоритмов;

· сужающие преобразования корректных алгоритмов.

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

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

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

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

Операнды — это объекты, над которыми выполняются операции, предписываемые алгоритмами.

9.3. Классификация алгоритмов

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

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

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

Выделяют также случайные и самоизменяющиеся алгоритмы.

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

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

Эвристические алгоритмы (или эвристики) - это алгоритмы теоретически не обоснованные, но позволяющие сократить количество переборов в пространстве поиска. Они характеризуются как алгоритмы:

· находящие обычно «хорошие», но не обязательно наилучшие (оптимальные) решения;

· имеющие более простую реализацию, чем любой известный алгоритм, гарантирующий оптимальное решение.

Понятие «хороший» меняется от задачи к задаче. Универсальной структуры описания эвристических алгоритмов не существует.

Например, во многих задачах информатики требуется выборка А предметов из множества В предметов. Один эвристический подход состоит в том, чтобы выбирать предметы с вероятностью А/В. Здесь каждый предмет принимается или отвергается в момент его просмотра и можно делать только один просмотр вдоль всего набора предметов. В общем виде эта процедура не гарантирует, что будет выбрано в точности А предметов. Другой эвристический подход при выборе А чисел из В состоит в том, чтобы многократно генерировать случайные целые числа до тех пор, пока не окажется А различных чисел.

Приведем другую классификацию. Согласно ей все алгоритмы можно разделить на три группы:

· линейные;

· разветвляющиеся;

· циклические.

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

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

Наиболее сложным является циклический алгоритм (по структуре), который выполняется путем многократного повторения некоторой последовательности действий. Циклические алгоритмы делятся:

· на последовательные, с явно заданным числом повторений цикла;

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

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

На рис. 9.2 а – в приведена условная структура последовательных, итерационных и поисковых алгоритмов.

а)                    б)

в)

Рис. 9.2. Условная структура алгоритмов а) последовательная; б) итерационная; в) иерархическая (поисковая)

Во многих случаях эффективное решение задачи получают при использовании иерархического алгоритма. При этом исходная задача Z₀ разбивается на некоторое число подзадач Z₁, Z₂,..., Z_k и делаются попытки решить каждую из них. Такое разбиение обычно описывается деревом поиска решения. Смысл разбиения на подзадачи состоит в том, что после разбиенияза счет снижения объема конкретной подзадачи и возможного изменения ее структуры затраты на решение отдельной подзадачи значительно меньше, нежели на решение исходной задачи в целом. Важной проблемой при использовании иерархических алгоритмов является поиск оптимального решения, реализуемогонаоснове перебора путей на дереве решений. Выделяют следующие базовые виды поиска:

· в глубину;

· в ширину.

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

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

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

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

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

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

Алгоритмы регулирования связаны с управлением технологическими процессами и применяются в задачах автоматического управления и регулирования технических систем.

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

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

Алгоритмы решения задач вычислительной математики представляют собой комплексные алгоритмы решения конечных уравнений вида F (x) = 0, однородных дифференциальных уравнений ∂ x / ∂ t = f (x (t), t), линейных уравнений вида А х = В, и т.д. Обычно эти алгоритмы оформляются в виде стандартных программ.

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

Предметно-ориентированные алгоритмы направлены на решение задач, относящихся к определенному виду предметной области (например, расчет математических моделей объектов проектирования).

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

ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ

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

Вход: последовательность чисел (а_1, а_2, а_3,…,а _n).

Выход: перестановка (а^’_1, а^’_2, а^’_3,…,а^’ _n) исходной последовательности, для которой а^’_{1 ≤} а^’₂ ≤ … _≤ а^’ _n. Например, для входной последовательности (31, 59, 26, 58) алгоритм сортировки должен выдать (26, 31, 58, 59).

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

Рассмотрим один из важных методов сортировки вставками, описанный Корменом Т., Лейзерсоном Ч., Ривестом Р. Он эффективен при сортировке коротких числовых последовательностей. Метод основан на выборе очередного числа и вставки его в нужное место, сравнивая с имеющимися и передвигаясь справа налево. Исходными данными алгоритма является массив А [ 0, …, n ] (последовательность элементов (чисел) длины n, подлежащая сортировке). Число элементов в массиве А обозначается через length [A]. Последовательность сортируется без дополнительной памяти. Здесь используется входной массив и фиксированное число ячеек памяти.

На рис. 9.3 показана работа алгоритма сортировки Кормена Т., Лейзерсона Ч., Ривеста Р на примере числовой последовательности А = (4, 1, 3, 5, 0, 2).

Рис. 9.3. Работа процедуры сортировки

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

 

ПСЕВДОКОД АЛГОРИТМА СОРТИРОВКИ:

1 for j ← 2 to length [ A ]

2 do key ← A [ j ]

3    “добавить A [ j ] к отсортированной части A [0, …, j - 1 ] ”

4 i ← j - 1

5 while i > 0 and A [ i ] > key

6           do A [ i + 1] ← A [ i ]

7               i ← j - 1

8    A [ i + 1] ← key

 

Индекс j указывает выбранный очередной элемент. Часть массива A [0,…, j - 1 ] составляют уже просмотренные элементы, a - A [ j + 1, …, n ] — еще не просмотренные элементы. После выполнения процедуры сортировки массив А упорядочен по возрастанию.

В цикле for индекс j проходит массив слева направо. Просматривается элемент A [ j ] (строка 2 алгоритма) и производится сдвиг стоящих перед ним больших по величине элементов (начиная с (j - 1)-го) вправо, освобождая место для выбранного элемента (строки 4-7). В строке 8 элемент A [ j ] помещается на свободное место.

Комментарий:

1. Отступ от левого поля указывает на уровень вложения. Например, тело цикла for (строка 1) состоит из строк 2-8, а тело цикла while (строка 5) содержит строки 6-7.

2. Циклы while, for, repeat и условные конструкции if – then - else имеют тот же смысл, что и в языке программирования «Паскаль».

3. Кавычки начинают и заканчивают комментарий (идущий до конца строки).

4. Одновременное присваивание i ← j ←е (переменные i и j получают значение е) заменяет два присваивания j ← е и i ←j (в этом порядке).

5. Переменные (в данном случае i, j, key) локализуются внутри описанной процедуры (если не оговорено иное).

6. Индекс массива пишется в квадратных скобках, то есть запись A [ v ] соответствует v -му элементу в массиве А.

КОНТРОЛЬНЫЕ ВОПРОСЫ

1. Откуда произошло понятие алгоритма?

2. Приведите пять основных особенностей алгоритма, данные Д. Кнутом.

3. Приведите основные определения алгоритма.

4. Что такое алгоритмический процесс, шаг алгоритма, интуиция?

5. Что является основной особенностью алгоритма?

6. Какие типы данных используются в алгоритме?

7. Приведите пример виртуального представления алгоритма в виде «черного ящика».

8. Что такое правильный и неправильный алгоритмы?

9. Перечислите способы записей алгоритмов.

10. Что такое массовость и результативность алгоритма?

11. Что такое определенность алгоритма?

12. Поясните понятие «порочный круг».

13. Что такое детерминированность и корректность алгоритма?

14. Что такое алгоритмический язык и язык операндов?

15. Что такое имитирующие и эмпирические алгоритмы? Приведите примеры.

16. Что такое случайные и самоизменяющиеся алгоритмы?

17. Дайте определение эвристических алгоритмов и приведите примеры.

18. Что такое линейные, разветвляющиеся и циклические алгоритмы?

19. Что такое поисковые алгоритмы. Приведите примеры алгоритмов поиска в глубину и в ширину.

20. Приведите примеры следующих видов алгоритмов: логических; обработки данных; регулирования; эволюционных; оптимизации; решения задач вычислительнойматематики; проблемно-ориентированных; предметно-ориентированных; решения системных задач ЭВМ.

21. В чем заключаются алгоритмы сортировки?

22. Приведите пример представления псевдокода алгоритма.

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ

1. Следуя образцу (рис. 1.3), покажите, как работает алгоритм сортировки вставками для входной числовой последовательности А = (101, 71, 49, 66, 81, 38).

2. Предложите другой алгоритм сортировки по убыванию (возрастанию).

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

4. Запишите псевдокод алгоритма поиска в ширину нахождения минимального числа в массиве A = (2, 17, 33, 10, 22).

5. Приведите итерационный алгоритм нахождения максимального числа в массиве B = (20, 10, 40, 60, 30).

6. Постройте псевдокод последовательного алгоритма сортировки одномерного массива C = (55, 32, 20, 13, 48) по возрастанию.

7. Пусть задана матрица размера 3 ´ 4. Запишите псевдокод для нахождения суммы элементов главной диагонали.

8. Пусть задана матрица размера 3 ´ 4. Запишите псевдокод для нахождения суммы элементов первой строки и четвертого столбца.