metod_15.03.04_atppp_oaip_ump_2016 (1016599), страница 21
Текст из файла (страница 21)
С точки зрения управления, основной характеристикой исполнителя являетсясистема его команд (СКИ), т.е. конечное множество команд, которые понимает и можетвыполнить исполнитель. При построении СКИ решаются две проблемы: проблемаэлементарности команд и проблема полноты системы команд. Система командисполнителя называется полной, если она содержит весь минимально-необходимый90набор команд, позволяющий построить любой алгоритм в том классе задач, на которыйориентирован исполнитель.Взаимосвязь основных понятий из определения алгоритма:ДанныеАлгоритм1-я команда2-я команда…………….N-я командаИСПОЛНИТЕЛЬ(СКИ)РезультатыРабота исполнителя состоит в последовательном формальном выполнении командалгоритма. Следовательно, возможно создание и использование автоматическихисполнителей, в частности, компьютера.Свойства алгоритмов:Дискретность – алгоритм определяется последовательностью шагов (этапов илидействий), причем выполнение очередного шага возможно только после выполненияпредыдущих и основывается на их результатах.Детерминированность (определенность) или точность – однозначность действийисполнителя на каждом шаге обработки данных.Элементарность – простота и строгая определенность правила получения данныхна каждом шаге из предыдущих результатов.Результативность (конечность) – конечное число шагов для получения результата.Массовость – пригодность алгоритма для решения определенного класса задач изнекоторого множества.Работу алгоритма можно представить математической моделью преобразования поправилам Q исходных данных, выраженных посредством алфавита А в окончательныерезультаты за К шагов (действий):Рк = fQ (P),Где Р – слово исходных данных, составленное на основание алфавита А, Q –алгоритм преобразования исходных данных, Рк – к-ый шаг алгоритма.Данная модель подходит как для класса задач, связанных с вычислениями значенийфункции, так и для класса задач, связанных с распознаванием принадлежности объектазаданному множеству.Функция называется вычислимой (разрешимой), если существует алгоритм,определяющий ее значения.Множество называется разрешимым, если имеется алгоритм, который для любогообъекта позволяет определить принадлежность его к данному множеству.Существует круг задач, решение которых алгоритмически невозможно.
Например,«проблема остановки» - когда по исходным данным Р и правилам преобразования Q(описание алгоритма) невозможно установить, завершится ли выполнение алгоритмарезультативной остановкой. Или проблема распознавания эквивалентности алгоритмов91– нельзя создать алгоритм, оценивающий два других алгоритма на предмет полученияими всегда одинаковых результатов.Сказанное означает, что нельзя создать универсальный алгоритм решения любойзадачи из-за наличия алгоритмически неразрешимых проблем.Исполнение любого алгоритма требует обеспечения определенных ресурсов: памятии времени. Поэтому встает вопрос об эффективности их использования. На практикепод эффективностью понимают сокращение времени решения задачи и проводятоценку по временной сложности алгоритма.Временная сложность алгоритма – это функция, которая для всех конкретныходнотипных задач с объемом входных данных n (длина входного слова) ставит всоответствие максимальное время, затрачиваемое алгоритмом на ее решение.
Еслиданная функция имеет полиномиальный характер (f(n) = n или n**2 или n**3), тоданный алгоритм полиномиальный. Если же характер функции (f(n) = 2**n или а** n ),то такой алгоритм носит название экспоненциального.Считается, что задача является трудноразрешимой, если для нее невозможно создатьполиномиальный алгоритм.С практической точки зрения к алгоритму предъявляются требования удобствапрограммирования и эффективности решения задачи.На практике при разработке и описании алгоритма решения задачи определяющимиоказываются возможности исполнителя.Исполнитель алгоритма считается заданным, если для него установлены параметры:элементарных действий алгоритма, которые способен система команд - совокупностьвыполнить исполнитель; формы представления входной и выходной информации; система допустимых внутренних состояний;язык представления алгоритма.Исполнителем алгоритма является субъект или устройство, способныеправильно интерпретировать описание алгоритма и выполнить содержащийся внем перечень действий.Блок обработки данныхРветвление (развилка)(Р – проверяемоелогическое условие)Начало и конец алгоритмаВвод – вывод данныхСоединительная линияОбъединениеПодпрограмма (использование ранее созданных алгоритмов)Комментарий,пояснения,Циклическая конструкция содержаниеподпрограмм.92Если исполнителем является человек, то для правильного и однозначного пониманияим содержания и последовательности действий достаточно представить описаниеалгоритма на естественном языке, в виде формулы, псевдокода (частичноформализованный язык, позволяющий записывать алгоритмы в форме, весьма близкойк алголоподобным языкам программирования) или в виде графической блок-схемыВ графической форме записи или блок-схеме для представления отдельных блоковалгоритма используется обусловленный набор геометрических фигур.Графическая форма предназначена для исполнителя – человек и это ее недостаток.Однако на этапе разработки программ для технического устройства представлениеалгоритма в виде блок-схем оказывается очень удобным для разработчика.По блок-схеме гораздо проще осуществляется запись алгоритма на каком-либоформальном языке.Прежде чем приступить к составлению блок-схемы, необходимо:Регламентировать состав входа и выхода, т.е.
определить имена входных данных,промежуточных и выходных результатов.Дать наименование основной программе и вспомогательным алгоритмам.Исполнитель алгоритма – техническое устройствоРеализации алгоритма техническим устройством определяются совокупностьюдопустимых команд (СКИ), реализация которых считается элементарными действиями.Поэтому алгоритм для реализации техническим устройством должен быть представленв виде последовательности машинных кодов (команд) данного исполнителя.
Этотрудоемко и не всегда удобно.Если программу в машинных кодах разбить по каким-то признакам на части (блоки),то ее можно представить цепочкой из блоков. Каждый блок представляет собойнекоторое законченное комплексное (интегральное) действие группы машинныхкоманд. Для объединения блоков в цепочку заранее устанавливаются определенныеправила. Можно построить устройство, преобразующее полученные блоки в цепочкупрограммы в машинных кодах. В этом случае при построении алгоритмапреобразования данных разработчику достаточно будет указать последовательностьинтегральных команд, а такое устройство будет автоматически преобразовывать их вцепочку истинно элементарных шагов.
Таким образом, указания по выполнениюдействий для каждого конкретного исполнителя формулируются посредствомнекоторого языка. Язык описания алгоритма включает набор определяющих действиякоманд (служебных слов) и синтаксические правила их объединения.Первым (низшим) уровнем интеграции является язык ассемблера – внутренний, т.е.аппаратно-зависимый язык. Он является символьным отражением языка машинныхкодов.Интегрированные команды появляются только в алгоритмических языках высокогоуровня (Паскаль). По отношению к программисту исполнителем в этом случаеоказывается алгоритм транслятора (компилятор) языка программирования.Еще большую степень интеграции элементарных команд может обеспечитьприкладная программа, которая является исполнителем по отношению к конечномупользователю.
СКИ такого исполнителя включает все команды управления,93представленные в виде меню, экранных кнопок, окон настройки и других элементовпользовательского интерфейса. Использование одной команды этого уровня вызываетцепочку сложных действий.В силу ряда причин – непостоянство словарного состава, неоднозначность трактовкифраз, избыточность – невозможно для исполнителей-компьютеров описыватьалгоритмы на обычном языке.
Поэтому были разработаны формальные языки сострогим синтаксисом и полной смысловой определенностью.Для создания формального языка необходимо разработать синтаксис (грамматику) исемантику.Синтаксис (грамматика) – это совокупность правил, согласно которым строятсядопустимые в данном языке конструкции. Семантика – смысловая сторона языка –соотносит единицы и конструкции языка с некоторым внешним миром, для описаниякоторого язык и используется.Любая грамматика начинается с установления алфавита, т.е.
набора символов,посредством которого строятся конструкции языка.Синтаксис формального языка задается некоторой системой правил (порождающейсистемой), которая из небольшого набора исходных конструкций порождает вседопустимые комбинации языка, т.е. язык образуется как множество разрешенныхправилами сочетаний исходных конструкций. Кроме того, синтаксис содержитформулировку условия законченности комбинации языка, в соответствии с которымпринимаются к выполнению только конструкции, выполняющие указанное условие.Конечные цепочки символов данного алфавита называются предложениямиформального языка, а само множество цепочек – языком, описываемым даннойграмматикой.7.2.
«ВЕЛИЧИНА» И АЛГОРИТМКомпьютер работает с информацией. Информация, обрабатываемая компьютернойпрограммой, называется данными.Данные – это сведения, характеризующие какой-то объект, процесс или явление,представленные в определенной форме и предназначенные для дальнейшего использования.Величина – это отдельный информационный объект, отдельная единица данных.Команды в компьютерной программе определяют действия, выполняемые надвеличинами.
По отношению к программе данные делятся на исходные, результаты(окончательные данные) и промежуточные данные, которые получаются в процессевычислений.Исходные данныеПРОГРАММА(промежуточные данные)РезультатыНапример, при решении квадратного уравнения: ах2 + bх + с = 0, исходнымиданными являются коэффициенты а, b, с; результатами – корни уравнения: х1 х2;промежуточным данным – дискриминант уравнения: D = b2 – 4ас.Всякая величина занимает свое определенное место в памяти ЭВМ — ячейку памяти.94У величины имеются три основных характеристики: имя, значение и тип.
На уровнемашинных команд всякая величина идентифицируется адресом ячейки памяти, вкоторой она хранится, а ее значение — двоичный код в этой ячейке. В алгоритмах иязыках программирования величины делятся на константы и переменные. Константа— неизменная величина и в алгоритме она представляется собственным значением,например: 15, 34.7, 'к', true и пр. Переменные величины могут изменять свои значения входе выполнения программы и представляются символическими именами —идентификаторами, например: X, S2, codl5 и пр. Однако ученики должны знать, что иконстанта, и переменная занимают ячейку памяти, а значение этих величинопределяется двоичным кодом в этой ячейке.Теперь о типах величин – типах данных.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
