Максимов Н.В., Партыка Т.Л., Попов И.И. Архитектура ЭВМ и вычислительных систем (2005) (1186253), страница 16
Текст из файла (страница 16)
Схемы предназначаются для преобразования двоичного кода (X) на входе в управляющий сигнал (Z) на одном извыходов Если входов и, то выходных шин должно быть N=2"(табл 1 33, и = 3, У У = 8 )86Глава 1. Вычислительные приборы и устройства...Таблица 1 33. Пример таблицы состояний дешифратора*]Х2Хз2оz\Zz0001000000101000000100111000100001010111101Z42-6Z!000000000001000000100000001000000001000000001^3^5Дешифраторы могут быть линейными и многокаскадными.У линейных дешифраторов все переменные Х\, Х2, Х3 подаются навход одновременно (рис.
1.19, а). Они обладают более высоким бы-1Ч\чч чч—' ч ччччччч\XччX УчXч ч-с__гЧh'—'Нh-СП"н h-ЕR TI— i •ч•ч^2А^2ГЛ Т,•Ч64 выводаКр Т,-мсРис. 1.19. Линейный дешифратор (а), диодная матрица (б),многокаскадный дешифратор (в)зF6-ц7.5. Алгоритмы и программы87стродействием, но более трех переменных одновременно податьнельзя, поэтому чаще применяются многокаскадные дешифраторы.Здесь количество элементов в каждом следующем разряде больше,чем в предыдущем.
На вход первого каскада подается один слог, навход следующего каскада — второй слог и результаты конъюнкций,произведенных в первом каскаде.Простейший линейный дешифратор можно построить на диодной матрице (рис. 1.19, б). В этой схеме используется отрицательнаялогика. При подаче «1» на анод (коллектор) диода он закрывается.Если закрыты все три диода, подсоединенные к одной горизонтальной линии, то на этой линии появляется потенциал -Е, соответствующий уровню «1».Многокаскадный дешифратор можно организовать так, как этоизображено на рис. 1.19, в. Два линейных дешифратора обрабатывают по два слова. В последнем каскаде образуются конъюнкции выходного сигнала первого каскада.
Многокаскадные дешифраторыобладают меньшим быстродействием.1.5. Алгоритмы и программыПонятие алгоритма является одним из основных в современнойнауке и практике. Еще на самых ранних ступенях развития математики (Древний Египет, Вавилон, Греция) в ней стали рассматриваться различные вычислительные процессы чисто механическогохарактера. С их помощью искомые величины ряда задач вычислялись последовательно из исходных величин по определенным правилам и инструкциям. Со временем все такие процессы в математике получили название алгоритмов (алгорифмов).Алгоритм есть совокупность четко определенных правил, процедурили команд, обеспечивающих решение поставленной задачи за конечноечисло шагов.Термин алгоритм происходит от имени средневекового узбекского математика Аль-Хорезми, который еще в IX в.
(825 г.) далправила выполнения четырех арифметических действий в десятичной системе счисления. Процесс выполнения арифметических действий был назван алгоризмом.С 1747 г. вместо слова алгоризм стали употреблять алгорисмус,смысл которого состоял в комбинировании четырех операцийарифметического исчисления — сложения, вычитания, умножения,деления.Ш88Глава 1. Вычислительные приборы и устройства...К 1950 г. алгорисмус стал алгорифмом. Смысл алгорифма чащевсего связывался с алгорифмами Евклида — процессами нахождения наибольшего общего делителя двух многочленов, наибольшейобщей меры двух отрезков и т.
п.Важнейшими характеристиками алгоритма являются: выбранный язык описания, однозначность определения цели, расчлененность на отдельные элементарные акты и достижение искомого результата. Благодаря этому, алгоритм является точным описаниемпроцесса обработки или передачи данных. Алгоритмы описываютсяв виде правил, формул, программ. Нахождение алгоритмов решенияразличных классов задач является одной из целей математики.Способы записи алгоритмовАлгоритм должен быть понятен (доступен) пользователю и/илимашине.
Доступность пользователю означает, что он обязан отображаться посредством конкретных формализованных изобразительных средств, понятных пользователю. В качестве таких изобразительных средств используются следующие способы их записи:• словесный;• формульный;• табличный;• операторный;• графический;• макроязык программирования.При словесном способе записи содержание последовательныхэтапов алгоритма описывается в произвольной форме на естественном языке.Формульный способ основан на строго формализованном аналитическом задании необходимых для исполнения действий.Табличный способ подразумевает отображение алгоритма в видетаблиц, использующих аппарат реляционного исчисления и алгебрулогики для задания подлежащих исполнению взаимных связей между данными, содержащимися в таблице.Операторный способ базируется на использовании для отображения алгоритма условного набора специальных операторов: арифметических, логических, печати, ввода данных и т.
д.; операторыснабжаются индексами и между ними указываются необходимыепереходы, а сами индексированные операторы описываются чащевсего в табличной форме.Графическое отображение алгоритмов в виде блок-схем — весьма наглядный и распространенный способ. Графические символы,1.5. Алгоритмы и программы89отображающие выполняемые процедуры, стандартизованы.
Нарядус основными символами используются и вспомогательные, поясняющие процедуры и связи между ними.Алгоритмы могут быть записаны и в виде команд какого-либоязыка программирования. Если это макрокоманды, то алгоритм читаем и пользователем-программистом, и вычислительной машиной,имеющей транслятор с соответствующего языка.Приведем пример словесного представления алгоритма на примере нахождения произведения п натуральных чисел (с = п\ == 1-2 3-4-...-я).Этот процесс может быть записан в виде следующей системыпоследовательных указаний (пунктов):1. Полагаем с равным единице и переходим к следующемупункту.2.
Полагаем / равным единице и переходим к следующемупункту.3. Полагаем с равным с = i • с и переходим к следующему указанию.4. Проверяем, равно ли / числу п. Если / = п, то вычисления прекращаем. Если / < я, то увеличиваем / на единицу и переходим кпункту 3.Классификация и свойства алгоритмовАлгоритмы, в соответствии с которыми решение поставленныхзадач сводится к арифметическим действиям, называются численными алгоритмами.Алгоритмы, в соответствии с которыми решение поставленныхзадач сводится к логическим действиям, называются логическими алгоритмами. Примерами логических алгоритмов могут служить алгоритмы поиска минимального числа, поиска пути на графе, в лабиринте и др.Алгоритмом является последовательность четких однозначныхуказаний, которые, будучи применены к определенным имеющимсяданным, обеспечивают получение требуемого результата.
Данныминазывают все величины, участвующие в решении задачи. Данные,известные перед выполнением алгоритма, являются начальными,исходными данными. Результат решения задачи — это конечные, выходные данные.Каждое указание алгоритма предписывает исполнителю выполнить одно конкретное законченное действие. Исполнитель не можетперейти к выполнению следующей операции, не закончив полно-90Глава 1. Вычислительные приборы и устройства...стью выполнения предыдущей.
Предписания алгоритма надо выполнять последовательно одно за другим, в соответствии с указаннымпорядком их записи. Выполнение всех предписаний гарантируетправильное решение задачи.Поочередное выполнение команд алгоритма за конечное числошагов приводит к решению задачи, к достижению цели. Разделениевыполнения решения задачи на отдельные операции (выполняемыеисполнителем по определенным командам) — важное свойство алгоритмов, называемое дискретностью.Анализ примеров различных алгоритмов показывает, что записьалгоритма распадается на отдельные указания исполнителю выполнить некоторое законченное действие.
Каждое такое указание называется командой. Команды алгоритма выполняются одна за другой.После каждого шага исполнения алгоритма точно известно, какаякоманда должна выполняться следующей. Алгоритм представляетсобой последовательность команд (также — инструкций, директив),определяющих действия исполнителя (субъекта или управляемогообъекта).Таким образом, выполняя алгоритм, исполнитель может не вникать в смысл того, что он делает, и вместе с тем получать нужныйрезультат. В таком случае говорят, что исполнитель действует формально, т. е. отвлекается от содержания поставленной задачи итолько строго выполняет некоторые правила, инструкции.Это очень важная особенность алгоритмов.
Наличие алгоритмаформализовало процесс, исключило рассуждения. Если обратиться кпримерам других алгоритмов, то можно увидеть, что и они позволяют исполнителю действовать формально. Таким образом, созданиеалгоритма дает возможность решать задачу формально, механическиисполняя команды алгоритма в указанной последовательности.Построение алгоритма для решения задачи из какой-либо области требует от человека глубоких знаний в этой области, бываетсвязано с тщательным анализом поставленной задачи, сложными,иногда очень громоздкими рассуждениями. На поиски алгоритмарешения некоторых задач могут быть потрачены многие годы.
Нокогда алгоритм создан, решение задачи по готовому алгоритму ужене требует каких-либо рассуждений и сводится только к строгомувыполнению команд алгоритма.Всякий алгоритм составляется в расчете на конкретного исполнителя с учетом его возможностей. Для того чтобы алгоритм могбыть выполнен, нельзя включать в него команды, которые исполнитель не в состоянии выполнить. У каждого исполнителя имеетсясвой перечень команд, которые он может исполнить.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
