Logo GenDocs.ru

Поиск по сайту:  


Загрузка...

Ответы по информатике - файл 1.doc


Ответы по информатике
скачать (1803 kb.)

Доступные файлы (1):

1.doc1803kb.16.11.2011 09:26скачать

содержание
Загрузка...

1.doc

1   2   3   4   5   6   7   8
Реклама MarketGid:
Загрузка...

^ 6. Позиционные системы счисления. Представление чисел в компьютере. Двоичное кодирование текстовой, графической и звуковой информации.

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

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

Определение 1. Система счисления – это совокупность правил для обозначения и наименования чисел.

Системы счисления делятся на следующие виды:

  1. непозиционные системы счисления;

  2. позиционные системы счисления.

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

Определение 2. Непозиционной называется такая система счисления, в которой количественный эквивалент каждой цифры не зависит от ее положения (места, позиции) в коде числа.

Непозиционные системы счисления возникли раньше позиционных. Вот только некоторые примеры таких систем.

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

I – 1; V – 5; Х – 10; L – 50; С – 100; D – 500; М – 1000; ...

Для записи промежуточных чисел используется правило:

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

Например, IX обозначает 9, XI обозначает 11. Десятичное число 28 представляется следующим образом: XXVIII =10+10+5+1+1+1, а десятичное число 99 имеет вот такое представление: IC=–1+100.

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

Пример 2. В старину на Руси широко применялись системы счисления, с помощью которых сборщики податей заполняли квитанции об уплате подати (ясака) и делали записи в податной тетради.

Например, 1232 руб. 24 коп. изображается так, как на рисунке. Вот текст закона об этих, так называемых ясачных знаках:

"Чтобы на каждой квитанции, выдаваемой Родовитому Старосте, от которого внесен будет ясак, кроме изложения словами, было показано особыми знаками число внесенных рублей и копеек так, чтобы сдающие простым счетом сего числа могли быть уверены в справедливости показания. Употребляемые в квитанции знаки означают: звезда − тысяча рублей, колесо − сто рублей, квадрат − десять рублей, Х − один рубль, IIIIIIIIII − десять копеек, I − копейку. Дабы неможно было сделать здесь никаких прибавлений, все таковые знаки очерчивать кругом прямыми линиями" .

Непозиционные системы счисления имеют ряд недостатков:

  1. Для записи больших чисел приходится вводить новые цифры. Например, пользуясь только цифрами I, V, X, число "тысяча" записать неудобно. И всегда есть числа, которые трудно изобразить даже вновь введенными цифрами.

  2. Невозможно записывать дробные и отрицательные числа.

  3. Сложно выполнять арифметические операции.

Определение 3. Система счисления называется позиционной, если количественный эквивалент (значение) цифры зависит от ее места (позиции) в коде числа.

В привычной нам системе счисления для записи чисел используются десять различных знаков (цифры 0, 1, 2, 3, 4, 5, 6, 7, 8 и 9). Поэтому ее называют десятичной. Из двух написанных рядом цифр (55) левая выражает число, в десять раз большее, чем правая. Имеет значение не только сама цифра, но и ее место, позиция. Именно поэтому такую систему счисления называют позиционной (поместной).

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

  • с помощью нескольких колес, каждое из которых может фиксироваться в одном из десяти возможных положений;

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

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

Определение 4. Основанием (базисом) позиционной системы счисления называется количество знаков или символов, используемых для изображения числа в данной системе счисления.

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

В десятичном числе А=255=2х102+5х101+5х100 цифры 5, находящиеся на разных позициях, имеют различные количественные значения – 5 десятков и 5 единиц. При перемещении цифры на соседнюю позицию ее вес (числовой эквивалент) изменяется в 10 раз.

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

^ Представление чисел в позиционных системах счисления

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

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

В системе счисления с основанием q (q-ичная система счисления) единицами разрядов служат последовательные степени числа q, иначе говоря, q единиц какого-либо разряда образуют единицу следующего разряда. Для записи чисел в q-ичной системе счисления требуется q различных знаков (цифр), изображающих числа 0, 1,..., q–1. Запись числа q в десятичной системе счисления имеет вид 10.

В позиционной системе счисления любое вещественное число может быть представлено в следующем виде:

