Какие алгоритмы должен знать уважающий себя программист? Базовые структуры программирования (виды алгоритма) Какие алгоритмы должен знать программист

Понятие алгоритма относится к основным понятиям информатики. Рассмотрим основные понятия, связанные с понятием алгоритма.

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

Исполнитель - человек или автомат (например, компьютер), который умеет выполнять определенный конечный набор действий.

Предписание - приказ на выполнение действий из указанного конечного набора.

Система предписаний - совокупность допустимых приказов.

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

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

Программирование - составление последовательности команд, которая необходима для решения поставленной задачи.

Составлению программы предшествует разработка алгоритма.

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

Любой алгоритм обладает следующими свойствами:

• 1. Дискретность. Выполнение алгоритма разбивается на последовательность элементарных действий - шагов. Каждое действие должно быть закончено исполнителем прежде, чем он перейдет к выполнению следующего действия. Произвести каждое отдельное действие исполнителю предписывает специальное указание в записи алгоритма, называемое командой.
• 2. Точность или детерминированность. Запись алгоритма должна быть такой, чтобы, выполнив очередную команду, исполнитель точно знал, какую команду надо выполнять следующей.
• 3. Понятность. Каждый алгоритм строится в расчете на конкретного исполнителя, который должен быть в состоянии выполнить каждую команду алгоритма в строгом соответствии с ее назначением.
• 4. Результативность. При точном исполнении всех предписаний алгоритма процесс должен завершится за конечное число шагов и при этом должен быть получен какой-либо ответ на поставленную задачу. В качестве одного из возможных решений может быть установление того факта, что задача не имеет решения
• 5. Массовость. помощью одного и того же алгоритма можно решать однотипные задачи и делать это неоднократно. Свойство массовости значительно увеличивает практическую ценность алгоритмов.

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

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

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

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

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

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

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

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

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

Представляет собой последовательное выполнение действий (рис. 12).

Рис. 12.

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

Рис. 13.

Действия 1 и 2 могут, в свою очередь, включать в себя другие алгоритмические структуры.

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

Применяется, когда некоторые операции надо повторять до тех пор, пока некоторое условие не станет ложным (рис. 14).

Рис. 14. Цикл До.

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

Применяется, когда некоторые операции надо повторять до тех пор, пока некоторое условие не станет истинным (рис. 15).

Рис. 15. Цикл Пока.

Часто появляются статьи вида «нужны ли программисту алгоритмы», и все они имеют примерно одинаковый шаблон. Автор статьи как правило пишет: «Я 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 запроса и вбивание команды в консоль, то хочу вас огорчить: вы не программист, вы – пользователь, вам действительно не нужны алгоритмы и иже с ним, и вы зря потратили время в университете потому что для такой работы достаточно закончить курсы или прочитать пару вводных книжек самостоятельно.

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

Мотивирующее изображение:

Проблема

Обычно в разработчики переходят новоиспеченные специалисты до 30-ти лет. И сразу же возникает несколько серьезных проблем:

• 5-6 лет потерянных на изучение предметов и наук, которые больше никогда не понадобятся;
• Необходимая смена мышления с гуманитарного\технического на логическое\цифровое;
• Освоение 5-6 лет программы технического вуза в кратчайшие сроки;
• Создание угрозы жизни и благополучия людей, компаний, бизнеса...

Время

Спрашивается, зачем человек изучал несколько лет не нужные ему науки? Зачем подвергал себя таким умственным нагрузкам? Чтобы потом все бросить и начать все с начала? Даже 5 лет это много. За это время можно стать миллиардером или же получить Нобелевскую премию, так нет, человек изучает то что ему не интересно, спит на парах и говорит, что философия - это полнейший бред!

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

Там же все просто!

Сколько таких новоявленных «программистов», прочитавших о JAVA у Брюса Эккеля. Все они считают себя гениями программирования, а ООП, MVC, Agile, двоичная система исчисления, теория сложности вычислений… не для них.

Приведу несколько жизненных примеров:

1. «Программист» пишет вторую версию программы. В первой - была одна форма на 50 кнопок. Вторая версия обладает большей функциональностью, но ее логика не так прозрачна. Планируется писать программу пару месяцев. В функционал заложено порядка 100 кнопок на одной форме. После 10-и минутного введения в теорию графов количество кнопок сократилось до одной (удаление точки), срок написания программы сократился до двух дней.
2. «Программисту» дали задание написать программу-конвертер. Логика простая: приходит пакет вида ключ=значение, надо по специальной таблице конвертировать его в пакет2 вида ключ2=значение2 и отправить дальше. После двух месяцев «изучения платформы» ему был передан каркас приложения (прием пакета, трансформация, отправка пакетов) старшими товарищами. Через месяц конвертер был готов!
3. Множество реализованных велосипедов;
4. Говорящий за себя http://govnokod.ru ;

Могу сказать только одно: если бы программирование было таким простым, то ему бы не учили в университетах по пять лет. Достаточно было бы и трехмесячных курсов .

Таланты

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

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

Запах пороха

Очень хорошая идея показать, что представляет собой разработка. Понюхать пороха, так сказать! Вот уже и мэры начали изучать JS .

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

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

Заключение

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

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

Как показывают исследования . IT в России - не самая высокооплачиваемая отрасль. Она занимает лишь третье место. На втором месте сырьевые отрасли, а на первом - высший менеджмент . Из-за специфики IT, программист никогда не достигнет ступеньки высшего менеджмента. Максимум, на что стоит рассчитывать, это должность руководителя отдела, ведущего направления, директора собственной компании.

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

P.S. В комментариях спрашивают про цели заметки: серьезнее относиться в выбору профессии, заниматься только любимым делом, учиться тому что нравится, профессионально расти, а не пробовать все понемногу без определенной цели. Удивляют люди, которые в 30-40 лет так и не смогли найти себе занятие по душе.

Первый шаг к пониманию важности изучения и знания алгоритмов это дать точное определение тому, что понимается под алгоритмом. Согласно популярной книге Алгоритмы: построение и анализ (Кормен, Лейзерсон, Ривест, Штайн) «алгоритм (algorithm) - это любая корректно определенная вычислительная процедура, на вход (input) которой подается некоторая величина или набор величин, и результатом выполнения которой является выходная (output) величина или набор значений». Другими словами, алгоритмы похожи на дорожные карты для достижения четко определенной задачи. Кусок кода, для вычисления членов последовательности Фибоначчи - это реализация конкретного алгоритма. Даже простая функция сложения двух чисел является алгоритмом, хотя и простым.

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

Анализ времени выполнения алгоритма

Одним из наиболее важных аспектов алгоритма является его скорость. Часто бывает легко придумать алгоритм решающий задачу, но если алгоритм слишком медленный, то он возвращается на доработку. Поскольку точная скорость алгоритма зависит от того где запускается алгоритм, а также деталей реализации, компьютерные специалисты обычно говорят о времени выполнения относительно входных данных. Например, если вход состоит из N целых чисел, то алгоритм может иметь время выполнения пропорциональное N 2 , что представляется как O(N 2). Это означает, что если вы запустите реализацию алгоритма на компьютере с входом размером в N, то это займет C*N 2 секунд, где C-некоторая константа, которая не меняется с изменением размера входа.

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

Сортировка

Сортировка является хорошим примером алгоритма, который часто используется программистами. Самый простой способ отсортировать группу элементов это начать с удаления наименьшего элемента из группы, и поставить его первым. Затем удаляется второй по величине элемент и ставится вторым и т.д. К сожалению, время работы этого алгоритма составляет O(N 2), а это означает, что потребуется количество времени пропорциональное количеству элементов в квадрате. Если бы нам пришлось сортировать млрд. элементов, то этот алгоритмы бы потребовал 10 18 операций. Если считать что обычные настольные ПК делают примерно 10 9 операций в секунду, то потребуются годы чтобы закончить сортировку этого млрд. элементов.

