Файл: Алгоритмизация как основной этап разработки программ (подробно).pdf

Введение

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

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

Компьютеры невероятно быстры в манипулировании данными. Однако объем данных, используемых компьютерами, часто настолько велик, что не имеет значения, насколько быстрым является компьютер, потребуется слишком много времени, чтобы изучить каждый фрагмент данных (такие компании, как Google, Facebook и Twitter, регулярно обрабатывают миллиарды фрагментов данных в день, а в некоторых случаях, в минуту) Именно здесь в дело и вступают алгоритмы. Если компьютер использует лучший алгоритм для обработки данных, то не имеет значения, сколько информации он должен просматривать, он все равно будет в состоянии сделать это в разумные сроки. Скорость приложения на компьютере имеет большое значение для человека, использующего его. Если создаваемое приложение слишком медленное, люди будут разочарованы этим и не будут его использовать [5.]. Таким образом, потребность в создании и развитии алгоритмов является актуальной.

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

---

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

Понятие алгоритма

Термин «алгоритм» первоначально относился к любым вычислениям, выполняемым с помощью набора правил, применяемых к числам, записанным в десятичной форме. Слово происходит от фонетического произношения фамилии Абу Джафара Мохаммеда ибн Мусы аль-Хорезми, арабского математика, который изобрел набор правил для выполнения четырех основных арифметических операций (сложение, вычитание, умножение и деление) над десятичными числами [3.].

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

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

---

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

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

Однако иногда необходим компромисс между другими факторами. Например, эффективность может быть принесена в жертву ради высокой степени надежности. Разработка алгоритмов для решения простых задач может быть простой, но разработка алгоритмов для больших и сложных задач может быть сложной и трудоемкой. Хотя этот пример может касаться только простых задач, используемые методы важны при разработке алгоритмов и для сложных задач. Один общий подход к большим и сложным проблемам – использовать нисходящий дизайн. Нисходящее проектирование начинается в верхней части структурной схемы с общей формулировкой задачи, написанной точным, формальным способом для обеспечения высокоуровневой спецификации алгоритма. Этот способ предполагает разделение на отдельные логические части, для решения которых предоставляется общая спецификация. Эти части соответствуют основным модулям в конечном алгоритме. Затем части подразделяются и составляются инструкции. Наконец, алгоритм достигает той стадии, когда общая спецификация состоит из вычислений, сравнений и доступа к данным, и может быть запрограммирован без дальнейшего объяснения [4.].

---

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

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

1. Ввести размеры трубопровода;
2. Проверить корректность введенных данных;
3. Рассчитать площадь поперечного сечения;
4. Рассчитать объем стали;
5. Рассчитать вес;
6. Вывести вес.

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

Понятие программы и данных

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

Вывод относится к данным, отправленным с процессора компьютера на автоматические устройства хранения данных или на внешнее устройство. Вывод может быть напечатан, отображен на экране компьютера, записан на накопитель, диск или дискету, нанесен на карту (визуализирован) на графическом устройстве или использован для управления автоматическим устройством. Внутренняя перестановка данных, во время которой значения копируются из одной ячейки памяти в другую, достигается главным образом с помощью инструкций присваивания, которые выглядят как простые уравнения. Например, инструкция языка Си a = b; не означает, что a и b – это одно и то же, а то, что a присваивается (назначается) то же значение, что и b. Фактически значение, содержащееся в ячейке памяти с именем b, копируется в ячейку памяти с именем a. После того как оператор выполнит оператор a = b, ячейка памяти a будет содержать то же значение, что и ячейка памяти b. Арифметические инструкции состоят из основных арифметических операций сложения, вычитания, умножения, деления, остатка и возведения в степень (возведения в степень), а также присваивания значения переменной. Таким образом, инструкция а = 2,5 + 6,5 / 3,25; означает, что значение 4,5 рассчитывается как значение, назначенное для переменной a. Арифметические выражения оцениваются компьютером с тем же приоритетом, что и в математике. В этом примере деление выполняется перед сложением. Команды управления используются для переключения с одного набора команд на другой в зависимости от логического сравнения значений данных. Например, компьютер может выбирать между сложением или вычитанием в зависимости от того, является ли число положительным или нет: if(x > 0) z = x + 5; else z = x – 5;

---

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

Сбор связанной между собой информации, подлежащей обработке прикладной программой, такой как температура, усредненная за определенный период времени, называется данными. Данные могут быть числовыми, символьными или логическими. Числовые данные могут быть записаны в виде вещественных, целых чисел или в экспоненциальном виде. Числовые значения данных обрабатываются как числовые значения, даже если они записаны в виде строк цифр и специальных символов. В языке Cи значения символьных данных записываются в виде символов внутри одинарных кавычек ('a') или строк символов внутри двойных кавычек (''axbcd''). Хотя Cи не имеет типа данных специально для логических данных, целые числа используются для представления значений true (истина) и false (ложь). Ноль интерпретируется как ложь, а все остальные целые числа интерпретируются как истина.

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

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

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

---