Aq=±(an-1qn–1+an–2qn–2+...+a0q0+a–1q–1+a–2q–2+...+a–mq–m)    (1)

или



Здесь:

  • Аq − само число,

  • q − основание системы счисления,

  • аi − цифры данной системы счисления,

  • n − число разрядов целой части числа,

  • m − число разрядов дробной части числа.

Определение 5. Запись числа по формуле (1) называется развернутой формой записи.

Иначе такую форму записи называют многочленной, или степенной.

Пример 1. Десятичное число А10=4718,63 в виде (1) запишется так:

А10=4 × 103+7 × 102+1 × 101+8 × 100+6 × 10–1+3 × 10–2

Пример 2. Восьмеричная система счисления. Основание: q=8. Алфавит: 0, 1, 2, 3, 4, 5, 6 и 7.

Формула (1) для восьмеричной системы счисления имеет вид:

A8=(an–1×8n–1+...+a0×80+a–1×8–1+...+a–m×8–m), где ai − цифры 0–7.

Восьмеричное число A8=7764,1 в виде (1) запишется так:

A8=7 × 83+7 × 82+6 × 81+4 × 80+1 × 8–1

Пример 3. Пятеричная система счисления. Основание: q=5. Алфавит: 0, 1, 2, 3 и 4.

Пятеричное число A5=2430,21 в виде (1) запишется так:

A5=2 × 53+4 × 52+3 × 51+0 × 50+2 × 5–1+1 × 5–2

Развернутая форма записи числа применяется для перевода чисел из любой системы счисления в десятичную. Так, вычислив последнее выражение, можно получить десятичный эквивалент указанного пятеричного числа: 365,44.

Пример 4. Шестнадцатеричная система счисления. Основание: q=16. Алфавит: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, А, В, С, D, Е и F.

Здесь только десять цифр из шестнадцати имеют общепринятое обозначение 0–9. Для записи остальных цифр обычно используются первые пять букв латинского алфавита − А, В, С, D, Е и F, означающие соответственно 10, 11, 12, 13, 14 и 15.

Таким образом, запись 3AF, означает:

ЗAF16=З × l62+10 × l61+l5 × l60=З × 256+160+15=94310.

Из (1) легко получить формулу (2) для записи произвольного целого числа:

Aq=±(an–1 × qn–1+an–2 × qn–2+...+a–m × q–m)      (2)

и формулу (3) для записи произвольного дробного числа:

Aq=±(a–1 × q–1+a–2 × q–2+...a–m × q–m)      (3)

Определение 6. Свернутой формой записи числа называется запись в виде

Aq=±аn–1аn–2...a1а0a–1...а–m

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

Примеры чисел: 32218; 43216; 12215; 12213; 10112.

Можно кодировать размеры, формы, цвета объектов, а можно кодировать сообщение, т.е. само изображение. Определение указанных характеристик объекта неоднозначно связано с его изображением (вспомним поговорку "Лучше один раз увидеть, чем сто раз услышать"). Поэтому графическая информация кодируется только как сообщения. В этой связи сразу возникает вопрос об алфавите, в котором формируются графические сообщения. Здесь сразу возникает проблема, так как любое графическое изображение состоит из бесконечно большого числа бесконечно малых фрагментов, отличающихся друг от друга. Иными словами, для формирования изображения требуется бесконечный алфавит, если под одним его символом понимать бесконечно малый фрагмент изображения. По этой причине кодирование графических сообщений проводится в два этапа. Первый этап – это дискретизация, т.е. представление изображений как совокупность конечного числа элементов. В зависимости от выбора вида этих элементов различают растровое и векторное представления. В первом случае на изображение накладывается сетка (растр), каждая ячейка которой рассматривается как фрагмент, определяемый набором атрибутов: координатами, формой, размером, цветом. Можно сказать, что, используя растр, мы представляем изображение в виде конечной совокупности точек. Примерно так, как это делается в одном из направлений живописи под названием "пуантилизм". Физическое представление ячейки растра на экране монитора получило название пиксель (pixel – аббревиатура от picture element – ячейка (элемент) изображения). Из сказанного следует, что отождествлять пиксель и физическое зерно покрытия экрана монитора неправильно. Размер зерна определяет минимально возможный размер пикселя. В заданном растре в каждый пиксель может входить определенное количество зерен. Иными словами, пиксель – это точка изображения, но не точка экрана.

