Для чего нужны алгоритмы
Что такое алгоритм: о сложном – простыми словами
О том, что такое алгоритмы и как они влияют на нашу жизнь.
Наверняка вы слышали слово «алгоритм». Этот термин широко используется в современной жизни. И если вставить слово в повседневный разговор не составит труда, намного сложнее объяснить, что именно это такое. Сегодня поговорим о значении слова и об истинной природе алгоритмов, которые существовали в человеческой жизни еще до момента появления компьютерных технологий.
1. Алгоритм – это набор конкретных инструкций
Простыми словами, «алгоритм – это последовательность инструкций», говорит Педро Домингос, профессор компьютерных наук в Вашингтонском университете и автор книги «Верховный алгоритм. Как машинное обучение изменит наш мир».
Как испечь пирог, найти значение суммы 2+2 или управлять страной в соответствии с Конституцией – все это алгоритмы. Но чаще всего это слово связывают со сферой IT. В этом случае под «алгоритмом» понимается «последовательность инструкций, которые говорят компьютеру, что делать».
Любая компьютерная программа – это алгоритм, написанный на языке компьютерного программирования, который компьютер может понять и выполнить. И это устроено намного сложнее, чем в обычной жизни.
«Компьютерные алгоритмы должны быть предельно точны. Для их определения могут потребоваться миллионы строк», – подчеркивает профессор.
2. Люди писали и использовали алгоритмы задолго до появления компьютеров
Несмотря на то что сегодня алгоритмы используются в контексте компьютерных технологий, их история намного старше ПК. Люди создавали алгоритмы еще в Вавилонскую эпоху – они помогали им решать математические уравнения и управлять земледельческим обществом.
«Все потому, что для выполнения алгоритма не всегда нужен компьютер – им могут управлять сами люди», – утверждает Домингос.
С появлением и распространением компьютеров во второй половине XX-го века алгоритмы начали активно использоваться в военной сфере (для определения того, куда навести ракету), а позже в области бизнес-администрирования (в приложениях для расчета заработной платы) и науки (прогноз погоды).
Поворотный момент для развития современных алгоритмов наступил, когда Ларри Пейдж и Сергей Брин создали Google PageRank. Вместо того чтобы просто полагаться на информацию на странице для определения ее релевантности поисковому запросу, алгоритм поисковой системы учитывал множество других сигналов, которые помогали ему выявлять наилучшие результаты.
Например, сколько других ссылок указывало на статью и насколько авторитетными были эти статьи, в зависимости от количества ссылок, указывающих на эти страницы, и так далее.
3. Сегодня алгоритмы повсюду
С распространением компьютеров и Интернета алгоритмы стали неотъемлемой частью нашей повседневной жизни. На них основаны новостные ленты социальных сетей, которые определяют, какой контент показывать вам при скроллинге, а также механизмы интернет-магазинов, предлагающих вам товары, которые могли бы вам понравиться.
«Facebook может разместить в вашей новостной ленте кучу постов и публикаций, но благодаря алгоритму он довольно избирателен, – сказал Домингос. – Обычно он учитывает целую комбинацию факторов. Например, как часто вы взаимодействуете с людьми, которые прямо или косвенно создали этот пост; насколько публикации близки вам в вашей социальной сети; насколько они актуальны с точки зрения тематики, насколько свежи и т. д.».
По словам профессора Домингоса, мы сталкиваемся с алгоритмами на протяжении всей нашей жизни и даже можем об этом не подозревать. Например, благодаря алгоритму посудомоечная машина узнает, когда пора переходить от стирки к сушке. Это алгоритм определяет, как ваш автомобиль регулирует потребление топлива и понимает, когда его бак на заправке становится полным.
«Совершенно очевидно, что каждый раз, когда вы пользуетесь компьютером или Интернетом, вы имеете дело с алгоритмами, – подчеркнул Домингос. – В наши дни они задействованы практически во всем».
4. В самых сложных алгоритмах используется машинное обучение
Благодаря технологическому прогрессу современные алгоритмы претерпевают дальнейшие изменения. Особенно с появлением машинного обучения – разновидности искусственного интеллекта (ИИ).
«В традиционном программировании человек должен записывать каждую мелочь, для того чтобы это сделал другой, что очень затратно по времени и средствам, – объяснил Домингос. – Машинное обучение – это компьютер, использующий свои собственные алгоритмы вместо того, чтобы ему говорили, что делать».
Другими словами, машинное обучение – это когда программист вводит в программу необработанные данные в качестве отправной точки, а затем задает конечную точку того, как выглядит организованная, классифицированная версия этих данных.
Остальное делает программа: она самостоятельно выясняет, как добраться из пункта А в пункт Б. Рассмотрим пример из кулинарии. Человек, который умеет готовить, может превратить обычный лук из сырого в карамелизированные обжаренные кусочки.
В традиционном варианте программист должен был бы прописать каждый шаг инструкции по приготовлению лука. Но в алгоритме, разработанном ИИ, с учетом конечной точки-цели, программа сама должна выяснить, как перейти от сырого состояния к карамелизированному. Это значит, что машина учится этому самостоятельно.
Такие типы алгоритмов становятся еще более мощными, когда человек не знает, как добраться из точки А в точку Б. Например, человеческий процесс, такой как способность понимать, что кошка это кошка, требует сложных умственных способностей, которые невозможно расписать пошагово.
Но если дать программе набор фотографий кошки и предметов, которые кошкой не являются, и показав желаемую конечную точку в качестве категоризации изображения кошки в виде животного, компьютер научится выполнять этот процесс самостоятельно.
«Это возможность создавать мощные сложные алгоритмы с минимальным вмешательством человека», – подчеркивает Домингос.
5. Алгоритмы – это не волшебство
Из-за большого количества обрабатываемых алгоритмов данных может показаться, что они ключ ко всем загадкам человечества. Но важно помнить, что алгоритм – всего лишь набор инструкций. Более того, его создают люди, а это значит, что он может быть ошибочным. Люди, которые не очень разбираются в компьютерах, часто полагают, что «алгоритмы идеальны». Что в корне неверно.
Домингос объяснил, что программисты тратят огромное количество времени на исправление ошибок в алгоритмах. Все для того, чтобы они давали соответствующие результаты.
«Кроме того, в традиционном программировании вы должны беспокоиться о предвзятости программиста, – говорит Домингос. – В машинном обучении вы в основном должны беспокоиться о предвзятости, исходящей от данных».
Например, алгоритм найма, основанный на машинном обучении, может использовать в качестве отправной точки множество резюме кандидатов, а в качестве результата – резюме людей, которые были наняты в прошлом. Однако большинство технологических компаний не отличаются расовым разнообразием.
Таким образом, автоматизированный алгоритм, который дает рекомендации по найму, может отражать это реальное неравенство: исследования показали, что искусственный интеллект может отражать гендерные и расовые стереотипы людей, которые их обучают.
6. Алгоритмы по-прежнему способны изменить мир
Алгоритмы могут быть несовершенными, но они все равно меняют наш мир. «Все эти вещи, которые мы принимаем как должное – Интернет, социальные сети и так далее, – они бы не существовали без алгоритмов», – сказал Домингос.
«Современные алгоритмы делают для умственного труда то же, что когда-то сделала промышленная революция с ручным трудом. Алгоритмы – это автоматизация интеллекта. И очень мощное средство: то, что раньше требовало больших умственных и физических усилий, теперь можно сделать с помощью алгоритма… Алгоритмы никуда не денутся. Но только от нас зависит то, какими мы их создадим – предвзятыми или справедливыми, полезными или вредными», – подытожил профессор.
Что такое алгоритмы и зачем они нужны
Содержание статьи
Конечно, собрать кубик Рубика можно и без памятки, просто перемещая грани в случайном порядке. Но перебор возможных вариантов может занять долгое время, это будет непроизводительный и неоптимальный процесс. Гораздо удобнее иметь список шагов, последовательное выполнение которых всегда будет приводить к положительному результату. Именно эти принципы легли в такое понятие как «алгоритм».
Алгоритм — совокупность инструкций (шагов), описывающих порядок операций исполнителя для достижения результата решения задачи за конечное число действий.
Что такое «исполнитель»?
Для наилучшего понимания алгоритма вообще, необходимо также рассмотреть понятие «исполнитель алгоритма». Под исполнителем в понятии алгоритма подразумевается абстрактная система, способная выполнять действия, описываемые алгоритмом, а также обладающая рядом характеристик. В качестве исполнителя чаще всего подразумевается то или иное техническое средство (3D-принтер, станок с ЧПУ, ЭВМ), однако стоит понимать, что это широкое понятие: исполнителем может являться, например, человек.
Тем не менее, исполнителем может быть названа только система, одновременно обладающая рядом параметров:
— отказами, в случае, если выполнение действий невозможно.
Свойства алгоритмов
Ограничения, накладываемые на понятие «исполнитель» приводят к тому, что само понятие «алгоритм» также обладает рядом свойств и ограничений. Алгоритмы получили широкое распространение именно благодаря этим ограничениям, которые способствуют стандартизации. Среди свойств алгоритмов можно выделить:
— массовость (способность алгоритма оставаться правильным при разных наборах входных данных);
— определенность (на любом шаге алгоритма у исполнителя должно быть достаточно данных, чтобы его выполнить);
— детерминированность (при одних и тех же наборах входных данных должен получаться один и тот же результат);
Зачем нужны алгоритмы?
Вышеприведенные свойства обеспечивают алгоритмам широкое применение. Так алгоритмы служат для стандартизации описаний любых процессов. Без алгоритмов были бы невозможны любые виды вычислений, а решение любой проблемы начиналось бы «с нуля» — даже если она была решена множество раз. Применение алгоритмов позволяет быстро решать однотипные задачи, сократить время на поиск решения, автоматизировать процесс его нахождения, а также распространять найденное решение в стандартизованной — а значит, понятной всем форме.
Зачем программисту изучать алгоритмы
руководитель программ «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, где собраны упражнения для любого уровня подготовки. Попробовать решить типичные для алгоритмических собеседований задачи можно и в бесплатной части курса «Алгоритмы для разработчиков» в Яндекс.Практикуме.
Зачем программисту знать алгоритмы
Если посмотреть на все эти статьи, то можно заметить, что люди, которые их пишут, фактически обижены на университеты за то, что их заставили учить много сложного материала — в виде алгоритмического анализа, сложных алгоритмов и структур данных — который им вроде бы не пригодился. По сути, авторы статей обижены на университеты из-за того, что там не смогли предсказать будущую область работы авторов и дать им только минимально нужный набор навыков. Ведь действительно, чтобы писать простенькие сайты и скрипты, не нужно особого знания алгоритмов и структур данных. Или всё-таки нужно?
Давайте подумаем, что же нужно учить программисту в университете, для того чтобы приобрести необходимые навыки для успешной карьеры. Библиотеки? Фреймворки? Они устаревают, интерфейсы к ним меняются, все они написаны чаще всего под один язык, который студенты могут и не использовать никогда в индустрии. Всех учить писать сайты? Или всех учить писать ОС? Образование должно охватывать как можно большую аудиторию и давать максимально возможный набор навыков. Программист в первую очередь должен уметь анализировать и решать проблемы – это основной навык, которым должны обзавестись выпускники факультетов информатики. Написание кода – это просто необходимый инструмент, который используется для решения задач. Кто может знать какие навыки вам понадобятся в будущем? Таким образом учить теорию – это наиболее оптимально с точки зрения образования. Полученные навыки можно применить в любой области, а выучить библиотеку или фреймворк имея хорошую базу знаний не составит большого труда. Парадоксально то, что люди задающие вопросы про нужность алгоритмов, как правило имеют какие-то знания в этой области. Я не помню ни одного человека, который не имел знаний в области теории вычислений, и с гордостью кричал об этом, утверждая, что ему они не нужны.
Итак, вы абстрактный программист в вакууме, работаете десять с лишним лет клепая сайты и решая простые однотипные задачи клиентов/компании. Вам хорошо и уютно в вашей нише, и только мучительно больно за бесцельно потраченное время в классе по теории вычислений и алгоритмическому анализу, который вам ничего не дал. По утрам закуривая сигарету за чашкой кофе, в глубине философских размышлений о бренности бытия вы задумываетесь: зачем же программистам, не решающим сложных задач, знать алгоритмы и основы анализа. Короткий ответ: чтобы быть квалифицированным специалистом и эффективно использовать доступные инструменты, включая язык, на котором вы пишите. Теория алгоритмов и анализа учит не только экзотические алгоритмы и структуры данных в виде АВЛ и красно-чёрных деревьев. Она также даёт представления о том, как эффективно организовать данные, как писать код с максимальной производительностью, где в системе возможно бутылочное горлышко и как с ним бороться. Вас ознакамливают с готовыми решениями, чтобы вы не писали велосипедов, и не бежали в гугл каждый раз, когда нужно сделать что-то нетривиальное.
Знания теории анализа и алгоритмов применяются всеми программистами на самом деле каждый день, просто мы привыкли к этим вещам настолько, что даже не задумываемся над этим. Какую бы задачу вы не решали – будь то простой сайт с выборкой данных из БД, или баш скрипт на сервере, вы будете использовать какие-то структуры данных. Как минимум примитивный массив, а скорее всего и что-то посложнее. Языки дают нам множество различных структур, многие из которых взаимозаменяемы. Часто мы имеем несколько вариаций одного абстрактного типа с разными реализациями. Например, в С++ есть структуры данных vector и list. Чем они отличаются, и какие будут преимущества и недостатки использования одного или другого? Как в С++ реализована map, и чем она отличается от multimap? Как реализован list в Python – через массив или связным списком и как лучше всего с ним работать? Почему в C# нежелательно использовать ArrayList, а вместо него использовать List? Как реализован SortedDictionary и как он повлияет на исполнение программы если будет использован вместо Dictionary? Как работает continuation, когда её нужно использовать, и будут ли какие-то побочные эффекты при её использовании? Когда вы в последний раз использовали каррированные функции, которые есть почти в каждом языке? Если вы думаете, что map в С++ реализована как хэш-таблица, вы ошибаетесь. Она реализована на красно-чёрных деревьях, а хэш-таблицей реализована unordered_map. Отдельно стоит упомянуть динамическое программирование. Понимание что это такое, как можно оптимально переписать рекурсивные функции и что такое мемоизация, часто поможет избежать выстрела себе в ногу. Таким образом просто чтобы полноценно и эффективно использовать язык, на котором вы пишите, уже нужно иметь хотя бы поверхностные знания о структурах данных, что они из себя представляют, и как могут повлиять на исполнение вашей программы.
А как же библиотеки? Ведь они решают столько задач! Чтобы рационально использовать библиотеки, их тоже нужно понимать. Во-первых, функции в библиотеки могут иметь побочные эффекты или поведение, которые вы не будете знать без понимания алгоритмов. Получив баг в таком случае можно долго и упорно пытаться его поймать и решить, когда можно было избежать. Во-вторых, различные инструменты и библиотеки часто нужно «настраивать» — говорить им какие алгоритмы, структуры данных и технологии использовать внутри. Без элементарных знаний вам придётся либо идти читать маны, либо выбирать наугад. В-третьих – есть множество задач, которые нельзя решить простым вызовом API библиотеки или фреймворка. Что вы будете делать в таком случае? Тратить часы на поиски возможных решений и просить помощи у друга? В-четвёртых – множество задач решается очень просто несколькими строчками кода или встроенными средствами языка. Если для решения каждого чиха вы будете тянуть библиотеку, то ваши программы будут гигантскими монстрами, занимая по сотни мегабайт и больше на диске, отжирая всю память на сервере, и при том имея довольно скудный функционал. Кроме того, наличие кучи подключенных библиотек влечёт за собой проблемы совместимости, и программа может падать случайным образом из-за странного поведения нескольких библиотек в одном проекте. Бездумное использование библиотек может привести к довольно плачевным последствиям, и разработчики, которые умеют только использовать библиотеки, но не способны решить даже простую проблему самостоятельно, никогда не будут ценится, потому что их решения будут неконкурентоспособны.
Может ли программист обойтись без знаний алгоритмов и теории анализа? Может, и таких «программистов» очень много. Только назвать их программистами можно разве что с большой натяжкой. Ко мне на собеседование приходит очень много программистов, со стажем десять-пятнадцать лет, и толком не понимающих что же они делают и почему. У них своя ниша, они ходят от компании к компании, не задерживаясь в них больше года. Как правило, у них есть небольшой набор задач, которые они могут решать, и если сделать шаг в сторону, то человек теряется и ему нужно обучить себя новым навыкам. Таких людей приглашают на проект, и от них избавляются как можно быстрее, потому что они теряют кучу времени, изобретая велосипеды и читая маны чтобы узнать то, что уже должны были знать из университета. У них как правило нет особо никакой карьеры и нестабильный заработок.
В итоге, для чего нужно знать алгоритмы и теорию анализа, если можно выполнять работу и без этих знаний? Чтобы быть квалифицированным специалистом в своей профессии, иметь карьерный рост и уважение коллег. Чтобы эффективно решать поставленные задачи и не изобретать велосипедов. Чтобы не писать монстров с огромным количеством сторонних библиотек, которые занимают сотни мегабайт на диске от отжирают кучу памяти на сервере и регулярно падают по случайной причине в зависимости от фазы луны. Чтобы эффективно и с максимальными возможностями использовать язык, на которым вы пишете. Чтобы принимать информированные и осмысленные решения по выбору библиотеки и технологии для решения проблемы. Если же ваша работа заключается в написание SQL запроса и вбивание команды в консоль, то хочу вас огорчить: вы не программист, вы – пользователь, вам действительно не нужны алгоритмы и иже с ним, и вы зря потратили время в университете потому что для такой работы достаточно закончить курсы или прочитать пару вводных книжек самостоятельно.