К счастью существует ряд более совершенных алгоритмов, например, быстрая сортировка (quicksort), пирамидальная сортировка (heapsort) и сортировка слиянием (mergesort). Эти алгоритмы имеют время выполнения O(N * Log(N)). Таким образом, число операций необходимых для сортировки млрд. элементов сокращается до таких разумных пределов, что даже самый дешевый настольный ПК способен провести такую сортировку. Вместо млрд. в квадрате операций (10 18) эти алгоритмы требуют только 10 млрд. операций (10 10), т.е. на 100 млн. быстрее.

Кратчайший путь

Алгоритмы поиска кратчайшего пути из одной точки в другую исследуются уже на протяжении многих лет. Примеров прикладного применения этих алгоритмов предостаточно, однако для простоты изложения будем придерживаться следующей постановки: требуется найти кратчайший путь из точки А в точку Б в городе с несколькими улицами и перекрестками. Существует много разных алгоритмов для решения этой задачи и все они со своими преимуществами и недостатками. Прежде чем мы углубимся в их изучение, давайте рассмотрим время выполнения простого алгоритма перебором. Если алгоритм рассматривает каждый возможный путь от А до Б (который не образует циклов) он вряд ли закончится при нашей жизни, даже если А и Б находятся в маленьком городке. Время выполнения этого алгоритма является экспоненциальным, что обозначается как O(C N) для некоторого C. Даже для малых значений C, C N становится астрономическим числом, когда N принимает умеренно большое значение.

Один из самых быстрых алгоритмов для решения этой задачи имеет время выполнения O(E*V*Log(V)), где E число дорожных сегментов, а V число пересечений. Алгоритм займет около 2 секунд времени, для поиска кратчайшего пути в городе из 10000 пересечений и 20000 дорожных сегментов (обычно бывает около 2 дорожных сегментов на одно пересечение). Этот алгоритм известен как алгоритм Дейкстры , он является довольно таки сложным и требует использования структуры данных очередь с приоритетом (priority queue). Однако в некоторых случаях даже такое время выполнения является слишком медленным (взять например нахождение кратчайшего пути от Нью-Йорка до Сан-Франциско - в США есть миллионы пересечений), в таких случаях программисты пытаются улучшить время выполнения с помощью так называемой эвристики. Эвристика - это приближенное значение чего-то, что имеет отношение к задаче. В задаче поиска кратчайшего пути, например, может оказаться полезным знать, как далеко находится точка от пункта назначения. Зная это можно разработать более быстрый алгоритм (например алгоритм поиска А* в некоторых случаях работает значительно быстрее чем алгоритм Дейкстры). Такой подход не всегда улучшает время выполнения алгоритма в наихудшем случае, но в большинстве реальных приложений алгоритм начинает работать быстрее.

Приближенные алгоритмы

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

На самом деле есть немало важных задач, для которых известные на сегодня алгоритмы выдают оптимальный результат слишком медленно. Наиболее известная группа из этих задач называется NP (non-deterministic polynomial) . Если задача называется NP-полной или NP-трудной, то это означает, что никто не знает достаточно хорошего способа для получения оптимального решения. Кроме того, если кто-то разработает эффективный алгоритм для решения одной NP-трудной задачи, то этот алгоритм можно будет применить ко всем NP-трудным задачам.

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

Случайные алгоритмы

Еще один подход, применяемый для решения некоторых задач, заключается в том, чтобы сделать алгоритм случайным. Данный подход не улучшает время алгоритма в худшем случае, но довольно часто хорошо работает в среднем случае. Алгоритм быстрой сортировки является хорошим примером использования рандомизации. В худшем случае, алгоритм быстрой сортировки сортирует группу элементов за O(N 2), где N количество элементов. Если в этом алгоритме использовать рандомизацию, то шансы на худший случай становятся незначительно малыми, и в среднем случае алгоритм быстрой сортировки работает за время O(N*Log(N)). Другие алгоритмы даже в худшем случае гарантируют время работы O(N*Log(N)), однако они медленнее в среднем случае. Хотя оба алгоритма имеют время работы пропорциональное N*Log(N), алгоритм быстрой сортировки имеет более меньший постоянный коэффициент (constant factor) - т.е. он требует C*N*Log(N), в то время как другие алгоритмы требуют более 2*C*N*Log(N) операций.