Такие атрибуты пикселя, как координаты, форма, размер, определяются растром, так что свободным атрибутом оказывается цвет пикселя. Можно сказать, что элементами алфавита графических сообщений являются цвета. Для цветового алфавита, как и для символьного, строится кодировочная таблица, т.е. каждому цвету ставится в соответствие номер – целое число, которое затем переводится в двоичную систему счисления. Количество цветов N определяется размером двоичной последовательности b, используемой для кодировки, и может быть найдено по формуле: N=2b.

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


^ 7. Хранение информации. Логические основы компьютера.

Информация на ПК хранится в файлах. Файл — это поименованная область дискового пространства, то есть файл обязательно должен иметь имя и место размещения на жестком диске, дискете или ином носителе информации. Имя файла состоит из двух частей. Первую часть имени также называют «имя». Имя файла может содержать до 255 символов. В качестве символов можно использовать русские и английские буквы, пробел, цифры и некоторые знаки. Нельзя использовать знаки / \<> | * ?: ". Вторую часть имени называют «расширение». Расширение может содержать до трех символов. Между именем и расширением ставится точка. В качестве символов можно использовать русские и английские буквы, цифры и некоторые знаки. Нельзя использовать знаки / \ <> | * ?: ". Рекомендуется давать файлу имя, отражающее его содержание. Например, Письмо Иванову, Приказ о командировании Петрова и т. д. Для удобства работы не рекомендуется использовать в имени файла более 25-30 символов. Расширение файлу обычно автоматически присваивается программой, в которой этот файл создан. Например программа Word присваивает файлам расширение .doc, программа Excel - .xls и т. д. Не рекомендуется произвольно изменять расширение имени файла.

При размещении информации на жестком диске его для удобства особым программным способом условно разделяют на несколько частей - логических дисков. Логический диск имеет имя. Имя логического диска представляет собой латинскую букву с двоеточием - С: D: и т. д. Имена А: и В: зарезервированы для дисководов гибких дисков (дискет). Устройство для работы с компакт-дисками также имеет имя - первая свободная буква, следующая за именами логических дисков. Например, если жесткий диск разделен на три логических диска С: D: Е:, устройство для работы с компакт-дисками имеет имя F:.

Имена файлов на логическиx дисках регистрируются в папках (каталогах). Папки имеют имена. Требования к именам папок те же, что и к именам файлов. В большинстве случаев имена папок не имеют расширения.


^ 8. Базовые логические элементы компьютера. Сумматор двоичных чисел. Триггер.

Основные логические устройства компьютера (сумматор, регистр).

    Поскольку любая логическая операция может быть представлена в виде комбинации трех базовых операций (И, ИЛИ, НЕ), любые устройства компьютера, производящие обработку или хранение информации, могут быть собраны из базовых логических элементов как из кирпичиков.
    
    Логические элементы ЭВМ

Базовые логические элементы реализуют три основные логические операции:

  • логический элемент «И»

  • логический элемент «ИЛИ»

  • логический элемент «НЕ»

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

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








A

B A&BvC&D

C

D




A

B (AvB)&C&D

C

D





A

A&BvC

B

C


Построить таблицы истинности.

A

B

A&B A




A

B

A B

И

И

И




И

И

И

И

Л

И




И

Л

И

Л

И

Л




Л

И

Л

Л

Л

И




Л

Л

И

Сумматор — это электронная логическая схема, выполняющая суммирование двоичных чисел.

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

^ Многоразрядный двоичный сумматор, предназначенный для сложения многоразрядных двоичных чисел, представляет собой комбинацию одноразрядных сумматоров, с рассмотрения которых мы и начнём.

При сложении чисел A и B в одном i-ом разряде приходится иметь дело с тремя цифрами:

1. цифра ai первого слагаемого;

2. цифра bi второго слагаемого;

3. перенос pi–1 из младшего разряда.

В результате сложения получаются две цифры:

1. цифра ci для суммы;

2. перенос pi из данного разряда в старший.

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

Входы

Выходы

Первое слагаемое

Второе слагаемое

Перенос

Сумма

Перенос

0

0

0

0

0

0

0

1

1

0

0

1

0

1

0

0

1

1

0

1

1

0

0

1

0

1

0

1

