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

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

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

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

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

Для создания алгоритма (программы) необходимо знать:

    полный набор исходных данных задачи (начальное состояние объекта);

    цель создания алгоритма (конечное состояние объекта);

    систему команд исполнителя (то есть набор команд, которые исполнитель понимает и может выполнить).

Полученный алгоритм (программа) должен обладать следующим набором свойств:

    дискретность (алгоритм разбит на отдельные шаги - команды);

    однозначность (каждая команда определяет единственно возможное действие исполнителя);

    понятность (все команды алгоритма входят в систему команд исполнителя);

    результативность (исполнитель должен решить задачу за конечное число шагов).

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

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

Обозначение Описание Примечания
Начало и конец алгоритма
Ввод и вывод данных. Вывод данных иногда обозначают иначе:
Действие В вычислительных алгоритмах так обозначают присваивание
Развилка Развилка - компонент, необходимый для реализации ветвлений и циклов
Начало цикла с параметром
Типовой процесс В программировании - процедуры или подпрограммы
Переходы между блоками

Приведем пример описания алгоритма суммирования двух величин в виде блок-схемы:

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

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

Линейная структура (следование).

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

Ветвление.

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

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

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


Цикл (повторение).

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

Ц иклы «д о » - повторение тела цикла до выполнения условия:

Ц иклы «п ока » - повторение тела цикла пока условие выполняется (истинно):

Ц иклы со счётчиком (с параметром) – повторение тела цикла заданное число раз:

Вспомогательный алгоритм (подпрограмма, процедура).

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

Методы разработки сложных алгоритмов.

Существует два метода разработки сложных алгоритмов:

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

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

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

В простейшем случае таких объектов два:

С точки зрения информатики управляющие воздействия можно рассматривать как управляющую информацию. Информация может передаваться в форме команд. Последовательность команд по управлению объектом, приводящая к заранее поставленной цели, называется алгоритмом управления . Следовательно, объект управления можно назвать исполнителем управляющего алгоритма. В рассмотренном примере, управляющий объект работает "не глядя" на то, что происходит с управляющим объектом (управление без обратной связи ). Такая схема управления называется незамкнутой . Другая схема управления может учитывать информацию о процессах, происходящих в объекте управления:

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

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

Часто появляются статьи вида «нужны ли программисту алгоритмы», и все они имеют примерно одинаковый шаблон. Автор статьи как правило пишет: «Я N лет пишу сайты/скрипты в 1С, и никогда не пользовался алгоритмами или структурами данных. Тут же приводятся в пример красно-чёрные деревья или какие-нибудь другие экзотические структуры, которые в области, в которой работает автор не часто увидишь, если увидишь вообще. Такие статьи сводятся к тому, что в конкретной области программисты не используют сложные структуры данных и не решают NP задач.

Сама постановка такого вопроса в корне не верна. Количество специальностей в индустрии растёт постоянно, и человек, который пишет сайты на.net будет заниматься совсем другими вещами, нежели человек, пишущий драйвера для сенсоров на ARM архитектуре под экзотической ОС. Давайте прежде всего определим, что же такое алгоритм. Неформально Кормен определяет алгоритм как строго определённую процедуру, которая принимает одно или несколько значений как ввод, и возвращает одно или несколько значений как результат. Формально алгоритм определяется в разных моделях вычислений: операции, которые можно выполнить на машине Тьюринга или с помощью лямбда-исчислений. Таким образом фактически любой код, который что-то делает, является алгоритмом. Получается, что вопрос «нужны ли программисту алгоритмы» можно перевести как «нужно ли программисту уметь писать код». Правильно такой вопрос должен звучать что-то вроде: «нужно ли программисту в отрасли Х знать продвинутые алгоритмы и детали теории вычислений».

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

