Избранные главы дискретной математики

--PAGE_BREAK--




§4 Теория нечетких множеств

Нечёткое(или размытое, расплывчатое, туманное, пушистое)множество — понятие, введённое Лотфи Заде в 1965 г. в статье «FuzzySets» (нечёткие множества) в журнале «InformationandControl». Л. Заде расширил классическое канторовское понятие множества, допустив, что характеристическая функция (функция принадлежности элемента множеству) может принимать любые значения в интервале [0,1], а не только значения 0 или 1.

Определение

Под нечётким множеством Aпонимается совокупность

где X— универсальное множество, а  — функция принадлежности (характеристическая функция), характеризующая степень принадлежности элемента xнечёткому множеству A.

Функция  принимает значения в некотором вполне упорядоченном множестве M. Множество Mназывают множеством принадлежностей, часто в качестве Mвыбирается отрезок [0,1]. Если M
={0,1}, то нечёткое множество может рассматриваться как обычное, чёткое множество.

Для пространства рассуждения Xи данной функции принадлежности  нечёткое множество определяется как


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



Основные определения

Пусть Aнечёткое множество с элементами из универсального множества Xи множеством принадлежностей M
=[0,1]. Тогда

·          Носителем (суппортом) нечёткого множества supp

Aназывается множество

.

·          Величина


называется высотой нечёткого множества A. Нечёткое множество  нормально, если его высота равна 1. Если высота строго меньше 1, нечёткое множество называется субнормальным.

·          Нечёткое множество пусто, если . Непустое субнормальное нечёткое множество можно нормализовать по формуле:



.

·          Нечёткое множество унимодально, если  только на одном xиз X.

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

Операции над нечёткими множествами

При M
=[0,1]

·          Пересечениемнечётких множеств A и B называется наибольшее нечёткое подмножество, содержащееся одновременно в A и B:



·          Произведениемнечётких множеств A и B называется нечёткое подмножество с функцией принадлежности:

.

·          Объединениемнечётких множеств A и B называется наименьшее нечёткое подмножество, содержащее одновременно A и B:



·          Суммойнечётких множеств A и B называется нечёткое подмножество с функцией принадлежности:



·          Отрицаниеммножества Aпри M
=[0,1] называется множество  с функцией принадлежности:



для каждого.




§5 Алгоритмы сортировки и поиска

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

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

Сортировка включением

Одним из наиболее простых и естественных методов сортировки является сортировка с простыми включениями. Пусть имеется массив ключей  a
1, a
2, ..., an. Для каждого элемента массива, начиная со второго, производится сравнение с элементами с меньшим индексом (элемент ai
последовательно сравнивается с элементами ai
-1, ai
-2...) и до тех пор, пока для очередного элемента ajвыполняется соотношение aj> ai, aiи ajменяются местами. Если удается встретить такой элемент aj, что ajai, или если достигнута нижняя граница массива, производится переход к обработке элемента a[i+1] (пока не будет достигнута верхняя граница массива).

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

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

Сортировка «методом пузырька»

Простая обменная сортировка (в просторечии называемая «методом пузырька») для массива a
1, a
2, ..., an
 работает следующим образом. Начиная с конца массива сравниваются два соседних элемента (an и an
-1). Если выполняется условие an
-1> an, то значения элементов меняются местами. Процесс продолжается для an
-1  и an
-2  и т.д., пока не будет произведено сравнение a
2 и a
1. Понятно, что после этого на месте a
1 окажется элемент массива с наименьшим значением.

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

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

Сортировка выбором

При сортировке массива a
1, a
2, ..., anметодом простого выбора среди всех элементов находится элемент с наименьшим значением ai, и a
1  и aiобмениваются значениями. Затем этот процесс повторяется для получаемых подмассивов a
2, a
3, ..., an,… aj, aj
+1, ..., an
до тех пор, пока мы не дойдем до подмассива
an, содержащего к этому моменту наибольшее значение.

Сортировка разделением (Quicksort)

Метод сортировки разделением был предложен Чарльзом Хоаром  в 1962 г. Этот метод является развитием метода простого обмена и настолько эффективен, что его стали называть «методом быстрой сортировки — Quicksort».

Основная идея алгоритма состоит в том, что случайным образом выбирается некоторый элемент массива x, после чего массив просматривается слева, пока не встретится элемент aiтакой, что ai> x, а затем массив просматривается справа, пока не встретится элемент ajтакой, что aj

Алгоритм поиска по бинарному дереву

Суть этого алгоритма достаточно проста. Представим себе, что у нас есть набор карточек с телефонными номерами и адресами людей. Карточки отсортированы в порядке возрастания телефонных номеров. Необходимо найти адрес человека, если мы знаем, что его номер телефона 222-22-22. Берем карточку из середины пачки, номер карточки 444-44-44. Сравнивая его с искомым номером, мы видим, что наш меньше и, значит, находится точно в первой половине пачки. Откладываем вторую часть пачки в сторону, она нам не нужна, массив поиска мы сузили ровно в два раза. Теперь берем карточку из середины оставшейся пачки, на ней номер 123-45-67. Из чего следует, что нужная нам карточка лежит во второй половине оставшейся пачки. Таким образом, при каждом сравнении, мы уменьшаем зону поиска в два раза. Отсюда и название метода — половинного деления или дихотомии.

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




§6 Теория графов

Теория графов — раздел дискретной математики, изучающий свойства графов. Первая работа по теории графов принадлежит Леонарду Эйлеру. В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов. Но термин «граф» впервые ввел в 1936 году венгерский математик Денеш Кениг.

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



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

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

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

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

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

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

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

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




                                                                                 Последовательности вершин (рис. 1): 1–2–3–4–2–5 не простой путь, а маршрут; последовательности 1–2–3–4–7–5 и 1–2–5 – простые пути; 1–2–3–4–2–5–6–1 –это цикл (но не контур); 1–2–5–6–1 – это контур.


Рис.2

Граф называется связным, если любые две его вершины можно соединить маршрутом (или путем). На рис.2 изображен связный граф.

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

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

Степень вершины– это число ребер, входящих в эту вершину. Вершина называется висячей, если ее степень равна единице.

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

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

Применение теории графов

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

·        В химии (для описания структур, путей сложных реакций[1], правило фаз также может быть интерпретировано как задача теории графов); компьютерная химия — сравнительно молодая область химии, основанная на применении теории графов. Теория графов представляет собой математическую основу хемоинформатики. Теория графов позволяет точно определить число теоретически возможных изомеров у углеводородов и других органических соединений.

·        В информатике и программировании

·        В коммуникационных и транспортных системах. В частности, для маршрутизации данных в Интернете.

·        В экономике

·        В логистике


§7 Комбинаторика

Термин «комбинаторика» был введён в математический обиход Лейбницем.

В 1666 году Лейбниц опубликовал «Рассуждения о комбинаторном искусстве». В своём сочинении Лейбниц, вводя специальные символы, термины для подмножеств и операций над ними находит все k -сочетания из n элементов выводит свойства сочетаний.

Элиаким Гастингс Мур (1862-1932) ввёл термин тактическая конфигурация в статье «Tactical memoranda», понимая под этим термином систему n множеств, содержащих, соответственно, a1, a2, …, anэлементов.

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

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

Условно в комбинаторной теории можно выделить следующие три большие части (см. схему):

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

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

·        Теорию порядка, включающую конечные упорядоченные множества и решётки, матрицы и теоремы существования, подобные теоремам Холла и Рамсея.


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

В комбинаторике производящая функция последовательности {an} — это формальный степенной ряд

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

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

 Примерами комбинаторных конфигураций являются:

·        Размещениемиз n элементов по k называется упорядоченный набор из k различных элементов некоторого n-элементного множества.

·        Перестановкойиз n элементов (обычно чисел 1,2,…,n) называется всякий упорядоченный набор из этих элементов. Перестановка также является размещением из n элементов по n.

·        Сочетаниемиз n по k называется набор k элементов, выбранных из данных n элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений.

Основные свойства сочетаний:

1.Условились, что 

2.

3.

4.







·        Композициейчисла n называется всякое представление n в виде упорядоченной суммы целых положительных чисел.

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

Правило суммы:

Если элемент Aможно выбрать mспособами, а элемент Bможно выбрать kспособами, то выбор элемента Aили Bможно осуществить m
+
kспособами.

Правило суммы можно перефразировать на теоретико-множественном языке. Обозначим через | A| число элементов множества A, через A B— объединение множеств Aи B, через AB— декартово произведение множеств Aи B. Тогда для непересекающихся множеств Aи Bвыполняется равенство:

| AB| = | A| + | B|.

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

Правило произведения:

Если элемент Aможно выбрать mспособами, а после каждого выбора элемента Aэлемент Bможно выбрать kспособами, тогда, упорядоченную пару элементов (A, B) можно выбрать m
*
kспособами.

Правило произведения можно распространить на выбор последовательности

 (x1, x2, …, xn) произвольной конечной длины n.

На теоретико-множественном языке правило произведения формулируется так:

| A B| = | A|  | B|.

Теория Рамсея

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

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

В терминах структурной комбинаторики это же утверждение формулируется так:

в любом графе с 6 вершинами найдётся либо клика, либо независимое множество размера 3.

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

Теорема Холла о свадьбах

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

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




§8 Дискретизация

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

·        собственно дискретизации,

·        квантования.

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