Другой алгоритм, использующий случайные числа ищет медиану для группы чисел и его время работы в среднем случае составляет O(N). Это намного быстрее по сравнению с алгоритмом, который сортирует числа и выбирает среднее, и работает за O(N*Log(N)). Существуют детерминированные алгоритмы (не случайные) которые позволяют найти медиану за время O(N), однако случайный алгоритм проще для понимания и часто работает быстрее этих детерминированных алгоритмов.

Основная идея алгоритма поиска медианы это выбрать среди чисел случайное, и посчитать, сколько чисел в группе меньше чем выбранное число. Допустим, есть N чисел, K из них меньше или равно выбранному числу. Если K меньше чем половина N, тогда мы знаем что медиана это (N/2-K)-е число которое больше чем случайно выбранное число, так что мы отбрасываем K чисел меньших или равных случайному числу. Теперь допустим мы хотим найти (N/2-K)-е наименьшее число, вместо медианы. Алгоритм такой же, мы просто случайно выбираем число и повторяем описанные шаги.

Сжатие

Еще один класс алгоритмов предназначен для сжатия данных. Этот алгоритм не имеет ожидаемого результата (как например, алгоритм сортировки), но вместо этого делается оптимизация по некоторым критериям. В случае сжатия данных, алгоритм (например, LZW) пытается сделать так чтобы данные занимали как можно меньше байтов, но в то же время, чтобы можно было распаковывать их до первоначальной формы. В некоторых случаях этот тип алгоритмов использует те же методы что и другие алгоритмы, что приводит к хорошему результату, но неоптимальному. Например, JPG и MP3 сжимают данные таким образом, что конечный результат получается более низкого качества, чем оригинал, однако и размер меньше. MP3 сжатие не сохраняет каждую особенность оригинального аудио файла, но пытается сохранить достаточно деталей, чтобы обеспечить приемлемое качество и в то же время значительно сократить размер файла. Формат JPG следует тому же принципу, но детали существенно отличаются, т.к. целью является сжатие изображения, а не аудио.

Почему так важно знать алгоритмы

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

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

В качестве примера можно рассмотреть, как работают сетевые коммутаторы. Коммутатор имеет N подключенных к нему кабелей, и принимает пакет данных, поступающих по этим кабелям. Коммутатор должен сначала проанализировать пакеты, а затем отправить их обратно по правильному кабелю. Коммутатор также как и компьютер работает в дискретном режиме - пакеты отправляются дискретными интервалами, а не непрерывно. Быстрый коммутатор стремится послать, как можно больше пакетов в течение каждого интервала иначе они накопятся и коммутатор «упадет». Цель алгоритма отправлять максимальное количество пакетов в течение каждого интервала, а также обеспечить порядок, при котором пакеты, пришедшие раньше других отправлялись тоже раньше других. В этом случае оказывается, что для решения этой задачи подходит алгоритм известный как «stable matching», хотя на первый взгляд это может быть не очевидно. Такие связи между задачей и решением можно обнаружить только с помощью уже имеющихся алгоритмических знаний.

Реальные примеры

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

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

Бураков П.В., Косовцева Т.Р. Информатика. Алгоритмы и программирование. Учебное пособие.-СПб НИУ ИТМО, 2013. – 83с.

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

В 2009 году Университет стал победителем многоэтапного конкурса, в результате которого определены 12 ведущих университетов России, которым присвоена категория «Национальный исследовательский университет». Министерством образования и науки Российской Федерации была утверждена Программа развития государственного образовательного учреждения высшего профессионального образования «Санкт-Петербургский государственный университет информационных технологий, механики и оптики» на 2009– 2018 годы.

© Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики, 2013 ©П.В. Бураков, Т.Р.Косовцева