Давайте подумаем, что же нужно учить программисту в университете, для того чтобы приобрести необходимые навыки для успешной карьеры. Библиотеки? Фреймворки? Они устаревают, интерфейсы к ним меняются, все они написаны чаще всего под один язык, который студенты могут и не использовать никогда в индустрии. Всех учить писать сайты? Или всех учить писать ОС? Образование должно охватывать как можно большую аудиторию и давать максимально возможный набор навыков. Программист в первую очередь должен уметь анализировать и решать проблемы – это основной навык, которым должны обзавестись выпускники факультетов информатики. Написание кода – это просто необходимый инструмент, который используется для решения задач. Кто может знать какие навыки вам понадобятся в будущем? Таким образом учить теорию – это наиболее оптимально с точки зрения образования. Полученные навыки можно применить в любой области, а выучить библиотеку или фреймворк имея хорошую базу знаний не составит большого труда. Парадоксально то, что люди задающие вопросы про нужность алгоритмов, как правило имеют какие-то знания в этой области. Я не помню ни одного человека, который не имел знаний в области теории вычислений, и с гордостью кричал об этом, утверждая, что ему они не нужны.

Итак, вы абстрактный программист в вакууме, работаете десять с лишним лет клепая сайты и решая простые однотипные задачи клиентов/компании. Вам хорошо и уютно в вашей нише, и только мучительно больно за бесцельно потраченное время в классе по теории вычислений и алгоритмическому анализу, который вам ничего не дал. По утрам закуривая сигарету за чашкой кофе, в глубине философских размышлений о бренности бытия вы задумываетесь: зачем же программистам, не решающим сложных задач, знать алгоритмы и основы анализа. Короткий ответ: чтобы быть квалифицированным специалистом и эффективно использовать доступные инструменты, включая язык, на котором вы пишите. Теория алгоритмов и анализа учит не только экзотические алгоритмы и структуры данных в виде АВЛ и красно-чёрных деревьев. Она также даёт представления о том, как эффективно организовать данные, как писать код с максимальной производительностью, где в системе возможно бутылочное горлышко и как с ним бороться. Вас ознакамливают с готовыми решениями, чтобы вы не писали велосипедов, и не бежали в гугл каждый раз, когда нужно сделать что-то нетривиальное.

Знания теории анализа и алгоритмов применяются всеми программистами на самом деле каждый день, просто мы привыкли к этим вещам настолько, что даже не задумываемся над этим. Какую бы задачу вы не решали – будь то простой сайт с выборкой данных из БД, или баш скрипт на сервере, вы будете использовать какие-то структуры данных. Как минимум примитивный массив, а скорее всего и что-то посложнее. Языки дают нам множество различных структур, многие из которых взаимозаменяемы. Часто мы имеем несколько вариаций одного абстрактного типа с разными реализациями. Например, в С++ есть структуры данных vector и list. Чем они отличаются, и какие будут преимущества и недостатки использования одного или другого? Как в С++ реализована map, и чем она отличается от multimap? Как реализован list в Python – через массив или связным списком и как лучше всего с ним работать? Почему в C# нежелательно использовать ArrayList, а вместо него использовать List? Как реализован SortedDictionary и как он повлияет на исполнение программы если будет использован вместо Dictionary? Как работает continuation, когда её нужно использовать, и будут ли какие-то побочные эффекты при её использовании? Когда вы в последний раз использовали каррированные функции, которые есть почти в каждом языке? Если вы думаете, что map в С++ реализована как хэш-таблица, вы ошибаетесь. Она реализована на красно-чёрных деревьях, а хэш-таблицей реализована unordered_map. Отдельно стоит упомянуть динамическое программирование. Понимание что это такое, как можно оптимально переписать рекурсивные функции и что такое мемоизация, часто поможет избежать выстрела себе в ногу. Таким образом просто чтобы полноценно и эффективно использовать язык, на котором вы пишите, уже нужно иметь хотя бы поверхностные знания о структурах данных, что они из себя представляют, и как могут повлиять на исполнение вашей программы.