0

1

1

1

0

0

1

1

1

1

1

1

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

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

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

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

Самый простой триггер – RS-триггер. Он состоит из двух логических элементов «ИЛИ» и двух элементов «НЕ».

Входы и выходы элементов соединены кольцом: выход первого соединен со входом второго и выход второго – со входом первого.

Триггер имеет два входа: S (от англ. set – установка) и R (от англ. reset – сброс) и два выхода Q (прямой) и НЕ(Q) (инверсный).



В обычном состоянии на входы триггера подан сигнал 0, и триггер хранит 0. Для записи 1 на вход S (установочный) подается сигнал 1. Последовательно рассмотрев прохождение сигнала по схеме, видим, что триггер переходит в это состояние и будет устойчиво находиться в нем и после того, как сигнал на входе S исчезнет. Триггер запомнил 1, то есть с выхода триггера Q можно считать 1. При отсутствии входных сигналов триггер сохраняет последнее занесенное в него значение сколь угодно долго.

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

Подача 1 на входы R и S одновременно считается запрещенным, поскольку в этом случае после снятия входных сигналов (особенно одновременного!) результат непредсказуем. В более сложных триггерах подобная ситуация обрабатывается при помощи специальной входной логики.

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

  • динамическая память, будучи проще по устройству, имеет большую емкость и меньшую стоимость;

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

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

  • статическая память содержит больше активных элементов – триггеров, а значит, сильнее нагревается при работе.

Как видно из приведенных выше перечислений, ни один из видов памяти не свободен от недостатков. В настоящее время ОЗУ компьютера представляет собой динамическую память – решающим оказывается преимущество, стоящее в списке на первом месте.

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

Этот вид памяти заслуживает отдельного рассмотрения. Он появился относительно недавно, но, начиная с 486-го процессора, без кэш-памяти не обходится ни одна модель. Название "кэш" происходит от английского слова cache, которое обозначает тайник или замаскированный склад (в частности, этим словом называют провиант, оставленный экспедицией для обратного пути, или запас продуктов, например, зерна или меда, который животные создают на зиму). "Секретность" кэша заключается в том, что он невидим для пользователя и данные, хранящиеся там, недоступны для прикладного программного обеспечения. Процессор использует кэш, помещая туда извлеченные им из ОЗУ данные и команды программы и запоминая при этом в специальном каталоге адреса, откуда информация была извлечена. Если эти данные потребуются повторно, то уже не надо будет терять времени на обращение к ОЗУ – их можно получить из кэш-памяти значительно быстрее. Поскольку объем кэша существенно меньше объема оперативной памяти, его контроллер (управляющая схема) тщательно следит за тем, какие данные следует сохранять в кэше, а какие заменять: удаляется та информация, которая используется реже или совсем не используется. Следует заметить, что кэш-память является очень эффективным средством повышения производительности компьютера, в чем легко убедиться на практике, если в вашем компьютере предусмотрена возможность отключения кэша.

В современных компьютерах кэш обычно строится по двухуровневой схеме. При этом первичный кэш встроен непосредственно внутрь процессора, а вторичный обычно устанавливается на системной плате. Как и для ОЗУ, увеличение объема кэша повышает эффективность работы компьютерной системы.

^ 9. Многопроцессорные системы. Структура и функции.

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

Под общим полем понимается равнодоступность устройств. Так, общее поле памяти означает, что все модули ОП доступны всем процессорам и каналам ввода-вывода (или всем периферийным устройствам в случае наличия общего интерфейса); общее поле ВЗУ означает, что образующие его устройства доступны любому процессору и каналу.

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

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

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

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

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

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

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

Используются следующие способы организации межмодульных (межустройственных) связей:

  • регулярные связи между модулями;

  • многоуровневые связи, соответствующие иерархии интерфейсов ЭВМ;

  • многовходовые модули (в частности, модули памяти);

  • коммутатор межмодульных связей (“Эльбрус”);



  • общая шина (“СМ ЭВМ”).



Принципы организации МПС и ММС существенно отличаются в зависимости от их назначения. Поэтому целесообразно различать:

  • ВС, ориентированные в первую очередь на достижение сверхвысокой производительности;

  • ВС, ориентированные в первую очередь на повышение надежности и живучести.