Постановка задачи.........................................................................................................................
Разработка математической модели............................................................................................
Выбор метода численного решения.............................................................................................
Разработка алгоритма и структуры данных................................................................................
Реализация алгоритма в виде программы...................................................................................
Отладка и тестирование программы............................................................................................
Решение задачи на компьютере...................................................................................................
ПОСТРОЕНИЕ АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ.............................................................................
Описание алгоритма......................................................................................................................
Схема алгоритма..........................................................................................................................
Структурированные схемы алгоритмов....................................................................................
СРЕДСТВА РЕАЛИЗАЦИИ АЛГОРИТМА..........................................................................................
Критерии выбора языка программирования.............................................................................
СТРУКТУРА ПРОГРАММЫ И ЕЕ ЭЛЕМЕНТЫ.................................................................................
Основные элементы программирования...................................................................................
Алфавит и словарь языка TurboPascal (TPascal).......................................................................
Структура программы.................................................................................................................
ТИПЫ ДАННЫХ......................................................................................................................................
Скалярные типы данных.............................................................................................................
Структурированные типы данных.............................................................................................
ВВОД-ВЫВОД ДАННЫХ.......................................................................................................................
Процедуры ввода-вывода...........................................................................................................
ОПЕРАТОРЫ............................................................................................................................................
Общие сведения...........................................................................................................................
Простые операторы.....................................................................................................................
Структурные операторы.............................................................................................................
Условные операторы...................................................................................................................
Операторы цикла.........................................................................................................................
МАССИВЫ................................................................................................................................................
Действия над массивами.............................................................................................................
Действия над элементами массива............................................................................................
Операции с матрицами................................................................................................................
ПРОЦЕДУРЫ И ФУНКЦИИ...................................................................................................................
Необходимость структуризации в программировании............................................................
Подпрограммы в языке ТPascal..................................................................................................
Процедуры....................................................................................................................................
Функции.......................................................................................................................................
Механизм передачи параметров................................................................................................
ФАЙЛЫ.....................................................................................................................................................
Общие сведения...........................................................................................................................
Описания файлового типа..........................................................................................................
Средства обработки файлов.......................................................................................................
Текстовые файлы.........................................................................................................................

ЛАБОРАТОРНЫЙ ПРАКТИКУМ..........................................................................................................
Лабораторная работа 1.		Программирование линейных и	разветвляющихся
вычислительных процессов.............................................................................................................
Лабораторная работа № 2.	Циклические вычислительные процессы...................................
Лабораторная работа № 3.		Операции с массивами.................................................................
Лабораторная работа № 4.	Операции с файлами.....................................................................
Лабораторная работа 5. Процедуры и функции......................................................................
БИБЛИОГРАФИЧЕСКИЙ СПИСОК.....................................................................................................

ЭЛЕМЕНТЫ ТЕХНОЛОГИИ РЕШЕНИЯ ПРАКТИЧЕСКИХ ЗАДАЧ НА КОМПЬЮТЕРЕ

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

1. Постановка задачи.

2. Разработка математической модели.

3. Выбор метода численного решения для расчетных задач.

4. Разработка алгоритма решения и структуры данных.

5. Реализация алгоритма в виде программы.

6. Отладка и тестирование программы.

7. Решение задачи на компьютере, численные эксперименты и анализ результатов.

Постановка задачи

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

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

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

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

Разработка математической модели

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

Математической моделью задачи, сформулированной в примере 1 является формула: S = 0,5 a t 2 , где в качестве основной переменной выступает время t , параметром движения является ускорение а . Формула показывает зависимость между длиной пути и временем в соответствии с законом механики.

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

S = ∫ V (t) dt ,

при этом закон изменения скорости V(t) в зависимости от времени может быть достаточно сложным и определить значение интеграла аналитически не удается. Поэтому в большинстве случаев практически целесообразно использовать приближенные методы решения.

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

Выбор метода численного решения

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

∫ f (x ) dx ≈ ∆ x ∑ f (x i ) , где ∆х - шаг интегрирования (const), ∆х=(b-a)/n,

x i+1 =xi +∆ х, x1 =a , xn+1 =b

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

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

Разработка алгоритма и структуры данных

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

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

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

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

Реализация алгоритма в виде программы

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

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

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

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

Отладка и тестирование программы

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

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

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

Решение задачи на компьютере

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

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

Контрольные вопросы

1. Какие факторы влияют на эффективность решения задач на компьютере?