А как же библиотеки? Ведь они решают столько задач! Чтобы рационально использовать библиотеки, их тоже нужно понимать. Во-первых, функции в библиотеки могут иметь побочные эффекты или поведение, которые вы не будете знать без понимания алгоритмов. Получив баг в таком случае можно долго и упорно пытаться его поймать и решить, когда можно было избежать. Во-вторых, различные инструменты и библиотеки часто нужно «настраивать» - говорить им какие алгоритмы, структуры данных и технологии использовать внутри. Без элементарных знаний вам придётся либо идти читать маны, либо выбирать наугад. В-третьих – есть множество задач, которые нельзя решить простым вызовом API библиотеки или фреймворка. Что вы будете делать в таком случае? Тратить часы на поиски возможных решений и просить помощи у друга? В-четвёртых – множество задач решается очень просто несколькими строчками кода или встроенными средствами языка. Если для решения каждого чиха вы будете тянуть библиотеку, то ваши программы будут гигантскими монстрами, занимая по сотни мегабайт и больше на диске, отжирая всю память на сервере, и при том имея довольно скудный функционал. Кроме того, наличие кучи подключенных библиотек влечёт за собой проблемы совместимости, и программа может падать случайным образом из-за странного поведения нескольких библиотек в одном проекте. Бездумное использование библиотек может привести к довольно плачевным последствиям, и разработчики, которые умеют только использовать библиотеки, но не способны решить даже простую проблему самостоятельно, никогда не будут ценится, потому что их решения будут неконкурентоспособны.

Со мной работал один программист со стажем больше десяти лет. Однажды нам понадобилась функция, которую использованная нами библиотека на тот момент не поддерживала: примитивный text-wrap в одном из визуальных компонентов. Этот «программист» посмотрел, что стандартными средствами это сделать нельзя, и сразу заявил, что реализация такой функции невозможна. Задачу решил интерн-третьекурсник с аналитическим мозгом, который за два часа написал простой алгоритм и внедрил его в нужный компонент. Другой проект в виде сайта на.net мне достался по наследству. Главная страничка представляла собой несколько маленьких графиков, и загружалась почти 10 секунд. Оказалось, что человек, который изначально делал этот проект, нагородил кучу ужасных конструкций из тройных вложенных циклов, которые долго и печально забирали данные из БД, и потом привязывали их к графикам. После небольшого рефакторинга страница стала грузится почти мгновенно.

Может ли программист обойтись без знаний алгоритмов и теории анализа? Может, и таких «программистов» очень много. Только назвать их программистами можно разве что с большой натяжкой. Ко мне на собеседование приходит очень много программистов, со стажем десять-пятнадцать лет, и толком не понимающих что же они делают и почему. У них своя ниша, они ходят от компании к компании, не задерживаясь в них больше года. Как правило, у них есть небольшой набор задач, которые они могут решать, и если сделать шаг в сторону, то человек теряется и ему нужно обучить себя новым навыкам. Таких людей приглашают на проект, и от них избавляются как можно быстрее, потому что они теряют кучу времени, изобретая велосипеды и читая маны чтобы узнать то, что уже должны были знать из университета. У них как правило нет особо никакой карьеры и нестабильный заработок.

В итоге, для чего нужно знать алгоритмы и теорию анализа, если можно выполнять работу и без этих знаний? Чтобы быть квалифицированным специалистом в своей профессии, иметь карьерный рост и уважение коллег. Чтобы эффективно решать поставленные задачи и не изобретать велосипедов. Чтобы не писать монстров с огромным количеством сторонних библиотек, которые занимают сотни мегабайт на диске от отжирают кучу памяти на сервере и регулярно падают по случайной причине в зависимости от фазы луны. Чтобы эффективно и с максимальными возможностями использовать язык, на которым вы пишете. Чтобы принимать информированные и осмысленные решения по выбору библиотеки и технологии для решения проблемы. Если же ваша работа заключается в написание SQL запроса и вбивание команды в консоль, то хочу вас огорчить: вы не программист, вы – пользователь, вам действительно не нужны алгоритмы и иже с ним, и вы зря потратили время в университете потому что для такой работы достаточно закончить курсы или прочитать пару вводных книжек самостоятельно.

Часто появляются статьи вида «нужны ли программисту алгоритмы», и все они имеют примерно одинаковый шаблон. Автор статьи как правило пишет: «Я N лет пишу сайты/скрипты в 1С, и никогда не пользовался алгоритмами или структурами данных. Тут же приводятся в пример красно-чёрные деревья или какие-нибудь другие экзотические структуры, которые в области, в которой работает автор не часто увидишь, если увидишь вообще. Такие статьи сводятся к тому, что в конкретной области программисты не используют сложные структуры данных и не решают NP задач.

