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

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

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

Основными свойствами правильно построенного алгоритма являются:

l Результативность — алгоритм должен давать конкретное конструктивное решение, а не указывать на возможность решения вообще;

l Релевантность — алгоритм должен соответствовать сущности задачи и формировать верные, не допускающие неоднозначного толкования решения;

l Реалистичность — возможность реализации алгоритма при заданных ограничениях: временных, программных, аппаратных;

l Массовость — алгоритм должен быть воспроизводимым, пригодным для решения всех задач определенного класса на всем множестве допустимых значений исходных данных;

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

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

l экономичность — алгоритм должен обеспечивать необходимую и достаточную точность решения задачи.

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

l при словесном способе записи содержание последовательных этапов алгоритма описывается в произвольной форме на естественном языке;

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

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

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

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

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

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

Машинно-ориентированные языки (МК — мнемокоды, ЯСК — языки символического кодирования, автокоды, ассемблеры) относятся к языкам программирования низкого уровня — программирование на них наиболее трудоемко, но позволяет создавать оптимальные программы, максимально учитывающие функционально-структурные особенности конкретного компьютера. Программы на этих языках позволяют создавать, при прочих равных условиях, наиболее короткие и быстродействующие машинные программы. Кроме того, знание основ программирования на машинно-ориентированном языке позволяет специалисту подробнейшим образом разобраться с архитектурой компьютера. Именно последнее обстоятельство в большей степени и обусловливает целесообразность ознакомления с машинно-ориентированным языком, каковым и является язык ассемблер, при изучении вычислительных систем. Большинство команд машинно-ориентированных языков при трансляции (переводе) на машинный (двоичный) язык генерируют одну машинную команду (исключение составляют только макрокоманды обращения к внешним устройствам компьютера).

Процедурно-ориентированные и проблемно-ориентированные языки относятся к языкам высокого уровня, использующим макрокоманды. Макрокоманда при трансляции генерирует много машинных команд: для процедурно-ориентированной макрокоманды это соотношение в среднем «1 к десяткам машинных команд», а для проблемно-ориентированной команды это «1 к сотням машинных команд». Процедурно-ориентированные языки программирования являются самыми используемыми (Basic, Pascal, C++, PL, ALGOL, COBOL и еще десятки популярных языков). В этом случае программист должен описывать всю процедуру решения задачи, тогда как проблемно-ориентированные языки (их называют также непроцедурными) позволяют лишь формально идентифицировать проблему и указать состав, структуры представления и форматы входной и выходной информации для задачи.

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

Трансляторы бывают двух типов: трансляторы-компиляторы и трансляторы-интерпретаторы.

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

Откомпилированные двоично-кодированные программы практически человеком не читаемы. Но их можно вызвать в специальную программу-отладчик (DEBUG и его разновидности), которая переведет эти программы на язык ассемблер, то есть сделает их «человекочитаемыми» (еще один довод в пользу изучения языка ассемблер).

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

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

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

Машинная команда состоит из двух частей: операционной и адресной.

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

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

По количеству адресов (а1, а2, а3, ¼), записываемых в команде, команды делятся на безадресные, одно-, двух- и трехадресные.

а1 и а2 — адреса ячеек (регистров), где расположены, соответственно, первое и второе числа, участвующие в операции, а3 — адрес ячейки (регистра), куда следует поместить число, полученное в результате выполнения операции.

а1 — это обычно адрес ячейки (регистра), где хранится первое из чисел, участвующих в операции, и куда после завершения операции должен быть записан результат операции; а2 — обычно адрес ячейки (регистра), где хранится второе участвующее в операции число.

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

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

Наибольшее применение в ПК нашли двухадресныекоманды.

Пример двухадресной команды, записанной на языке символического кодирования (ЯСК):

Эту команду следует расшифровать так: СЛожить число, записанное в ячейке 0103 памяти, с числом, записанным в ячейке 5102, а затем результат (то есть сумму) поместить в ячейку 0103.

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