2. Перечислите этапы решения задач на компьютере.

3. Каковы основные требования к математической модели задачи?

4. Назовите главные характеристики алгоритмов.

5. Какие особенности следует учитывать при разработке программ на компьютере?

6. Чем завершается разработка алгоритма?

ПОСТРОЕНИЕ АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ

Описание алгоритма

Под алгоритмом понимается конечная последовательность точно сформулированных правил решения некоторого касса задач. Алгоритм обладает следующими свойствами:

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

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

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

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

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

Правильность . Способность алгоритма давать правильные результаты решения поставленных задач.

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

Рассмотрим алгоритмы решения нескольких задач. Задача 1 . Составить алгоритм вычисления x по формуле

x = a (r − q ) 2 , где p ≠ -12.

p + 12

1. Начало;

2. Вычислить b:= p + 12;

3. Вычислить c:= r – q;

4. Вычислить d:= c c;

5. Вычислить e:= a d;

6. Вычислить x:= e / b;

7. Записать результат: x;

В записи алгоритма решения задачи 1 введены буквенные обозначения

– переменные. Так, через b обозначено p + 12 , через c – разность r – q. Запись

b:= p+12 означает, что вначале должна быть найдена сумма p + 12 при определенных значениях p, а затем это значение присваивается переменной b.

Придавая a, p, q, r разные значения, будем получать различные задания на вычисление x . Поэтому алгоритм обычно позволяет решать не одну, а целый класс задач. Такую особенность алгоритма называют массовостью алгоритма. Возможны алгоритмы, решающие только единственную задачу.

Величины a, p, q, r, 12 составляют исходные данные для алгоритма, 12

– постоянную составляющую, a, p, q, r – переменную составляющую информации. Величины b, c, d, e являются вспомогательными переменными, x – результат исполнения алгоритма.

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

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

Задача 2 . По формуле

x = − b ± b 2 − 4 ac составить алгоритм решения квадратного уравнения

ax2 + bx + c = 0 (a ≠ 0).

1. Начало;

2. p:= 2a;

3. D:= b 2 – 4ac;

4. Если D ≥ 0, то перейти к п. 5, иначе к п. 10;

5. d:= D ;

6. x 1 : = − b − d ; p

7. x 2 : = − b + d ; p

8. Записать результат: x 1 , x2 ;

9. Перейти к п. 11;

10. Записать результат: уравнение действительных корней не имеет;

11. Конец.

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

Команды, определяющие порядок исполнения операций, подразделяются на два типа: команды условного перехода и команды безусловного перехода . К командам условного перехода относится, например, правило 4 алгоритма решения задачи 2 . Правило 9 содержит безусловный переход.

В командах условного перехода обязательно присутствует логическое условие типа: если α ◊ β , то …(где ◊ - один из операторов > , ≥ , < , ≤ , = , ≠ ).

Схема алгоритма

Схема алгоритма представляет собой графическое изображение алгоритма с помощью определенным образом связанных между собой блоков. Каждый блок изображается определенной фигурой. Блоки в схеме соединяются дугами. Дуги указывают порядок следования блоков при исполнении алгоритма. Типы блоков представлены на рисунке 1.

Рис.1 . Типы блоков

Прямоугольник вместе с заключенным в нем этапом вычисления S называют функциональным блоком , или процессом (рис.1, а). Ромб с заключенным в нем условием P называют блоком проверки условия , или решением (рис.1, б). Он используется для управления порядком исполнения блоков в схеме алгоритма. Из функционального блока выходит одна стрелка, а из блока проверки условия – две. Последнее объясняется тем, что в результате исполнения команды проверки условия получаем либо выполнение (да), либо невыполнение (нет) заданного условия P. Информационный блок (рис.1, в) используется для ввода и вывода А. Блоки (рис.1, г) и (рис.1, д) называют соответственно начальным и конечным . Блок-схема решения задачи начинается в начальном блоке и заканчивается в конечном.

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

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

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

На рисунках 2 и 3 изображены схемы алгоритмов решения задачи нахождения суммы n - чисел: a1 , a2 , a3 , a4 ,.., an .