Сама постановка такого вопроса в корне не верна. Количество специальностей в индустрии растёт постоянно, и человек, который пишет сайты на.net будет заниматься совсем другими вещами, нежели человек, пишущий драйвера для сенсоров на ARM архитектуре под экзотической ОС. Давайте прежде всего определим, что же такое алгоритм. Неформально Кормен определяет алгоритм как строго определённую процедуру, которая принимает одно или несколько значений как ввод, и возвращает одно или несколько значений как результат. Формально алгоритм определяется в разных моделях вычислений: операции, которые можно выполнить на машине Тьюринга или с помощью лямбда-исчислений. Таким образом фактически любой код, который что-то делает, является алгоритмом. Получается, что вопрос «нужны ли программисту алгоритмы» можно перевести как «нужно ли программисту уметь писать код». Правильно такой вопрос должен звучать что-то вроде: «нужно ли программисту в отрасли Х знать продвинутые алгоритмы и детали теории вычислений».

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

Давайте подумаем, что же нужно учить программисту в университете, для того чтобы приобрести необходимые навыки для успешной карьеры. Библиотеки? Фреймворки? Они устаревают, интерфейсы к ним меняются, все они написаны чаще всего под один язык, который студенты могут и не использовать никогда в индустрии. Всех учить писать сайты? Или всех учить писать ОС? Образование должно охватывать как можно большую аудиторию и давать максимально возможный набор навыков. Программист в первую очередь должен уметь анализировать и решать проблемы – это основной навык, которым должны обзавестись выпускники факультетов информатики. Написание кода – это просто необходимый инструмент, который используется для решения задач. Кто может знать какие навыки вам понадобятся в будущем? Таким образом учить теорию – это наиболее оптимально с точки зрения образования. Полученные навыки можно применить в любой области, а выучить библиотеку или фреймворк имея хорошую базу знаний не составит большого труда. Парадоксально то, что люди задающие вопросы про нужность алгоритмов, как правило имеют какие-то знания в этой области. Я не помню ни одного человека, который не имел знаний в области теории вычислений, и с гордостью кричал об этом, утверждая, что ему они не нужны.

Итак, вы абстрактный программист в вакууме, работаете десять с лишним лет клепая сайты и решая простые однотипные задачи клиентов/компании. Вам хорошо и уютно в вашей нише, и только мучительно больно за бесцельно потраченное время в классе по теории вычислений и алгоритмическому анализу, который вам ничего не дал. По утрам закуривая сигарету за чашкой кофе, в глубине философских размышлений о бренности бытия вы задумываетесь: зачем же программистам, не решающим сложных задач, знать алгоритмы и основы анализа. Короткий ответ: чтобы быть квалифицированным специалистом и эффективно использовать доступные инструменты, включая язык, на котором вы пишите. Теория алгоритмов и анализа учит не только экзотические алгоритмы и структуры данных в виде АВЛ и красно-чёрных деревьев. Она также даёт представления о том, как эффективно организовать данные, как писать код с максимальной производительностью, где в системе возможно бутылочное горлышко и как с ним бороться. Вас ознакамливают с готовыми решениями, чтобы вы не писали велосипедов, и не бежали в гугл каждый раз, когда нужно сделать что-то нетривиальное.