Перевод аналогового сигнала в дискретную форму для анализа на компьютере производится, как правило, через равные промежутки времени T. Важно правильно выбрать величину интервала дискретизации, т.е. правильно провести операцию собственно дискретизации. Согласно теореме Котельникова, этот интервал определяется частотой Найквиста Fn: чтобы представление сигнала x
(
t
)в дискретной форме было однозначным, максимальный интервал дискретизации не должен превышать T
= 1 / (2
Fn
). Если осуществлять выборки через интервалы времени, большие T, то можно столкнуться с эффектом маскировки (подмены) частот, т.е. возможно перепутывание низко- и высокочастотных составляющих исходного процесса. Явление подмены является источником ошибок, которые могут возникнуть лишь при работе с выборочными данными. Если обрабатываются аналоговые сигналы, то операция дискретизации не производится и ошибки подмены не возникают.

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

Рассмотрим теперь операцию квантования, которая состоит в переводе значений сигнала из аналогового непрерывного представления в цифровую форму. Как известно, цифровое представление чисел в ЭВМ заключается в их двоичном кодировании посредством целого числа бит. Точность цифрового (машинного) представления числа в виде непрерывного множества значений определяется количеством используемых бит. В типичных преобразователях аналогового сигнала в цифровой формат для кодирования применяется от 6 до 16 бит, что соответствует диапазону от 64 до 65536 уровней квантования. Так, если для представления чисел xиз интервала (0,5) используется 8 бит, то это означает, что весь непрерывный интервал разбит на 28 = 256 уровней c, 0 ≤ c
≤ 255, с шагом квантования  и только 256 целых чисел в цифровой форме можно использовать для записи любого числа из этого интервала (рис. 25). Математически операцию квантования можно записать в виде:



здесь INTозначает округление до целой части числа. Ошибка квантования  равна



и ограничена интервалом (-0.5,0.5). Если преобразователь работает правильно, то ошибка квантования имеет нулевое среднее, распределена   равномерно   с  плотностью   вероятности,   равной  единице (p(c)=1), а дисперсия ошибки равна:


Частота дискретизации

Частота дискретизации(или частота сэмплирования) — частота взятия отсчетов непрерывного во времени сигнала при его дискретизации (в частности, аналого-цифровым преобразователем). Измеряется в герцах.

Термин применяется и при обратном, цифро-аналоговом преобразовании, особенно если частота дискретизации прямого и обратного преобразования выбрана разной (Данный приём, называемый также «Масштабированием времени», встречается, например, при анализе сверхнизкочастотных звуков, издаваемых морскими животными).

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

Используемые частоты дискретизации звука:

·        8 000 Гц — телефон, достаточно для речи, кодек Nellymoser;

·        11 025 Гц;

·        22 050 Гц — радио;

·        44 100 Гц — используется в Audio CD;

·        48 000 Гц— DVD, DAT.

·        96 000 Гц— DVD-Audio (MLP 5.1)

·        192 000 Гц — DVD-Audio (MLP 2.0)

·        2 822 400 Гц — SACD Super audio CD 5.1 — максимальная на данный момент (2008)

Сигналы

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

Классификация сигналов

·        По физической природе носителя информации:

o       электрические,

o       электромагнитные,

o       оптические,

o       акустические

o       и др.;

·        По способу задания сигнала:

o       регулярные (детерминированные), заданные аналитической функцией;

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

·        В зависимости от функции, описывающей параметры сигнала, выделяют:

o       непрерывные (аналоговые), описываемые непрерывной функцией;

o       дискретные, описываемые функцией отсчетов, взятых в определенные моменты времени;

o       квантованные по уровню;

o       дискретные сигналы, квантованные по уровню (цифровые).

Детерминированность

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

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

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

Интерполяция

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

Определение интерполяции

Рассмотрим систему несовпадающих точек xi() из некоторой области D. Пусть значения функции fизвестны только в этих точках:



Задача интерполяции состоит в поиске такой функции Fиз заданного класса функций, что



·        Точки xiназывают узлами интерполяции, а их совокупность — интерполяционной сеткой.

·        Пары (xi
,

yi
)называют точками данных или базовыми точками.

·        Разность между «соседними» значениями  — шагом интерполяционной сетки. Он может быть как переменным так и постоянным.

·        Функцию F
(
x
)— интерполирующей функцией или интерполянтом.

Экстраполяция

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

Экстраполяция — приближённое определение значений функции f(x) в точках x, лежащих вне отрезка [x0,xn], по её значениям в точках x01 n



Сплайны

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


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

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

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




§9 Теория сложности алгоритмов

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

Для каждой задачи может существовать множество алгоритмов, приводящих к цели. Увеличение эффективности алгоритмов составляет одну из задач современной информатики. В 50-х гг. XXвека появилась даже отдельная её область — быстрые алгоритмы. В частности, в известной всем с детства задаче об умножении десятичных чисел обнаружился ряд алгоритмов, позволяющих существенно (в асимптотическом смысле) ускорить нахождение произведения.

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

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

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

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

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

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

§10 Теория конечных автоматов

    продолжение
--PAGE_BREAK--