^ 10. Алгоритм и его формальное исполнение. Типы и свойства алгоритмов. Основные типы алгоритмических структур.

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

Термин имеет интересное историческое происхождение. В IX веке великий узбекский математик аль-Хорезми разработал правила арифметических действий над десятичными числами. Совокупность этих правил в Европе стали называть "алгоризм". Впоследствии слово трансформировалось до известного нам сейчас вида и, кроме того, расширило свое значение: алгоритмом стали называть любую последовательность действий (не только арифметических), которая приводит к решению той или иной задачи. Можно сказать, что понятие вышло за рамки математики и стало применяться в самых различных областях.

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

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

А теперь пример из художественной литературы. Вот как описывает известная писательница Андрэ Нортон в своей книге "Саргассы в космосе" алгоритм движения по гигантскому лабиринту. Главный герой Дейн, тайком наблюдая за главарем галактических гангстеров Ричем, быстро узнает этот алгоритм.

"Он дал Ричу отойти, а затем двинулся следом. Рич шагал уверенно, сразу было видно, что он отлично знает дорогу. Еще до того, как вдали в сером сумраке засветился луч фонарика Муры, Дейн уже знал формулу пути к выходу из лабиринта. Два поворота направо, один налево, еще три направо и пропустить один проход. И снова: два поворота направо, один налево и так далее до самого выхода. Рич на глазах у Дейна проделал этот цикл четыре раза подряд..."

Описанные выше алгоритмы обычно принято называть "бытовыми". Кроме них, можно выделить еще три крупных разновидности алгоритмов: вычислительные, информационные и управляющие. Первые, как правило, работают с простыми видами данных (числа, векторы, матрицы), но зато процесс вычисления может быть длинным и сложным. Информационные алгоритмы, напротив, реализуют сравнительно небольшие процедуры обработки (например, поиск элементов, удовлетворяющих определенному признаку), но для больших объемов информации. Наконец, управляющие алгоритмы непрерывно анализируют информацию, поступающую от тех или иных источников, и выдают результирующие сигналы, управляющие работой тех или иных устройств. Для этого вида алгоритмов очень существенную роль играет их быстродействие, так как управляющие сигналы всегда должны появляться в нужный момент времени.

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

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



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

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

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

Компьютер – формальный автоматический исполнитель алгоритмов.

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

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

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

Дискретность (от лат. discretus – разделенный, прерывистый). Процесс решения задачи должен быть разбит на последовательность отдельных шагов, каждый из которых называется командой. Примером команд могут служить пункты инструкции, нажатие на одну из кнопок пульта управления, рисование графического примитива (линии, дуги и т.п.), оператор языка программирования. Наиболее существенным здесь является тот факт, что алгоритм есть последовательность четко выделенных пунктов – такие "прерывные" объекты в науке принято называть дискретными.

Понятность. Каждая команда алгоритма должна быть понятна тому, кто исполняет алгоритм; в противном случае эта команда и, следовательно, весь алгоритм в целом не могут быть выполнены. Данное требование можно сформулировать более просто и конкретно. Составим полный список команд, которые умеет делать исполнитель алгоритма, и назовем его системой команд исполнителя (СКИ). Тогда понятными будут являться только те команды, которые попадают в этот список. Именно из такой формулировки становится ясно, почему компьютер такой "привередливый" при приеме введенных в него команд: даже если неверно написана всего одна буква, команда уже не может быть обнаружена в СКИ.

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

^ Определенность или детерминированность (от лат. determinate – определенность, точность). Команды, образующие алгоритм (или, можно сказать, входящие в СКИ), должны быть предельно четкими и однозначными. Их результат не может зависеть от какой-либо дополнительной информации извне алгоритма. Сколько бы раз вы не запускали программу, для одних и тех же исходных данных всегда будет получаться один и тот же результат.

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

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

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

Теперь пример другой ситуации. Рассмотрим алгоритм деления некоторого числа n "столбиком" на 3. При n=4,2 он благополучно получает результат, а вот для простейшего значения n=1 процесс деления оказывается бесконечным. Впрочем; достаточно дополнить алгоритм условием на количество требуемых в ответе знаков после запятой, и результативность немедленно будет восстановлена.

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

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

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

1   2   3   4   5   6   7   8



Скачать файл (1803 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации
Рейтинг@Mail.ru