Знания теории анализа и алгоритмов применяются всеми программистами на самом деле каждый день, просто мы привыкли к этим вещам настолько, что даже не задумываемся над этим. Какую бы задачу вы не решали – будь то простой сайт с выборкой данных из БД, или баш скрипт на сервере, вы будете использовать какие-то структуры данных. Как минимум примитивный массив, а скорее всего и что-то посложнее. Языки дают нам множество различных структур, многие из которых взаимозаменяемы. Часто мы имеем несколько вариаций одного абстрактного типа с разными реализациями. Например, в С++ есть структуры данных vector и list. Чем они отличаются, и какие будут преимущества и недостатки использования одного или другого? Как в С++ реализована map, и чем она отличается от multimap? Как реализован list в Python – через массив или связным списком и как лучше всего с ним работать? Почему в C# нежелательно использовать ArrayList, а вместо него использовать List? Как реализован SortedDictionary и как он повлияет на исполнение программы если будет использован вместо Dictionary? Как работает continuation, когда её нужно использовать, и будут ли какие-то побочные эффекты при её использовании? Когда вы в последний раз использовали каррированные функции, которые есть почти в каждом языке? Если вы думаете, что map в С++ реализована как хэш-таблица, вы ошибаетесь. Она реализована на красно-чёрных деревьях, а хэш-таблицей реализована unordered_map. Отдельно стоит упомянуть динамическое программирование. Понимание что это такое, как можно оптимально переписать рекурсивные функции и что такое мемоизация, часто поможет избежать выстрела себе в ногу. Таким образом просто чтобы полноценно и эффективно использовать язык, на котором вы пишите, уже нужно иметь хотя бы поверхностные знания о структурах данных, что они из себя представляют, и как могут повлиять на исполнение вашей программы.

А как же библиотеки? Ведь они решают столько задач! Чтобы рационально использовать библиотеки, их тоже нужно понимать. Во-первых, функции в библиотеки могут иметь побочные эффекты или поведение, которые вы не будете знать без понимания алгоритмов. Получив баг в таком случае можно долго и упорно пытаться его поймать и решить, когда можно было избежать. Во-вторых, различные инструменты и библиотеки часто нужно «настраивать» - говорить им какие алгоритмы, структуры данных и технологии использовать внутри. Без элементарных знаний вам придётся либо идти читать маны, либо выбирать наугад. В-третьих – есть множество задач, которые нельзя решить простым вызовом API библиотеки или фреймворка. Что вы будете делать в таком случае? Тратить часы на поиски возможных решений и просить помощи у друга? В-четвёртых – множество задач решается очень просто несколькими строчками кода или встроенными средствами языка. Если для решения каждого чиха вы будете тянуть библиотеку, то ваши программы будут гигантскими монстрами, занимая по сотни мегабайт и больше на диске, отжирая всю память на сервере, и при том имея довольно скудный функционал. Кроме того, наличие кучи подключенных библиотек влечёт за собой проблемы совместимости, и программа может падать случайным образом из-за странного поведения нескольких библиотек в одном проекте. Бездумное использование библиотек может привести к довольно плачевным последствиям, и разработчики, которые умеют только использовать библиотеки, но не способны решить даже простую проблему самостоятельно, никогда не будут ценится, потому что их решения будут неконкурентоспособны.

Со мной работал один программист со стажем больше десяти лет. Однажды нам понадобилась функция, которую использованная нами библиотека на тот момент не поддерживала: примитивный text-wrap в одном из визуальных компонентов. Этот «программист» посмотрел, что стандартными средствами это сделать нельзя, и сразу заявил, что реализация такой функции невозможна. Задачу решил интерн-третьекурсник с аналитическим мозгом, который за два часа написал простой алгоритм и внедрил его в нужный компонент. Другой проект в виде сайта на.net мне достался по наследству. Главная страничка представляла собой несколько маленьких графиков, и загружалась почти 10 секунд. Оказалось, что человек, который изначально делал этот проект, нагородил кучу ужасных конструкций из тройных вложенных циклов, которые долго и печально забирали данные из БД, и потом привязывали их к графикам. После небольшого рефакторинга страница стала грузится почти мгновенно.

Может ли программист обойтись без знаний алгоритмов и теории анализа? Может, и таких «программистов» очень много. Только назвать их программистами можно разве что с большой натяжкой. Ко мне на собеседование приходит очень много программистов, со стажем десять-пятнадцать лет, и толком не понимающих что же они делают и почему. У них своя ниша, они ходят от компании к компании, не задерживаясь в них больше года. Как правило, у них есть небольшой набор задач, которые они могут решать, и если сделать шаг в сторону, то человек теряется и ему нужно обучить себя новым навыкам. Таких людей приглашают на проект, и от них избавляются как можно быстрее, потому что они теряют кучу времени, изобретая велосипеды и читая маны чтобы узнать то, что уже должны были знать из университета. У них как правило нет особо никакой карьеры и нестабильный заработок.

