для чего нужна алгоритм
Зачем программисту изучать алгоритмы
Авторизуйтесь
Зачем программисту изучать алгоритмы
руководитель программ «Python-разработчик» и «Алгоритмы для разработчиков» в Яндекс.Практикуме
Понятие «алгоритм» довольно расплывчато — обычно оно обозначает последовательность действий для достижения конкретной цели. Например, есть алгоритм заваривания чая или алгоритм сборки шкафа из ИКЕА. Но в контексте программирования мы имеем в виду другие алгоритмы.
За всю историю компьютерных наук сложилось понимание, какие алгоритмы и структуры данных (способы их хранения) нужны для решения практических задач — так называемый джентльменский набор, который должен знать каждый разработчик. Например, сортировка: товары в магазине сортируют по стоимости или сроку годности, а рестораны — по удалённости или рейтингу. Хэш-таблицы помогают проверить корректность пароля и не хранить его на сайте в открытом виде, графы — находить кратчайший путь и хранить связи между пользователями в соцсетях.
Все эти алгоритмы и структуры данных уже давно реализованы в библиотеках популярных языков программирования. Никто больше не пишет вручную алгоритм сортировки чисел, а чтобы пользоваться хэш-таблицами, даже не нужно знать, как они устроены. Разбираемся, зачем же нужны алгоритмы и в каких ситуациях их знание будет преимуществом.
Знание алгоритмов помогает найти эффективное решение задачи
Представьте, что вам нужно сходить в магазин за продуктами. До него есть три дороги: вдоль проезжей части по хорошо освещённому тротуару (долго, но безопасно), дворами, где ездит много машин (быстро, но небезопасно), на трамвае (быстро, безопасно, но нужно платить). У этой задачи также могут быть и другие решения: доехать на машине, заказать доставку на дом или отправить за продуктами собаку.
Аналогично и в программировании. Задача разработчика — использовать наиболее эффективное решение. Для этого нужно учитывать скорость работы программы, объём потребляемой памяти, экономическую эффективность (насколько стоимость решения оправдана конечным результатом), простоту реализации, масштабируемость.
Пример №1. Нужно отсортировать n чисел в порядке возрастания. Задача кажется невероятно простой. Проходим n раз по массиву чисел. На первом шаге выбираем наименьшее число из всех и меняем его местами с самым первым элементом. Второй шаг: выбираем самое маленькое число в массиве, начиная со второй позиции, и меняем его местами со вторым элементом. Повторяем для остальных элементов. Так работает алгоритм сортировки выбором. Но при таком подходе получится O(n 2 ) операций. Когда n станет неприлично большим, работать машина будет долго. Чтобы понимать, какой из алгоритмов будет оптимальным для ваших исходных данных, надо знать, как эти алгоритмы устроены. Скорее всего, вам примерно никогда не придётся реализовывать их вручную, но знание, как они работают, точно пригодится.
Пример №2. Вы научились писать код, но ничего не слышали об алгоритмах. Сделали на заказ видеосервис, дали на разработку год гарантии. Проект стал успешным, но уже при первых десяти тысячах пользователей всё начало ломаться: сервера быстро выходят из строя, а видео, по ощущениям пользователей, грузится миллион лет. Заказчик приходит к вам и просит решить проблему. Вы догадываетесь, что нужно использовать более эффективный алгоритм сжатия. Здесь и пригодится знание алгоритмов: понимая, как работает каждый из них, вы сможете подобрать наилучший вариант для решения задачи или даже написать собственный.
Наличие множества готовых библиотек не означает, что не нужно понимать, как они устроены. Фундаментальные знания помогают узнать, что внутри, как оно работает и почему решение А лучше Б в конкретной ситуации. Если вы разберётесь, как устроены классические алгоритмы, то сможете создавать собственные решения, комбинировать методы друг с другом, чтобы решать более сложные задачи.
Вы будете готовы к собеседованиям
В крупных ИТ-компаниях, таких как Яндекс, Google или Facebook, алгоритмическое собеседование — обязательный этап отбора разработчиков. На нём проверяют умение быстро отразить идею в коде. Но знание алгоритмов требуют не только ИТ-гиганты — для многих компаний это базовый навык хорошего инженера.
Вас могут попросить реализовать алгоритм полностью или представить часть решения. Например, найти пропущенное число или дубликаты в целочисленном массиве от 1 до 100. При этом от вас будут ждать не одно решение, а сравнение нескольких возможных вариантов, основываясь на их вычислительной сложности. То есть не просто воспользоваться сортировкой подсчётом, но и объяснить, почему этот метод лучше сортировки пузырьком или сортировки вставками.
Основная задача программиста — анализировать и решать проблемы, где код — это всего лишь инструмент достижения цели. Поиск Google или Яндекса не был бы таким умным и быстрым, если бы не алгоритмы. Они не просто ищут максимальное сходство по поисковой фразе, но пытаются вычленить контекст и подобрать самый подходящий по всем параметрам ответ.
Часто возникают проблемы, с которыми вы раньше не сталкивались. Тогда программисту следует разработать новый алгоритм или придумать, как использовать существующий. Чем больше вы будете знать о принципах работы алгоритмов, тем больше вероятность найти хорошее решение. Иногда даже новую проблему можно свести к старой, но для этого нужно обладать фундаментальными знаниями.
Это хороший способ тренировать мозг
Алгоритмы не обязательно использовать только в работе. Это один из вариантов «тренажёра для программистов». Сначала вы решаете задачи на Codeforces, а спустя некоторое время собираете команду для участия в соревнованиях по спортивному программированию.
Другой бонус: вы научитесь быстро и интуитивно решать обычные задачи. Главный инженер Apple и выпускник МТИ Али Альмоссави в своей книге «Bad Choices: How Algorithms Can Help You Think Smarter and Live Happier» рассказал, как использует знания компьютерных наук в обычной жизни.
Он сопоставляет повседневные действия с фундаментальными алгоритмами. Например, вам нужно получить больше подписчиков. Самый простой способ — найти людей, которые могут заинтересовать вас и заинтересоваться вами. Но между ними нужно найти связующее звено. Что для этого есть у соцсети? Хештеги. Значит, проще всего будет помечать свои фотографии нужными хештегами, искать по ним другие аккаунты и общаться по этой теме с людьми в комментариях.
Алгоритмы, как математика, приводят в порядок ум, учат выражать свои мысли и решать даже самые непростые задачи. Если захотите научиться решать задачи по программированию, отправляйтесь на Codeforces, TopCoder или LeetCode, где собраны упражнения для любого уровня подготовки. Попробовать решить типичные для алгоритмических собеседований задачи можно и в бесплатной части курса «Алгоритмы для разработчиков» в Яндекс.Практикуме.
Что такое алгоритмы и зачем они нужны
Содержание статьи
Конечно, собрать кубик Рубика можно и без памятки, просто перемещая грани в случайном порядке. Но перебор возможных вариантов может занять долгое время, это будет непроизводительный и неоптимальный процесс. Гораздо удобнее иметь список шагов, последовательное выполнение которых всегда будет приводить к положительному результату. Именно эти принципы легли в такое понятие как «алгоритм».
Алгоритм — совокупность инструкций (шагов), описывающих порядок операций исполнителя для достижения результата решения задачи за конечное число действий.
Что такое «исполнитель»?
Для наилучшего понимания алгоритма вообще, необходимо также рассмотреть понятие «исполнитель алгоритма». Под исполнителем в понятии алгоритма подразумевается абстрактная система, способная выполнять действия, описываемые алгоритмом, а также обладающая рядом характеристик. В качестве исполнителя чаще всего подразумевается то или иное техническое средство (3D-принтер, станок с ЧПУ, ЭВМ), однако стоит понимать, что это широкое понятие: исполнителем может являться, например, человек.
Тем не менее, исполнителем может быть названа только система, одновременно обладающая рядом параметров:
— отказами, в случае, если выполнение действий невозможно.
Свойства алгоритмов
Ограничения, накладываемые на понятие «исполнитель» приводят к тому, что само понятие «алгоритм» также обладает рядом свойств и ограничений. Алгоритмы получили широкое распространение именно благодаря этим ограничениям, которые способствуют стандартизации. Среди свойств алгоритмов можно выделить:
— массовость (способность алгоритма оставаться правильным при разных наборах входных данных);
— определенность (на любом шаге алгоритма у исполнителя должно быть достаточно данных, чтобы его выполнить);
— детерминированность (при одних и тех же наборах входных данных должен получаться один и тот же результат);
Зачем нужны алгоритмы?
Вышеприведенные свойства обеспечивают алгоритмам широкое применение. Так алгоритмы служат для стандартизации описаний любых процессов. Без алгоритмов были бы невозможны любые виды вычислений, а решение любой проблемы начиналось бы «с нуля» — даже если она была решена множество раз. Применение алгоритмов позволяет быстро решать однотипные задачи, сократить время на поиск решения, автоматизировать процесс его нахождения, а также распространять найденное решение в стандартизованной — а значит, понятной всем форме.
Зачем программисту знать алгоритмы
Если посмотреть на все эти статьи, то можно заметить, что люди, которые их пишут, фактически обижены на университеты за то, что их заставили учить много сложного материала — в виде алгоритмического анализа, сложных алгоритмов и структур данных — который им вроде бы не пригодился. По сути, авторы статей обижены на университеты из-за того, что там не смогли предсказать будущую область работы авторов и дать им только минимально нужный набор навыков. Ведь действительно, чтобы писать простенькие сайты и скрипты, не нужно особого знания алгоритмов и структур данных. Или всё-таки нужно?
Давайте подумаем, что же нужно учить программисту в университете, для того чтобы приобрести необходимые навыки для успешной карьеры. Библиотеки? Фреймворки? Они устаревают, интерфейсы к ним меняются, все они написаны чаще всего под один язык, который студенты могут и не использовать никогда в индустрии. Всех учить писать сайты? Или всех учить писать ОС? Образование должно охватывать как можно большую аудиторию и давать максимально возможный набор навыков. Программист в первую очередь должен уметь анализировать и решать проблемы – это основной навык, которым должны обзавестись выпускники факультетов информатики. Написание кода – это просто необходимый инструмент, который используется для решения задач. Кто может знать какие навыки вам понадобятся в будущем? Таким образом учить теорию – это наиболее оптимально с точки зрения образования. Полученные навыки можно применить в любой области, а выучить библиотеку или фреймворк имея хорошую базу знаний не составит большого труда. Парадоксально то, что люди задающие вопросы про нужность алгоритмов, как правило имеют какие-то знания в этой области. Я не помню ни одного человека, который не имел знаний в области теории вычислений, и с гордостью кричал об этом, утверждая, что ему они не нужны.
Итак, вы абстрактный программист в вакууме, работаете десять с лишним лет клепая сайты и решая простые однотипные задачи клиентов/компании. Вам хорошо и уютно в вашей нише, и только мучительно больно за бесцельно потраченное время в классе по теории вычислений и алгоритмическому анализу, который вам ничего не дал. По утрам закуривая сигарету за чашкой кофе, в глубине философских размышлений о бренности бытия вы задумываетесь: зачем же программистам, не решающим сложных задач, знать алгоритмы и основы анализа. Короткий ответ: чтобы быть квалифицированным специалистом и эффективно использовать доступные инструменты, включая язык, на котором вы пишите. Теория алгоритмов и анализа учит не только экзотические алгоритмы и структуры данных в виде АВЛ и красно-чёрных деревьев. Она также даёт представления о том, как эффективно организовать данные, как писать код с максимальной производительностью, где в системе возможно бутылочное горлышко и как с ним бороться. Вас ознакамливают с готовыми решениями, чтобы вы не писали велосипедов, и не бежали в гугл каждый раз, когда нужно сделать что-то нетривиальное.
Знания теории анализа и алгоритмов применяются всеми программистами на самом деле каждый день, просто мы привыкли к этим вещам настолько, что даже не задумываемся над этим. Какую бы задачу вы не решали – будь то простой сайт с выборкой данных из БД, или баш скрипт на сервере, вы будете использовать какие-то структуры данных. Как минимум примитивный массив, а скорее всего и что-то посложнее. Языки дают нам множество различных структур, многие из которых взаимозаменяемы. Часто мы имеем несколько вариаций одного абстрактного типа с разными реализациями. Например, в С++ есть структуры данных vector и list. Чем они отличаются, и какие будут преимущества и недостатки использования одного или другого? Как в С++ реализована map, и чем она отличается от multimap? Как реализован list в Python – через массив или связным списком и как лучше всего с ним работать? Почему в C# нежелательно использовать ArrayList, а вместо него использовать List? Как реализован SortedDictionary и как он повлияет на исполнение программы если будет использован вместо Dictionary? Как работает continuation, когда её нужно использовать, и будут ли какие-то побочные эффекты при её использовании? Когда вы в последний раз использовали каррированные функции, которые есть почти в каждом языке? Если вы думаете, что map в С++ реализована как хэш-таблица, вы ошибаетесь. Она реализована на красно-чёрных деревьях, а хэш-таблицей реализована unordered_map. Отдельно стоит упомянуть динамическое программирование. Понимание что это такое, как можно оптимально переписать рекурсивные функции и что такое мемоизация, часто поможет избежать выстрела себе в ногу. Таким образом просто чтобы полноценно и эффективно использовать язык, на котором вы пишите, уже нужно иметь хотя бы поверхностные знания о структурах данных, что они из себя представляют, и как могут повлиять на исполнение вашей программы.
А как же библиотеки? Ведь они решают столько задач! Чтобы рационально использовать библиотеки, их тоже нужно понимать. Во-первых, функции в библиотеки могут иметь побочные эффекты или поведение, которые вы не будете знать без понимания алгоритмов. Получив баг в таком случае можно долго и упорно пытаться его поймать и решить, когда можно было избежать. Во-вторых, различные инструменты и библиотеки часто нужно «настраивать» — говорить им какие алгоритмы, структуры данных и технологии использовать внутри. Без элементарных знаний вам придётся либо идти читать маны, либо выбирать наугад. В-третьих – есть множество задач, которые нельзя решить простым вызовом API библиотеки или фреймворка. Что вы будете делать в таком случае? Тратить часы на поиски возможных решений и просить помощи у друга? В-четвёртых – множество задач решается очень просто несколькими строчками кода или встроенными средствами языка. Если для решения каждого чиха вы будете тянуть библиотеку, то ваши программы будут гигантскими монстрами, занимая по сотни мегабайт и больше на диске, отжирая всю память на сервере, и при том имея довольно скудный функционал. Кроме того, наличие кучи подключенных библиотек влечёт за собой проблемы совместимости, и программа может падать случайным образом из-за странного поведения нескольких библиотек в одном проекте. Бездумное использование библиотек может привести к довольно плачевным последствиям, и разработчики, которые умеют только использовать библиотеки, но не способны решить даже простую проблему самостоятельно, никогда не будут ценится, потому что их решения будут неконкурентоспособны.
Может ли программист обойтись без знаний алгоритмов и теории анализа? Может, и таких «программистов» очень много. Только назвать их программистами можно разве что с большой натяжкой. Ко мне на собеседование приходит очень много программистов, со стажем десять-пятнадцать лет, и толком не понимающих что же они делают и почему. У них своя ниша, они ходят от компании к компании, не задерживаясь в них больше года. Как правило, у них есть небольшой набор задач, которые они могут решать, и если сделать шаг в сторону, то человек теряется и ему нужно обучить себя новым навыкам. Таких людей приглашают на проект, и от них избавляются как можно быстрее, потому что они теряют кучу времени, изобретая велосипеды и читая маны чтобы узнать то, что уже должны были знать из университета. У них как правило нет особо никакой карьеры и нестабильный заработок.
В итоге, для чего нужно знать алгоритмы и теорию анализа, если можно выполнять работу и без этих знаний? Чтобы быть квалифицированным специалистом в своей профессии, иметь карьерный рост и уважение коллег. Чтобы эффективно решать поставленные задачи и не изобретать велосипедов. Чтобы не писать монстров с огромным количеством сторонних библиотек, которые занимают сотни мегабайт на диске от отжирают кучу памяти на сервере и регулярно падают по случайной причине в зависимости от фазы луны. Чтобы эффективно и с максимальными возможностями использовать язык, на которым вы пишете. Чтобы принимать информированные и осмысленные решения по выбору библиотеки и технологии для решения проблемы. Если же ваша работа заключается в написание SQL запроса и вбивание команды в консоль, то хочу вас огорчить: вы не программист, вы – пользователь, вам действительно не нужны алгоритмы и иже с ним, и вы зря потратили время в университете потому что для такой работы достаточно закончить курсы или прочитать пару вводных книжек самостоятельно.
Зачем нужны алгоритмы и паттерны
Нужны ли фронтендеру алгоритмы и паттерны проектирования?
На самом деле, наверняка вы уже их используете, но можете ещё лучше.
Многих пугает слово алгоритм, кажется, что это что-то сложное, но на деле это просто законченный набор инструкций. Получается, что вы используете алгоритмы и в обычной жизни, например, когда готовите по рецепту, или добираетесь по навигатору из точки А в точку Б, или решаете квадратное уравнение.
Когда разработчики говорят об алгоритмах, они имеют ввиду не все алгоритмы, а только популярные решения стандартных задач. Многие алгоритмы были придуманы ещё до компьютеров: например, алгоритм поразрядной сортировки был запатентован в девятнадцатом веке в США для обработки данных, полученных после переписи населения.
Для решения одной и той же задачи могут подходить разные алгоритмы. Представьте, у вас есть список, в котором нужно найти элемент. Предположим, что это список товаров в интернет-магазине и пользователь вводит в фильтр название товара, которое начинается с буквы «Е». Как это сделать?
Если список отсортирован по алфавиту, вам подходит двоичный поиск — вы смотрите в середину списка, находите там товар, название которого начинается например, на «К». Список отсортирован, поэтому вы точно знаете что нужный вам товар находится в левой от вас части списка, потому что «Е» в алфавите стоит раньше, чем «К». Теперь вы берете левую часть списка и повторяете ту же процедуру с ней.
Если список не отсортирован, лучше подойдёт прямой перебор — вы по порядку идёте от начала списка до его конца и пытаетесь найти тот элемент, который вас интересует. В худшем случае вам придётся посмотреть все элементы, но зато вы будете заранее знать время, которое вы потратите на поиск нужного элемента.
Выбирать алгоритм нужно под задачу. Поймите с какими данными вы работаете и отталкивайтесь от этого. Существуют алгоритмы для работы со списками, массивами, деревьями и так далее. Чтобы выбрать алгоритм нужно понимать не только его плюсы, но и минусы: они тоже хорошо известны и описаны. Например, есть сайт, который помогает вам выбрать правильный алгоритм сортировки, наглядно показывая сравнение работы разных алгоритмов на разных списках.
Теперь поговорим о паттернах проектирования. Паттерны — это просто устойчивые конструкции в программировании. Все программисты в мире решают более-менее похожие задачи и для решения этих задач уже выработаны популярные решения. Есть известная книга на эту тему — книга «Банды четырёх», которая так и называется «Design Patterns». Ещё есть две отличные книги от Эдди Османи:
Паттерны помогают сэкономить время на организации кода и сосредоточиться на решении задачи. Есть паттерны, которые говорят вам как правильно написать какие-то отдельные решения в коде, например паттерн «перечисление»; есть паттерны, которые описывают как лучше разделить код приложения по папкам и что писать в конкретных файлах, например паттерн MVC и его родственники MVP и MVVM; а есть паттерны, которые рассказывают как между собой должны общаться разные модули, например паттерн «инверсия контроля».
Может показаться, что для того, чтобы применять паттерны, нужно очень глубоко понимать программирование и работать над сложными задачами, но на деле это не всегда так: часто разработчики используют паттерны, даже не подозревая об этом, потому что некоторые паттерны встроены прямо в языки программирования.
Представьте, что у вас на сайте есть кнопка, на которую нажимает пользователь. И есть алгоритм, который вы хотите запустить, когда пользователь нажимает на эту кнопку. Чтобы связать их между собой используется «обработчик событий» — реализация паттерна «наблюдатель», которая заложена в JavaScript прямо на уровне языка.
Так нужно ли фронтендеру изучать алгоритмы и паттерны? Да, вы всё равно сталкиваетесь с ними в своей работе каждый день и если вы делать это осознанно, то сможете решать свои задачи эффективней.
Кто же ты такой, алгоритм?
Сегодня довольно легко столкнуться с недобросовестными школьными учебниками, в частности с учебниками по информатике. В главах, посвященных алгоритмам, вы можете найти непосредственно определение алгоритма. Не пояснение, о чем идет речь, не рассказ о предмете, а именно определение. Причем выделенное жирным шрифтом, старательно обведенное в рамку и помеченное какой-нибудь заметной пиктограммой в виде восклицательного знака. Обычно приправлено всё это соусом из кучи обязательных и необязательных свойств, образуя в итоге феерический кавардак. Давайте попытаемся понять, что же такое алгоритм, почему мы не может дать ему конкретного определения и выясним, какие свойства являются обязательными, а какие нет.
Составителей учебников легко понять, ведь на самом деле строгого определения алгоритма не существует, и более того, такого определения быть не может. Но вместо попыток объяснить, что к чему, авторы подсовывают бедным ученикам еще одно задание по зубрежке бесполезных и неправильных терминов. Чтобы не быть голословным, приведу выдержку из одного весьма распространенного учебника:
В университетах дела обстоят получше, однако автору этих строк на курсе по математической логике и теории алгоритмов пришлось столкнуться все с тем же винегретом из определения алгоритма и его свойств. Разберемся, что тут не так.
Бесконечность не предел
Такой же трюк с нумерацией не пройдет для бесконечных непериодических дробей (иррациональных чисел). Допустим такое множество счетное, то есть элементы этого множества можно пронумеровать натуральными числами. Тогда рассмотрим бесконечную десятичную дробь с нулевой целой частью, у которой первая цифра после запятой не равняется цифре на той же позиции у дроби с номером 1, вторая цифра не равняется цифре на второй позиции у дроби с номером 2 и т.д. Тогда полученная дробь будет заведомо отличаться от всех дробей хотя бы одной цифрой. Получается для нее не нашлось номера в нашей бесконечной нумерации! Примененная схема доказательства называется канторовским диагональным методом в честь придумавшего ее математика Георга Кантора.
Про бесконечные дроби
Не стоит делать ошибку, записывая в иррациональные числа все бесконечные дроби. Иррациональными являются только те числа, которые нельзя представить в виде несократимой дроби вида m/n. В десятичной системе счисления дроби 1/3 и 2/7 тоже окажутся бесконечными, однако их «бесконечность« обусловлена выбранной системой счисления. В системе счисления по основанию 21 эти дроби будут иметь конечное представление, а вот, например, дробь 1/2 окажется бесконечной (периодической).
Говорят, что множество бесконечных десятичных дробей имеет мощность континуум, которая обозначается символом ℵ1 (алеф-один). В дальнейшем нам понадобится следующее множество. Рассмотрим некоторый алфавит (конечное множество символов). Теперь представим множество всех конечных цепочек символов алфавита A*. Коль скоро алфавит конечен, и каждая цепочка конечна, то множество таких цепочек счетно (их можно пронумеровать натуральными числами).
На сколько велика бесконечность?
Допустим в наш алфавит вошли все придуманные на земле символы: русский алфавит, японские иероглифы, шумерская клинопись и т.д. Тогда в наше множество войдут все написанные когда-либо книги, все книги, которые будут написаны и все книги, которые никто не стал бы писать (например, хаотичные последовательности символов). Кроме того, представим книгу, толщиной в Солнечную систему и диагональю листа равной диаметру Млечного Пути, набранную 12-м шрифтом. В наше придуманное множество войдут все такие книги, отличающиеся хотя бы одним символов, и не только они, ведь вселенная бесконечна! Кто мешает представить себе книгу, размером в миллиарды световых лет? А все такие книги? Уже на этом этапе воображение может давать сбои, а ведь наше множество всего лишь счетное. Чтобы дополнить множество до континуума, нужно рассмотреть бесконечную книгу, по сравнению с которой, предыдущие книги — детские игрушки. Но и одной бесконечной книги нам не хватит, нужно рассмотреть все бесконечные книги.
Конструктивно оперировать континуальными бесконечностями невозможно. Даже работая со счетными множествами, мы не рассматриваем сами множества, а только говорим, что какой бы не был элемент N, всегда найдется элемент N+1. Если мы ставим себе прикладную задачу, появление в наших рассуждениях континуальной бесконечности должно служить нам «тревожной лампочкой»: осторожно, выход за пределы конструктивного.
Алгоритмы и вычислимость
Компьютер проводит свои вычисления, подчиняясь некоторой программе, которая воплощает собой конструктивную процедуру, или алгоритм. Не сложно догадаться, что алгоритм как раз и есть то правило, по которому вычисляется функция. Можно сказать, функция считается вычислимой, если для нее существует некоторый алгоритм.
Понятия алгоритм и вычислимая функция оказываются настолько заковыристыми, что некоторые составители учебной литературы не утруждают себя попытками разъяснить их суть. Дело в том, что определения алгоритма не существует, и кроме того, существовать не может, иначе пришлось бы выбросить на свалку целый раздел математики — теорию вычислимости. Попробуем разобраться более подробнее.
Частично-рекурсивные функции и тезис Черча
Все началось с того, что математик Давид Гильберт в 1900 году предложил список нерешенных на тот момент математических проблем. Позже выяснилось, что десятая проблема (проблема решения произвольного диофантового уравнения) оказалось неразрешимой, но для доказательства этого факта пришлось составить целую новую математическую теорию. Вопросами того, какие задачи можно конструктивно решить, и что такое конструктивное решение, занялись математики Курт Гедель, Стивен Клини, Алонсо Черч и Алан Тьюринг.
Курт Гедель наиболее известен тем, что сформулировал и доказал 2 теоремы о неполноте. Между прочим, сделал он это в возрасте всего лишь 24 лет.
Как выяснилось выше, континуальные бесконечности не всегда подходят под конструктивные рассуждения, поэтому Гедель и Клини предложили рассматривать только функции натурального аргумента (при необходимости любые функции над счетными множествами можно привести к «натуральным функция» путем замены элементов множеств их номерами). Изучая вычислимость таких функций, Гедель, Клини, Аккерман и другие математики пришли к так называемому классу частично-рекурсивных функций. В качестве определения этого класса рассматривается набор базовых, очень простых функций (константа, увеличение на единицу и проекция, которая сопоставляет функции многих аргументов один из ее аргументов) и операторов, позволяющих из функций строить новые функции (операторы композиции, примитивной рекурсии и минимизации). Слово «частичные» показывает, что эти функции определены лишь на некоторых числах. На остальных они не могут быть вычислены. Попытки расширить класс частично-рекурсивных функций ни к чему не привели, так как введение новых операций приводило к тому, что получалось множество функций, совпадающее с классом частично-рекурсивных. В дальнейшем Алонсо Черч отказался от попыток расширения этого класса, заявив, что, видимо:
Частично-рекурсивные функции соответствуют вычислимым функциям в любом разумном понимании вычислимости.
Это утверждение называют тезисом Черча. Стоит отметить, что тезис Черча не является теоремой или доказанным утверждением. Во-первых, не понятно, что такое «разумное понимание», во-вторых, превратив тезис Черча в доказанный факт, мы лишаем себя перспектив дальнейшего исследования вычислимости и механизмов вычислений. Никто, впрочем, не мешает попробовать определить такой набор операций, который был бы мощнее базиса для частично-рекурсивных функций. Только вот, до сих пор это никому не удавалось сделать.
Ученые долго не могли привести пример частично-рекурсивной функции, не являющейся примитивно-рекурсивной (без оператора минимизации). Наконец это удалось Вильгельму Аккерману. Предложенная функция Аккермана растет так быстро, что количество цифр в десятичной записи числа A(4,4) превосходит количество атомов во Вселенной.
Формальная теория алгоритмов во многом построена аналогично теории вычислимости. Считается, что алгоритм есть некое конструктивное преобразование входного слова (цепочки символов некоторого алфавита) в некоторое выходное слово. Опять же, здесь мы имеем с функциями вида A*->A*. Конечно, предложенное описание не подходит под определение алгоритма, так как неясно, что же такое «конструктивное преобразование». Хоть понятия алгоритма и вычислимой функции близки, не стоит их смешивать. Для одного и того же алгоритма может быть предъявлено сколько угодно его записей на каком-нибудь формальном языке, но соответствующая вычислимая функция всегда одна. Один из основателей формальной теории алгоритмов, Алан Тьюринг, предложил формальную модель автомата, известного как машина Тьюринга. Тезис Тьюринга гласит:
Каково бы не было разумное понимание алгоритма, любой алгоритм, соответствующий такому пониманию, может быть реализован на машине Тьюринга.
Любые попытки построить более мощные автомат заканчивались неудачей: для каждого такого автомата (машина Поста, нормальные алгоритмы Маркова, автоматы с регистрами и несколькими лентами) удавалось построить аналогичную машину Тьюринга. Некоторые ученые объединяют тезис Черча и тезис Тьюринга в тезис Черча-Тьюринга, так как они весьма близки по духу.
С помощью такого незамысловатого автомата можно формализовать любой алгоритм.
Таким образом, определив понятие алгоритма, мы будем вынуждены забыть о тезисе Черча-Тьюринга, и отказаться от целой математической теории, богатой содержанием и подарившую нам множество практических результатов.
Свойства алгоритмов
Мы выяснили, почему у алгоритма не может быть конкретного определения. Однако можно определить свойства, которыми должен обладать каждый алгоритм. К сожалению, в литературе часто смешивают обязательные и необязательный свойств. Разберемся подробнее.
Обязательные свойства
Начнем с обязательных свойств. Алгоритм можно записать в виде конечного текста из символов конечного алфавита. Действительно, бесконечный текст мы не можем записать чисто технически, а раз алгоритмы имеют отношение к конструктивной деятельности, бесконечными они быть не могут. Возможность представить алгоритм в виде конечного текста можно назвать свойством объективности и конечности.
Еще одно достаточно очевидное свойство любого алгоритма — его дискретность. Независимо от исполнителя, исполнение алгоритма представляет собой дискретный процесс, при рассмотрение распадающийся на элементарные действия. Понимать дискретность можно и в том смысле, что любая информация, над которой работает алгоритм может быть представлена в виде текста.
Третье фундаментальное свойство алгоритмов называется детерминированностью. Оно заключается в том, что следовать предписанной процедуре можно только одним способом. Единственное, что может повлиять на ход выполнения — это исходные данные, однако при одних и тех же исходных данных, алгоритм всегда выдает один и тот же результат.
Эти три свойства присущи всем алгоритмам. Если нарушено хотя бы одно из них, перед нами уже не алгоритм. С натяжкой к обязательным свойствам можно добавить понятность для исполнителя, хотя это уже на грани фола. По большей части. это относится не к самому алгоритму, а к его записи.
«Винегрет» из свойств из того же учебника по информатике.
Необязательные свойства
Наряду с обязательными свойствами, алгоритм может обладать некоторыми частными свойствами, которые вовсе не обязательны. Начнем с массовости. Конечно, хочется, чтобы алгоритмы решали классы задач в зависимости от входных данных. Однако существуют алгоритмы, которые вообще не зависят от входных данных, например всем известный вывод на экран «Hello world». Как среди вычислимых функций существуют константные, так и среди алгоритмов существуют генераторы единственного результата.
Теперь рассмотрим широко распространенное убеждение, что алгоритмы должны обладать свойством правильности и завершаемости. Начнем с правильности. Такое свойство попросту невозможно формализовать, так как отсутствуют критерии этой правильности. Наверняка, многие из вас сталкивались с ситуацией, когда программист считает программу правильной, а заказчик нет. С завершаемостью дела обстоят интереснее. Рассмотрим термин «применимость« — алгоритм называется применимым к слову, если, получив на вход это слово, он завершается за конечное число шагов. Самое интересное то, что проблема применимости является алгоритмически неразрешимой, то есть невозможно составить алгоритм, которые определял бы по записи алгоритма и входному слову, завершится ли он за конечное число шагов. Никто не мешает вам составить программу, состоящую только из одного бесконечного цикла. И эта программа все еще будет алгоритмом.
Про зависающие программы
Программы, которые не могут зациклиться, на самом деле входят в класс примитивно-рекурсивных — подмножество частично-рекурсивного класса. Отличает их отсутствия оператора минимизации. Он то и вносит пикантности. Если вы используете «неарифметический цикл» while или рекурсию, для которых нельзя заранее определить, сколько раз они выполняться, то ваша программа сразу переходит из класса примитивно-рекурсивных в класс частично-рекурсивных.
Теперь перейдем к пресловутой последовательности шагов. Дело в том, что алгоритм может быть представлен в любой из имеющихся формальных систем (частично-рекурсивные функции, машина Тьюринга, лямбда-исчисление и т.д.). Воплощение алгоритма в виде компьютерной программы далеко не всегда будет описанием последовательности шагов. Здесь все зависит от парадигмы программирования. В императивной парадигме программисты действительно оперируют последовательностью действий. Однако существуют и другие парадигмы, такие как функциональная (привет Haskell программистам), где нету никаких действий, а лишь функции в сугубо математическом смысле, или чистая объектно-ориентированная, которая основана не на «последовательности действий», а на обмене сообщениями между абстрактными объектами.
Заключение
Иногда мир устроен несколько сложнее, чем хотелось бы. Существующие формализмы в теории алгоритмов не более чем абстрактные математические системы, наподобие геометрии Евклида или теории вероятности, тогда как понятие вычислимости, возможно, находится вне математики и является свойством нашей Вселенной наряду со скоростью света и законом всемирного тяготения. И хотя, скорее всего, нам так и не удастся ответить на вопрос, что такое алгоритмы и вычислимость, попытки найти ответ на этот вопрос оказались более ценными, чем возможный однозначный ответ.
Материал данной статьи во многом опирается на 1-ый том «Программирование: введение в профессию» А. В. Столярова. Тем, кто хочет подробнее изучить вопросы, связанные с алгоритмами и теорией вычислимости, кроме этой книги, советую Босс В «От Диофанта до Тьюринга» и трехтомник А. Шеня по математической логике и теории алгоритмов.
Дата-центр ITSOFT — размещение и аренда серверов и стоек в двух дата-центрах в Москве. За последние годы UPTIME 100%. Размещение GPU-ферм и ASIC-майнеров, аренда GPU-серверов, лицензии связи, SSL-сертификаты, администрирование серверов и поддержка сайтов.