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

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

Понятие алгоритм ввел математик IX в. Аль Хорезми и использовал его для выполнения арифметических действий, для решения задач.

Свойства алгоритмов:

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

· Каждый алгоритм строится в расчете на некоторого исполнителя. Для того чтобы исполнитель мог решить задачу по заданному алгоритму, необходимо, чтобы он был в состоянии понять и выполнить каждое действие, предписываемое командами алгоритма. Такое свойство алгоритмов называется определенностью (или точностью) алгоритма. (Например, в алгоритме указано, что надо взять 3—4 стакана муки. Какие стаканы, что значит 3—4, какой муки?)

· Еще одно важное требование, предъявляемое к алгоритмам, - результативность (или конечность) алгоритма. Оно означает, что исполнение алгоритма должно закончиться за конечное число шагов.

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

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

Способы задания алгоритма:

· словесный, (недостаток–многословность, возможна неоднозначность–«он встретил ее на поле с цветами»),

· табличный (физика, химия и т. д.),

· графический т.е. блок-схемы.

(пример блоксхемы)

Расчет максимального значения линий гистограммы

MaxValue=0

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

Расчет kx, ky

x=0, y=0

i=0(1)m_in

Расчет x, y Вывод линий гистограммы  

начало

конец

нет

да

Методы программирования.

1 Структурное программирование.

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

2 Объектно-ориентированное программиирование:

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

Объектно-ориентированный подход использует следующие базовые понятия:

· объект;

· свойство объекта;

· метод обработки;

· событие;

· класс объектов.

Объект это совокупность свойств (параметров) определенных сущностей и методов их обработки (программных средств).

Объект содержит инструкции (программный код), определяющие действия, которые может выполнять объект, и обрабатываемые данные.

Свойство – характеристика объекта, его параметр. Все объекты наделены определенными свойствами, которые в совокупности выделяют объект из множества других объектов.

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

Одним из свойств объекта являются метод его обработки. Метод это программа действий над объектом или его свойствами. Метод рассматривается как программный код, связанный с определенным объектом; осуществляет преобразование свойств, изменяет поведение объекта.

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

Событие – изменение состояния объекта.

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

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

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

языки и системы программирования;

Языки программирования делят на:

· машинные – языки программирования, воспринимаемые аппаратной частью компьютера (машинные коды);

· машинно-ориентированные ‑ языки программирования, которые отражают структуру конкретного типа компьютера (ассемблеры);

· алгоритмические – не зависящие от архитектуры компьютера языки программирования для отражения структуры алгоритма: Паскаль, Фортран и др.;

· процедурно-ориентированные – языки программирования, где имеется возможность описания программы как совокупности процедур (подпрограмм): С++, Паскаль.;

· проблемно-ориентированные – языки программирования, предназначенные для решения задач определенного класса: Fox Pro, Prolog.

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

Программы, составленные на ассемблерах, являются более короткими и требуют меньшего объема памяти. Однако разработка программ на ассемблерах предъявляет высокие требования к уровню подготовки программистов, которые должны хорошо знать конструктивные особенности ЭВМ.

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

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

К ним относятся Фортран, Паскаль, Си и др. Один из самых старых языков высокого уровня – язык Фортран – активно используется на персональных компьютерах и применяется главным образом при разработке прикладных систем, ориентированных на научные исследования, автоматизацию проектирования, где уже накоплены обширные стандартные библиотеки программ. Наиболее популярной его версией является Фортран-90, отдельные элементы которого реализованы в Microsoft Fortran, а в полном объеме – в Fortran PowerStation.

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

Язык Си применяется главным образом для создания системных и прикладных программ, в которых скорость работы и объем памяти являются критическими параметрами. Язык Си, более точно, чем Паскаль, позволяет программисту учитывать аппаратные особенности ЭВМ. Основными достоинствами языков Паскаль и Си, необходимыми при построении больших программных систем, являются:

· возможность работы с данными сложной структуры;

· наличие развитых средств для выделения отдельных частей программ в процедуры;

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

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

Рис. 4.54. Перевод текста программы

Выделяют три типа трансляторов:

· ассемблеры;

· интерпретаторы;

· компиляторы.

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

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

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

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

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

· средства написания программ (редакторы);

· преобразования программ к виду, удобному для выполнения на ПК (ассемблеры, компиляторы, загрузчики и редакторы связей);

· средства отладки: консоль и отладка программ.

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

Дата добавления: 2014-01-11