В итоге, для чего нужно знать алгоритмы и теорию анализа, если можно выполнять работу и без этих знаний? Чтобы быть квалифицированным специалистом в своей профессии, иметь карьерный рост и уважение коллег. Чтобы эффективно решать поставленные задачи и не изобретать велосипедов. Чтобы не писать монстров с огромным количеством сторонних библиотек, которые занимают сотни мегабайт на диске от отжирают кучу памяти на сервере и регулярно падают по случайной причине в зависимости от фазы луны. Чтобы эффективно и с максимальными возможностями использовать язык, на которым вы пишете. Чтобы принимать информированные и осмысленные решения по выбору библиотеки и технологии для решения проблемы. Если же ваша работа заключается в написание SQL запроса и вбивание команды в консоль, то хочу вас огорчить: вы не программист, вы – пользователь, вам действительно не нужны алгоритмы и иже с ним, и вы зря потратили время в университете потому что для такой работы достаточно закончить курсы или прочитать пару вводных книжек самостоятельно.

2.4.1. Понятие базовых алгоритмов

2.4.2. Алгоритмы линейной структуры

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

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

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

2.4.6. Базовые алгоритмы обработки одномерных массивов

2.4.7. Базовые алгоритмы обработки двумерных массивов

2.4.8. Контрольные вопросы по теме «Базовые алгоритмы и примеры их реализации»

2.4.9. Тестовые задания по теме «Базовые алгоритмы и примеры их реализации»

2.4.1. Понятие базовых алгоритмов

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

К базовым алгоритмам императивного программирования можно отнести:

    Простейшие алгоритмы, реализующие базовые алгоритмические структуры.

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

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

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

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

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

2.4.2. Алгоритмы линейной структуры

Пример 2.4.2-1.

где x = -1,4; y = 0,8;переменныеkиm– целого типа, остальные переменные - вещественного типа;[n]- целая часть числаn.

Схема алгоритма и программы на языках QBasic, Pascal, C++ , представлены на рис. 2.4.2-1.

Следует обратить внимание на то, что целая переменная k получила округленное значениеn , а целая переменнаяm - усе­ченное с помощью функцииFIX() до целой части значенияn.

Пример 2.4.2-2 . Вычислить и вывести на экран значения следующих величин:

где x = 2.9512; y = 0.098633;переменныеiиj– целого типа; остальные переменные – вещественного типа.

Схема алгоритма и коды программ представлены на рис. 3.2.1-2.

Рис. 2.4.2-2.

Результаты выполнения программы при указанных выше значе­ниях исходных данных имеют следующий вид:

Пример 2.4.2-3. Вычислить и вывести на экран значение первой космической скорости.

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

где – гравитационная постоянная; M – масса Земли;
– расстояние от центра Земли до космического аппарата.

Схема алгоритма и коды программ представлены на рис. 3.2.1-3.

Рис. 2.4.2-3.

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

Да, хорошая алгоритмическая подготовка важна для программиста. И нет, хорошая - это вовсе не заучивание алгоритмов из списка “Самых Важных Алгоритмов, Которые Должен Знать Каждый”. На мой взгляд хорошая алгоритмическая подготовка должна стремиться дать программисту следующие три умения.

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

Очевидно, для этого недостаточно просто знать алгоритмы. Нужно уметь “видеть их”, распознавать возможности их применения.

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

В-третьих, алгоритмическая подготовка должна помогать умело пользоваться готовыми инструментами. Базы данных - это сплошные структуры данных и алгоритмы. Причем на концептуальном уровне довольно простые и понятные - деревья поиска, хэштаблицы, SS-Table, …

Например, зная, что индекс в БД - это просто дерево поиска, несложно понять, какие запросы могут быть выполнены быстро, а какие обречены на full-scan.
Зная, как на каких алгоритмах работает полнотекстовый поиск в Lucene, можно предсказать, какие запросы к Elastic будут давать релевантные ответы, а какие - нет, и даже как это можно доработать.

Если подводить итог:

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