Современные компьютеры автоматически выполняют несколько сотен различных команд. Например, стандартный набор современных ПК IBM PC содержит более 240 машинных команд.

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

l операции пересылки информации внутри компьютера;

l операции над строками (текстовой информацией);

l операции обращения к внешним устройствам компьютера;

l обслуживающие и вспомогательные операции.

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

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

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

Команд безусловных передач управления обычно только три:

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

l команда передачи управления (ее часто называют командой вызова процедуры или подпрограммы), которая, кроме передачи управления процедуре, еще и запоминает в специальной стековой памяти адрес следующей команды (адрес возврата из процедуры);

l безадресная команда передачи управления (команда возврата из процедуры) возвращающая управление по запомненному адресу возврата.

Вторая и третья из названных команд безусловных передач управления работают «на пару» — одна передает управление процедуре, другая возвращает из нее. Важную роль в выполнении этих команд передачи управления (да и при многих других ситуациях, отрабатываемых компьютером) играет специальным образом организованная область оперативной памяти — стековаяпамять. Обращение к ячейкам этой памяти выполняется по принципу «последний записанный операнд первым считывается» или иначе «первым вошел — последним вышел» (FILO — first input, last output). Стековая память позволяет удобно реализовать процессы иерархического обращения ко многим процедурам (количество уровней иерархии практически не ограничено), последовательно записывая и выдавая по принципу FILO адреса возврата каждой из них.

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

Номер команды соответствует адресу ячейки памяти, где эта команда хранится.

l СЛ 10, 11, 11 — сложить число, находящееся в ячейке с адресом 10, с числом, находящимся в ячейке с адресом 11, и записать результат (сумму) в ячейку с адресом 11;

l УМ 11, 11, 101 — умножить число, находящееся в ячейке с адресом 11, на число, находящееся в ячейке с адресом 11, и записать результат (квадрат числа) в ячейку с адресом 101;

l СЛ К + 2, 12, К+2 — сложить двоичный код команды, находящийся в ячейке с адресом К + 2, со структурированным кодом, находящимся в ячейке с адресом 12, и записать результат (измененный код команды) в ячейку с адресом К + 2;

l УПУ< К + 2, 13, К + 1 — условная передача управления: если двоичный код команды, находящийся в ячейке с адресом К + 2, меньше двоичного кода команды, находящегося в ячейке с адресом 13, выполнять команду К + 1; в противном случае выполнять команду К + 5.

Исходные данные к программе (операнды) хранятся в ячейках:

l ячейки 12 и 13 — структурированные под код команды двоичные числа:

Что же считает программа? Рассмотрим последовательно выполнение команд. В программе выполняется много циклов вычислений.

Расчет окончен. В результате работы программы последовательно рассчитаны квадраты чисел от 1 до 100, которые записаны в последовательные ячейки памяти — 101–200.

Рассмотренная программа иллюстрирует несколько важных особенностей компьютерных программ:

l возможность выполнения операций над командами, то есть возможность автоматической модификации программ (в более сложных вариантах это может означать самонастройку программ, их оптимизацию, возможность компьютера самостоятельно создавать программы, которые могут превзойти программы «рукотворные»; отсюда извечный вопрос: «могут ли роботы превзойти своего создателя?»;

l возможность многократного повторения выполнения группы команд в цикле;

l возможность выполнения одной короткой программой большого объема вычислений (при замене, например, третьего адреса в коде команды, хранимой в ячейке с адресом 13, на 1101 этой программой будут вычислены квадраты тысячи чисел.

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

35. Формулировка и формализованная постановка задачи.

36. Выбор математической модели и метода решения задачи.

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

38. Составление программы решения задачи, то есть запись алгоритма решения задачи на языке, понятном машине.

40. Ввод исходных данных и решение задачи на компьютере.

41. Анализ полученных результатов и выводы по результатам решения.

Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право...

ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между...

Что будет с Землей, если ось ее сместится на 6666 км? Что будет с Землей? - задался я вопросом...

ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: