Классы
Предметы

Часть 1. Сложность и порядок

Введение

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

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

Рис. 1. Мауриц Корнелис Эшер «Порядок и хаос»

Упрощение в математике

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

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

Рассмотрим пример:

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

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

Например, для формулы квадрата суммы: .

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

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

Алгоритмическая и математическая сложность

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

Рассмотрим следующее уравнение: .

Корни уравнения легко подобрать, используя теорему Виета:

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

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

Рис. 2. Способы подъема в гору

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

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

Примеры из жизни

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

Приведем пример некой последовательности.  Если не знать, что данные числа составляют последовательность Фибоначчи, определить следующий элемент достаточно сложно. Если же знать закон (), определить следующие элементы не составит труда (Рис. 3).

Рис. 3. Элементы последовательности Фибоначчи

Таким образом, понятия «порядок», «сложность» и «алгоритм» взаимосвязаны.

Что такое порядок и беспорядок? Рассмотрим краски, находящиеся в тюбиках, и смешанные на картине. Что является более упорядоченным, сложным? (Рис. 4, 5)

Рис. 4. Краски в тюбиках

Рис. 5. Картина В.В. Кандинского «Желтое-красное-синее»

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

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

Пример из детства. Все мы складывали в детстве мозаику. Её элементы представляют собой хаос в разобранном состоянии и образуют порядок в собранном виде (Рис. 6).

Рис. 6. Мозаика

Шифрование и дешифровка служат еще одним примером порядка и хаоса. Не зная алгоритма дешифровки, запись «Диналтанолйе» кажется бессмысленным набором букв. Однако знание ключа придает записи смысл и позволяет расшифровать слово (Рис. 7).

Рис. 7. Расшифровка «Диналтанолйе»

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

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

Рис. 8. Книги на полке

Существуют ситуации, в которых мы сами вводим понятие порядка для классификации чего-либо. Порядок – это инструмент, который позволяет ориентироваться и действовать в мире. Например, адреса для улиц, ИНН для людей, штрихкод, QR-код для товаров и т.д. Любой закон – это упорядочивание. Следование правилам упорядочивает нашу жизнь. Мы знаем, как действовать в той или иной ситуации благодаря тому, что сами все упорядочили. Не было бы людей – не было бы придуманных ими законов.

Поиск

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

Актуальным вопросом в наше время является поиск в Интернете. Как же он устроен? Для каждого слова существует своя история: известно, в каких текстах это слово содержится. Когда мы запрашиваем некоторую фразу, каждое из слов встречается в большом количестве документов. То есть нужно найти документы, где встречаются все слова из фразы (Рис. 9). Логично, что начинать поиск с союза «и» бесполезно, так как он встречается во всех документах. Обычно поиск начинают с самого редкого слова. Из образовавшихся документов пересечением находят остальные слова из фразы.

Рис. 9. Поиск в Интернете

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

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