Понятия информации

ПОНЯТИЯ ИНФОРМАЦИИ Измерение количества информации Понятие количества информации в статистической теории информации определяется на основе понятия вероятности, которое применяется для описания систем с неопределенностью. Если, скажем, в наших знаниях о каком-либо предмете существует неясность, неопределенность, а получив новые сведения об этом предмете, мы можем более определенно судить о нем, то это значит, что сообщение содержало в себе информацию. А это, в свою очередь, означает, что получение сообщения можно рассматривать как получение дополнительного знания, которое меняет существующую ранее картину. Если сообщение не даст ничего нового, не снимает неопределенности, то с позиций статистической теории в нем не содержится информации. Таким образом, в статистической теории под информацией понимаются сведения или сообщения, которые снимают существовавшую до их получения неопределенность. Степень неопределенности измеряется величиной, которую в теории информации называют энтропией (Н). Энтропия является функцией вероятности (р): Н = – lоg2 p. При р = 1 энтропия равна нулю, неопределенность полностью отсутствует. Количество информации определяется как разность между начальной энтропией (до получения сообщения) и конечной энтропией (после получения сообщения). В том случае, если в результате получения какого-то сообщения неопределенность полностью исчезает, количество информации (I) в этом сообщении равно энтропии: I=H. Количество информации, равное единице Н = 1, принято называть битом. Рассмотрим, например, какое количество информации содержит сообщение: “Не высовывайтесь из окна” (“Do not lean of the window”). Будем измерять количество информации, принимая, что каждая из 29 позиций в этом сообщении (английский вариант) должна быть заполнена одним из двадцати семи символов (26 букв латинского алфавита плюс пробел). Следует отметить, что вероятность появления каждого символа на каждой позиции, вообще говоря, не равна 1/27. Это связано с тем, что различные буквы латинского алфавита имеют различную частоту повторяемости в английском языке, а следовательно, и вероятность появления на каждой позиции. Кроме того, вероятность появления данной буквы на позиции зависит от сочетания букв на предшествующих позициях. Однако для простоты мы будем считать вероятность появления каждого символа равной 1/27. Количество информации, которое несет каждый символ на каждой позиции, равно 1 H = – log2 27 = – log2 1 + log2 27=log2 27 = 4,75 бита (на позицию). Общее количество информации, содержащееся в сообщении, можно определить как Н = 25 log2 27 = 119 бит (всего). Применим эту формулу для определения информации в этом же сообщении на других языках. количества Немецкий язык: Nicht hinaus lehnen - 90,4 бит, Французский язык: Ne penchez pas au dehors - 114 бит. Из этого примера видно, что для передачи одной и той же мысли используется различное количество информации. Все естественные языки обладают определенной информационной избыточностью, величина которой зависит от того, какой язык мы выберем в качестве эталона. Из 3-х языков, сообщение на которых мы рассмотрели, избыточность двух из них можно выразить относительно немецкого языка, считая его эталоном с точки зрения лаконичности. Но, допустим, было бы выработано международное соглашение о том, что все окна маркируются 0 или Х в зависимости от того, безопасно или нет высовываться из соответствующего окна, при этом вероятности выбора окон обоих типов были бы примерно равными. Тогда информация, содержащаяся в сообщении из символов 0 и Х, была бы равна всего 1 биту. В сравнении с этим сообщением даже немецкий вариант сообщения был бы весьма избыточным. В 1965 году академик А.Н.Колмогоров ввел принципиально новое алгоритмическое определение понятия количества информации. Алгоритмом обычно называют некоторую систему правил, предписаний, определяющих процесс или программу решения задачи. Идея, введенная Колмогоровым, заключается в том, что количество информации определяется как длина минимальной программы, позволяющей однозначно преобразовать один объект (множество исходных данных) в другой объект (множество результатов). Так, если имеется один объект (например, последовательность букв а,а,а,а) и второй объект - эта же последовательность, то длина программы, которую необходимо выполнить, чтобы преобразовать один объект во второй, оказывается равной нулю. Таким образом, программа измеряет степень тождества или степень различия двух объектов, выражая эту степень количеством команд, инструкций, которые необходимо реализовать, выполнив их в определенном порядке, чтобы перевести один объект в другой. Пусть исходный объект – А, конечный объект – В, тогда программу мы можем изобразить как функцию отображения Ф исходного объекта на конечный объект, или множество В, как это показано на рис. 1.1. Рис. 1.1. Функция отображения В этом случае множество А можно рассматривать как множество исходных данных, а В – как множество результатов. Чем больше различаются эти два множества, тем более длинной или сложной оказывается программа перехода от одного объекта к другому. Очевидно, если два множества состоят из одних и тех же элементов, например А={а, в, с} и В= {а, в, с}, то мощность множества Ф=, т.е. длина программы, а следовательно, и количество информации равны нулю. Здесь, как и в статистической теории, бит – это единица измерения количества информации. Если же шары в нашем примере не различаются по цвету, то говорят, что в этом отношении совокупность не содержит информации. Чем больше в совокупности отличных друг от друга элементов, тем больше, с точки зрения кибернетики, эта совокупность содержит информации. Можно сказать, что информация появляется, когда два объекта различаются, и исчезает, когда они становятся тождественными. Кибернетика прежде всего связана с проблемой управления. Поэтому кибернетику больше всего интересует преобразование, переработка информации, предназначенной для достижения определенной цели, связанной с управлением. Управление невозможно без восприятия, передачи, а самое главное – без переработки и преобразования информации. Информация, которой пользуются люди, обладает не только количественными характеристиками, но и содержанием, или значением. Причем для человека важно прежде всего значение информации, понимание того, что передается в сообщении. Однако, чтобы воспринять сообщение, принимающая информацию сторона должна обладать определенным запасом знаний. В экономических системах этот запас знаний может быть представлен в виде тезауруса – систематизированного словаря понятий с указанием смысловых связей между ними. Тогда вновь полученное сообщение будет по определенным критериям сопоставляться с тезаурусным, в результате чего принимается решение о наличии в нем значения или содержания для данной системы. Однако, если таковая даже не имеется, то может иметь место развитие или обогащение системы за счет добавления новых понятий и связей. Свойства экономической информации Характерной особенностью экономической информации является то, что она существует, в основном, в документированном виде. Документ является основным носителем информации в организационных экономических системах, т.е. системах, в которых имеет место организованное взаимодействие людей. В экономике документ служит основным средством регистрации различных событий в деятельности хозяйственного объекта. В нем отражается влияние многочисленных факторов, характеризующих экономическое явление или экономический объект. Поэтому документ представляет собой достаточно сложное информационное образование, требующее отдельного детального изучения при анализе информационных систем. Подход к изучению таких сложных объектов хорошо известен в науке. Он состоит в отыскании элементарной составляющей сложных образований или структур и всестороннего их изучения. Любой объект или явление в экономике обладает рядом характеризующих его свойств, выражающихся в параметрах, признаках или характеристиках. Например, свойствами такого объекта, как продукция, являются: наименование, класс, гарантия, предприятие-производитель, цена и т.д. А такой экономический объект, как торговая фирма, может характеризоваться следующими свойствами: наименование, адрес, номер банковского счета. Состав параметров, характеризующих конкретный объект, может меняться в зависимости от конкретной задачи. Так, приведенный в предыдущем примере перечень свойств фирмы может вполне удовлетворить среднего покупателя, но окажется недостаточным для налоговых органов. Кроме того, большинство свойств экономических сущностей могут изменяться, а следовательно, параметры, их описывающие, должны быть величинами переменными. Параметры, описывающие экономический объект или явление, целесообразно выбрать в качестве элементарных составляющих, из которых образуются более сложные структурные информационные образования, в том числе и документы. В экономических информационных системах эти параметры носят названия реквизитов или атрибутов. Причем, термин реквизит чаще применяется в документальных немашинных информационных системах (ИС), а термин атрибут используется в компьютерных ИС, связанных с базами данных. Другими синонимами атрибута и реквизита, часто встречающимися в литературе, являются такие термины, как элемент, терм и признак. Мы чаще будем пользоваться термином атрибут, понимая, что атрибуты – это элементарные единицы информации, из которых образуются более сложные составные единицы информации (СЕИ). Единицу информации любой сложности или СЕИ можно представить состоящей из атрибутов как из элементарных компонентов. Взаимосвязь и взаимообусловленность экономических объектов и явлений проявляется и в информации, т.к. одно и то же свойство может наблюдаться у разных экономических сущностей. Так, например, признак "дата" необходим для фиксации процесса труда, при отображении поступления материальных ценностей и во многих других случаях. Признак "шифр цеха" может фигурировать в сообщениях о поступлении сырья и материалов, в плановых документах и документах о премировании работников. Это говорит о том, что отдельный атрибут обладает определенной самостоятельностью и имеет характерные только для него свойства, и он может фигурировать в самых разнообразных СЕИ, относящихся к различным экономическим объектам и явлениям. Всесторонняя характеристика атрибута вне зависимости от его вхождения в различные СЕИ достигается с помощью свойства, которое называется формой атрибута. Форма атрибута определяет его полное наименование, другие имена-синонимы, включая сокращенные идентификаторы, типы и классы значений, ограничения, накладываемые на конкретные значения, признаки редактирования и т.д. Наименование, или имя атрибута, используется для однозначной его идентификации. Обычно это слово или группа слов, например "шифр цеха". При разработке информационных систем для компактного написания вместо полного наименования атрибута применяют часто имена-идентификаторы, которые закрепляются за атрибутами при использовании в различных задачах. Классом значений атрибута называется некоторое конечное множество значений, которое он может принимать. Например, атрибуты "гарантия" и "класс изделия" имеют вполне определенные конечные множества значений. Используя это понятие можно сказать, что значение атрибута есть в каждый заданный момент времени одна из позиций класса значений данного атрибута. Таким образом, каждый атрибут можно рассматривать с двух сторон: со стороны его формы (наименование) и со стороны содержания (класс значений), т.е. со стороны наименования строки или столбца документа и наличия определенного числа или текста, записанного в данную строку или столбец. В экономических системах наибольшее распространение получили числовой и текстовой типы атрибутов. Атрибуты численного типа характеризуют количественные свойства сущностей и носят название оснований. Атрибуты текстового типа выражают, как правило, качественные свойства сущностей и характеризуют обстоятельства, при которых имел место изучаемый процесс и были получены те или иные числовые значения. Эти атрибуты носят название признаков. Признаки, в свою очередь, подразделяются на индивидуальные и общие. Индивидуальные признаки указывают на те особенности, которыми одно явление отличается от других, т.е. с их помощью производится индивидуализация сообщения. Обобщающие признаки служат для представления таких свойств, которые могут послужить основой для обобщения. Несмотря на то, что признаки относятся к атрибутам текстового типа, их значениями могут являться не только последовательности букв и специальных знаков, но и последовательности цифр, например дата или табельный номер работающего. Все эти последовательности называются строками или текстом. Можно сказать, что полный набор попарно различимых символов данной информационной системы составляет ее алфавит. Частным случаем сообщения является показатель – составная единица информации, состоящая из одного атрибута-основания и ряда характеризующих его и связанных с ним логическими отношениями атрибутов-признаков. Таким образом, если продолжить сравнение атрибута с атомом вещества, то можно утверждать, что показатель подобен молекуле, которая является мельчайшей частицей вещества, отражающей его свойства. Можно выделить семь классов признаков, входящих в экономический показатель и описывающих объект и свойства экономического показателя: • формальная характеристика объекта показателя; • характеристика процесса производства; • характеристика объекта производства; • единицы измерения объектов; • взаимодействие "объект - субъект"; • время взаимодействия объектов; • функции управления. Эти признаки образуют, соответственно, семь классов признаков экономического показателя: К1 – К7. Каждый из этих классов может включать подклассы со свойствами предметов. Например, класс признаков "формальная характеристика объекта" К1 образует два подмножества: М1 – абсолютные показатели и М2 – относительные показатели. В классе "единицы измерения" К4 можно выделить следующие подклассы: • натуральные – М9; • трудовые – М10; • стоимостные – М11; • временные – М12. Общая схема классификации экономических показателей представлена на рис. 1.3. Рис.1.3. Схема классификации показателей Формы представления информации В информатике информация, представленная в формализованном виде, пригодном для автоматизированной обработки, носит название данных. Под автоматизированной обработкой понимается обработка информации на ЭВМ при возможном участии человека. Можно сказать, что данные – это компьютерное представление информации. Превращение информации в данные происходит в процессе кодирования информации, при котором любая информация превращается в совокупность "0" и "1". Для компьютерных систем можно считать, что информация – это смысл, который приписывается двоичным кодам. Данные являются исходным материалом для процессов обработки данных. В начале эти процессы обеспечивали только обработку текстов, а затем – изображений и звука. Развитие аппаратных и программных средств позволяет представлять в мультимедийной среде различные типы данных, проводить их интеграцию в Рис. 1.4.Формы единой технологии обработки данных. представления данных Это стало возможным благодаря представлению текста, речи и звука в виде изображений. Таким образом, различные формы представления данных образовали пересекающиеся множества (рис. 1.4.). Данные в информатике формируются в группы, образуя компоненты баз данных и баз знаний. Формы представления данных определяют и характер пользовательского интерфейса. Можно сказать, что формой обмена информацией, или пользовательским интерфейсом, является язык устного (звукового) и текстового взаимодействия, а также язык изображения. Технический прогресс в области вычислительной техники, а именно, возросшая внутренняя и внешняя память компьютеров, расширение их графических возможностей, появление лазерных дисков, повышение качества видеотехники и многое другое, позволили реализовать принципиально новый подход к традиционным формам представления информации. Обычно любая экономическая информация имеет форму плана, отчета, проекта. Как правило, эти документы содержат тексты, таблицы, графики. Информация, содержащаяся в них, при восприятии ее человеком представляется как одна длинная строка символов, читаемая лишь в одном направлении. Как ни парадоксально, но такое, привычное нам, представление информации является малоэффективным с точки зрения ассоциативной психологии. Ассоциативная психология – это теория, сводящая психологические процессы, прежде всего мышление, к ассоциации представлений. С позиций этой теории более эффективным является такое представление, при котором текст представляется как многомерная структура фрагментов, имеющих многочисленные связи друг с другом. Переходя по этим связям от одного фрагмента к другому, можно уточнять информацию об изучаемом объекте. Таким образом, информация, содержащаяся в каждом фрагменте, дополняется за счет связей с другими объектами. Такой способ размещения информации, основанный на принципах ассоциативного мышления, называется гипертекстом. Гипертекст – это такая форма организации, при которой весь информационный материал разделяется на фрагменты, в каждом из которых указываются связи с другими фрагментами. Связи между фрагментами устанавливаются на основе семантической, смысловой близости фрагментов. Переходя по указанным во фрагменте связям можно просматривать текстовой материал не только в одном направлении, а в любом выбираемом пользователем порядке. Следовательно, гипертекстовая технология заключается в многомерном представлении текста иерархической структурой типа сети. Под информационными технологиями принято понимать совокупность конкретных технических и программных средств, с помощью которых выполняются разнообразные операции по обработке информации во всех сферах жизнедеятельности человека. В настоящее время, под информационными технологиями, чаще всего, понимают компьютерные технологии, так как информационные технологии имеют дело с использованием компьютеров и программного обеспечения для хранения, преобразования, защиты, обработки, передачи и получения информации. Под получением информации подразумевается получение фактов, сведений и данных о свойствах, структуре или взаимодействии объектов и явлений окружающего нас мира. Предметное содержание информации позволяет уяснить ее основные свойства: • Достоверность. Под достоверной понимают информацию, не искажающую истинное положение дел. Очевидно, что недостоверная информация может привести к принятию неправильных решений. • Полнота. Полнота информации определяется ее достаточностью для понимания и принятия решений. Неполнота информации сдерживает принятие решений или может повлечь ошибки. • Ценность. Ценность информации зависит от того, какие задачи мы можем решить с ее помощью. • Актуальность. При работе в постоянно изменяющихся условиях важно иметь актуальную, т.е. соответствующую действительности, информацию. • Понятность. Информация становится понятной, если она выражена языком, доступным людям, для которых она предназначена. Вопросы и упражнения 1. Что понимается под термином «информатика»? 2. Дайте определение понятию «информационные технологии». 3. Какие свойства информации вы знаете? 4. Какие из следующих сообщений содержат, с вашей точки зрения, информацию: «Москва – столица нашей Родины», «Волга впадает в Каспийское море», «Осторожно, впереди ремонт дороги!», «Осенью часто идет дождь»? 5. Приведите примеры сообщений, составленных из знаков алфавита Н = р, т, о и несущих смысловую информацию. 6. Записать алфавит для следующих систем передачи информации: а) книгопечатание на русском языке; б) телеграф, использующий азбуку Морзе; в) управление гужевым транспортом; г) управление движением с помощью светофора. 7. Приведите примеры информации, заключенной в каких-либо отдельных общепринятых знаках. 8. Какие характеристики существенными для человека? информации являются 9. Каким образом можно оценить ценность информации в экономических системах? 10. В каком состоянии, с точки зрения кибернетики, находится любая система при отсутствии управления? 11. Что такое язык экономической информации и какие он использует алфавиты? 12. Что называется алфавитом конкретной информационной системы? 13. В чем отличие атрибута от реквизита и сколько нужно атрибутов, чтобы охарактеризовать объем выпускаемой цехом продукции? 14. Что отражает конкретное сообщение об объекте, из какого типа реквизитов оно состоит? 15. Какими преимуществами обладает показатель сравнению с другими единицами измерения объема данных? по 16. К какому типу атрибутов можно отнести: а) номер телефона; б) дата рождения; в) учебная дисциплина (предмет); г) оценка. 17. Какие из признаков могут не отражаться в документах и показателях? 18. Как подразделяются показатели в зависимости от способа их получения? 19. Какая информация экономической информатике? носит название «данные» в 20. Какое сообщение, с точки зрения статистической теории, содержит информацию? 21. Какая единица информации называется составной? 22. Какая из минимальных единиц информации обладает информативностью? 23. Что является основным носителем информации в экономических системах? 24. Сколько показателей должен содержать документ? 25. Что является формой атрибута? 26. Какой из атрибутов является основанием? 27. Какие существуют формы представления данных? 28. Какое представление информации эффективным для ассоциативного мышления? является 29. Какие возможности для организации представляют гипертекстовые технологии? более информации 2. ПРЕДСТАВЛЕНИЕ ИНФОРМАЦИИ В ВЫЧИСЛИТЕЛЬНЫХ МАШИНАХ 2.1. Системы счисления Совокупность приемов наименования и изображения количественных величин с помощью ограниченного набора знаков будем называть системой счисления. В настоящее время используются два вида систем счисления: позиционные и непозиционные системы счисления. Наиболее известной непозиционной системой счисления является римская система счисления. В ней запись различных целых количеств производится с помощью цифр I, V, X, L, C, D, M и т.д., обозначающих количества один, пять, десять, пятьдесят, сто, пятьсот, тысяча и т.д. Несколько стоящих подряд цифр изображают сумму количеств, обозначаемых этими цифрами. Например, II = I + I – два; XXX = X + X + X – тридцать. Пара цифр, в которой младшая цифра (обозначающая меньшее количество) стоит слева от старшей (обозначающей большее количество), изображает разность соответствующих количеств. Например, IV = V – I – четыре; XL = L – X – сорок; СM = M - C – девятьсот. Запись, состоящая из старшей цифры (или старшей группы цифр) и стоящей справа от нее младшей цифры (или группы цифр), изображает сумму количеств, отвечающих этим цифрам (или группам цифр). Например, XI = X + I – одиннадцать; XIV = X + IV – четырнадцать; XLIV = XL + IV – сорок четыре. Запись MCMXСVII расшифровывается следующим образом: MCMXСVII = M + CM + XС + VII, и означает число «одна тысяча девятьсот девяносто семь». Запись цифр в определенном порядке будем называть числом. Изображение чисел в римской системе счисления является весьма неудобным, что и объясняет ограниченное использование этой системы счисления в наше время. Рассмотрение позиционных систем счисления начнем с хорошо знакомой десятичной системы счисления. В этой системе для записи чисел используется десять различных знаков – цифр: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Цифры обозначают количества от нуля до девяти. Количество, равное десяти, требует уже для своей записи две цифры "10". Остальные количества записываются числами, представляющими собой последовательности цифр, разделенных запятой на целую и дробную части. Десятичную систему называют позиционной потому, что значение количеств, изображаемых одной и той же цифрой, меняется в зависимости от ее положения в числе. Так, например, в числе 214252 двойка, стоящая на первой позиции, означает количество единиц, на третьей позиции – количество сотен, а на шестой – количество сотен тысяч (позиции считаются справа налево). Таким образом, каждой позиции числа, на которой может находиться любая из цифр, приписано определенное значение или вес. В десятичной системе счисления вес первой позиции равен единице, второй – десяти, третьей – ста и т.д. Поэтому, чтобы определить количество, изображенное данным числом, необходимо каждую цифру умножить на вес данной позиции и полученные произведения сложить: 2  100000 + 1  10000 + 4  1000 + 2  100 + 5  10 + 2  1. Десятичная система счисления настолько вошла в нашу жизнь, что подобный расчет мы не производим, а непосредственно определяем количество по самой записи числа. Однако, если мы увидим приведенное в примере число на табло, отображающем время, мы прочитаем его как 21 час 42 минуты и 52 секунды. На самом деле это число изображает количество секунд, прошедших с начала су- ток. Чтобы определить это количество, мы должны проделать следующий расчет: 2  36000 + 1  3600 + 4  600 + 2  60 + 5  10 +2  1 = 78172 (сек). Из этого примера видно, что одно и то же число изображает различные количества, поэтому для определения количества по данной записи числа необходимо знать еще и веса, которые приписаны каждой позиции. Номер позиции в числе будем называть разрядом. В общем случае число, записанное в произвольной системе счисления, можно представить в виде: x(n) x(n−1) ... x(2) x(1) x(0), x(−1) x(−2) ... x(−k). В этой записи номер позиции для младшей цифры целой части принят за нуль. Весовое же значение этой позиции в любой системе счисления будет равно единице. Для определения количества, которое оно изображает, представим его в виде многочлена: x(n)  P(n)+x(n−1)  P(n−1)+x(n−2)  P(n−2)+...+x(2)  P(2)+x(1)  P(1)+ n +x(0)  P(0) +x(-1)  P(−1)+...+x(−k)  P(−k) =  x(i)  P(i) i= −k , где x(i) – цифры, а P(i) – веса соответствующих разрядов числа. В нашем примере: x(5) = 2, x(4) = 1, x(3) = 4, x(2) = 2, x(1) = 5, x(0) = 2. Веса в десятичной системе счисления будут иметь значения: P(5) = 100000, P(4) = 10000, P(3) = 1000, P(2) = 100, P(1) = 10, P(0) = 1, а в случае с часами, когда та же самая запись числа отображает время, значения весов будут следующие: P(5) = 36000, P(4) = 3600, P(3) = 600, P(2) = 60, P(1) = 10, P(0) = 1. При записи различных чисел в одной и той же позиционной системе счисления значения цифр меняются, а весовые значения разрядов числа, т.е. их веса, остаются постоянными. Любое число в позиционной системе представляет собой совокупность символов-цифр, записанных в определенной последовательности. Количество цифр, используемых в системе счисления, называется ее основанием p. Каждая цифра x может отображать целые количества от 0 до p−1: 0  x  p−1. Теперь мы можем в общем виде сформулировать правило определения количества, отображаемого числом X, в любой позиционной системе счисления. Чтобы определить количество, отображаемое данным числом X, X= x(k) x(k−1) ... x(0) x(−1) x(−2) ... x(−c), необходимо значение каждой цифры умножить на весовое значение данной позиции и полученные произведения сложить: X = x(k)  P(k) + x(k-1)  P(k−1) + ... + x(0)  P(0) + x(-1)  P(−1) + ... + k + x(−c)  P(−c) =  x(i)  P(i) . i= − с Полученная запись носит название многочленной формы представления числа. Она позволяет определить количество, отображаемое данным числом, выраженное в десятичной системе счисления. Другими словами, представив число в системе счисления с любым основанием в форме многочлена, мы можем определить, какое количество отображает данное число в десятичной системе счисления. Большинство позиционных систем счисления строится таким образом, что последовательность весовых значений позиций цифр в числе образует геометрическую прогрессию со знаменателем, равным основанию системы счисления p: P = pi . В таких случаях в каждую i-ю позицию, или разряд числа, можно записать следующее количество R: 0  R  (p−1) • pi . Для записи количества K, превышающего верхнюю границу iго разряда, K > (p−1), значение следующего разряда увеличивается на единицу: x(i+1) = x(i+1) + 1, а в данный i-й разряд записывается значение: x(i) = K − p. Замечание. В качестве цифр различных систем счисления используются цифры десятичной системы счисления и буквы латинского алфавита. Для записи количеств равных или превышающих десять, используются следующие символы: 10 = A, 11 = B, 12 = C, 13 = Д и т.д. Примером позиционной системы счисления является хорошо знакомая нам десятичная система счисления. Весовые значения последовательности разрядов числа в ней образуют ряд членов геометрической прогрессии со знаменателем, равным десяти. Число необходимых символов для записи единиц, сотен, тысяч и т.д. также равняется десяти: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Произвольное число M = x(n) x(n−1) ... x(2) x(1) x(0) ... x(−k) в десятичной системе счисления отображает количество, которое можно определить следующим образом: M = x ( n)  10 n + x ( n − 1)  10 n − 1 ... x (2)  10 2 + x (1)  10 1 + x ( 0)  x 0 + + x ( −1)  10 −1 + ... + x ( − k )  10 −k n =  x(i)  10 . i i= −k B десятичной системе счисления максимальное количество, которое может быть записано с помощью одной цифры, равняется девяти. Большие количества требуют записи в следующие разряды, т.е. требуют дополнительных цифр. Количество цифр в десятичной системе счисления можно объяснить тем, что в качестве первого приспособления для счета человек использовал собственные руки, имеющие десять пальцев. По тем же принципам, по которым построена десятичная система счисления, строится система счисления, имеющая произвольное количество цифр. Допустим, в системе счисления используется p цифр. Эти цифры должны отображать количества от 0 до p-1. Количество, равное p, должно записываться в следующий по старшинству разряд цифрой, отображающей количество, равное единице. Для этого весовые значения последовательности разрядов в позиционной системе счисления с основанием p должны образовывать ряд членов геометрической прогрессии со знаменателем, равным p. Тогда произвольное число M = x(n) x(n−1) ... x(0), x(−1) x(−2) ... x(−k) в системе счисления с основанием p означает количество, которое может быть определено следующим образом: M = x(n)  p n + x(n−1)  pn-1 + ... + x(2)  p2 + x(1)  p1 + x(0)  p0 + n + x(−1)  p-1 + ... + x(−k)  p-k =  x(i)  pi , i= -k где x(i) – цифры, а p – основание системы счисления, т.е. количество используемых цифр. Следовательно, мы можем сделать вывод о том, что отображаемые одной цифрой количества являются целыми и лежат в диапазоне 0  x(i)  p−1. Рассмотрим, как можно использовать эти общие положения в создании конкретной позиционной системы счисления. Допустим, нам необходимо построить восьмеричную систему счисления. Основание системы счисления в этом случае равно восьми (p = 8). Максимальное количество, которое может быть отображено с помощью цифр в этой системе счисления, равно семи, а первые восемь цифр десятичной системы счисления – 0, 1, 2, 3, 4, 5, 6, 7. Тогда, например, число 256, записанное в восьмеричной системе счисления, в десятичной системе счисления будет означать количество, равное 256(8) = 2  8 2 + 5  8 1 + 6  8 0 = 128 + 40 + 6 = 174(10). Индексы в скобках означают основания систем счисления. При построении шестнадцатеричной системы счисления основанием системы счисления будет количество, равное шестнадцати. Поэтому для записи цифр в этой системе счисления необходимо шестнадцать символов. Возьмем в качестве символов, обозначающих количества от нуля до девяти, цифры десятичной системы счисления: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Для обозначения количеств от десяти до пятнадцати воспользуемся символами A, B, C, D, E, F соответственно. Тогда число B5F(16), записанное в шестнадцатеричной системе счисления, будет означать количество, которое в десятичной системе счисления можно определить следующим образом: B5F(16) = 11  16 2 + 5  16 1 + 15  16 0 = 2911(10). Минимальным целым положительным числом, которое может служить знаменателем геометрической прогрессии, является два. Следовательно, два – это минимальное количество, которое может служить основанием системы счисления. В этой системе счисления, которая носит название двоичной, всего две цифры – 0 и 1. Тем не менее, в этой системе счисления может быть записано любое количество. Так, число 1011(2) означает количество, которое можно записать в десятичной системе счисления следующим образом: 1011(2) = 1  2 3 + 0  2 2 + 1  2 1 + 1  2 0 = 11(10). Из сравнения позиционных систем счисления с различными основаниями можно сделать вывод о том, что чем больше основание системы счисления, тем меньше требуется разрядов для записи одного и того же количества, более компактна запись числа. Однако набор цифр, используемых для записи чисел, при этом увеличивается. С точки зрения технической реализации записи и хранения чисел наиболее привлекательной является двоичная система счисления. Это объясняется тем, что при технической реализации записи и хранения чисел каждой цифре должно соответствовать определенное состояние физического элемента. Для того, чтобы записать любую цифру в двоичной системе счисления, требуется физический элемент, имеющий всего два различимых состояния. Так, наличие или отсутствие пробивки на перфокарте или перфоленте или намагничивания в определенной позиции магнитного носителя, наличие или отсутствие сигнала любой физической или иной природы может трактоваться, соответственно, как запись "1" или "0". Арифметические операции в различных системах счисления выполняются по тем же правилам, что и в десятичной системе счисления. Так, если при выполнении операции сложения двух целых чисел X = x(n) x(n−1) ... x(i) ... x(2) x(1) x(0), x(-1) … x(-k) и Y = y(n) y(n−1) ... y(i) ... y(2) y(1) y(0), y(-1) … y(-k) результат поразрядного сложения в каждом разряде меньше основания системы счисления, т.е. x(i) + y(i) < p, где i = -k, …, -1, 0,1,2,...n, а p – основание системы счисления, то в i-й разряд суммы z(i) записывается цифра, которая отображает количество, равное z(i) = x(i) + y(i). В том случае, если результат поразрядного сложения больше основания системы счисления или равен ему, т.е. x(i) + y(i)  p, то в i-й разряд суммы записывается цифра, которая отображает количество, равное z(i) = x(i) + y(i) − p. При этом в следующий разряд суммы z(i+1) переносится единица, которая должна учитываться при суммировании в (i+1)-м разряде. Операция вычитания является обратной к операции сложения. Поэтому при вычитании числа Y из числа X поступают по аналогичным правилам. То есть, если разряд вычитаемого меньше разряда уменьшаемого x(i) > y(i), то в i-й разряд частного записывается цифра, которая означает количество r(i) = x(i) − y(i). Если разряд вычитаемого будет больше разряда уменьшаемого, то в i-й разряд частного записывается цифра, обозначающая количество, равное r(i) = x(i) + p − y(i), а значение старшего разряда x(i+1) уменьшается на единицу. Читателям предлагается самостоятельно изобразить правило вычитания с помощью блок-схемы алгоритма вычитания. Операции умножения и деления, как известно, выражаются через операции сложения и вычитания аналогично тому, как это дела- ется в десятичной системе счисления. Поэтому разбор этих операций оставляем за читателем. Мы же рассмотрим выполнение операций сложения и вычитания на примере шестнадцатеричной системы счисления. Пусть X = 2FC(16), а Y = A3F(16). Тогда сумма X + Y будет определяться следующим образом: 2 F C + A 3 F D 3 B При поразрядном сложении C и F получается количество 27. Это количество не может быть записано с помощью цифр шестнадцатеричной системы счисления, т.е. возникает единица переноса в старший разряд. Следовательно, количество, которое будет записано в младшем разряде, равно 27 − 16 = 11, т.е. B. Во втором разряде результат поразрядного сложения цифр с учетом единицы переноса из младшего разряда имеет вид: 15 + 3 + 1 = 19. Этот результат также больше основания системы счисления. Поэтому во второй разряд суммы запишется величина 19 − 16 = = 3, и появится единица переноса в третий разряд. С учетом этой единицы переноса в старшем разряде суммы должно быть отображено количество 10 + 2 + 1 = 13. Это количество меньше основания системы счисления и может быть записано цифрой D. По аналогии определим разность шестнадцатеричных чисел Y и X: A 3 F - 2 F C 7 4 3 Операции умножения и деления рассмотрим на примере восьмеричной системы счисления. Для определения частных поразрядных произведений составим таблицу умножения (табл.2.1). В этой таблице номера строк и столбцов соответствуют значениям сомножителей. Значения произведений по заданным значениям сомножи- телей находятся на пересечении соответствующих строк и столбцов. Наиболее просто арифметические операции выполняются в двоичной системе счисления. Эта простота вызвана тем, что в двоичной системе счисления всего две цифры 0 и 1. Следовательно, максимальное количество, которое может быть записано в каждом разряде, равно одному. Количество, равное двум, записывается как 10. Таблицы сложения, вычитания и умножения двоичных чисел весьма просты. Каждая из них состоит всего из четырех строчек (табл.2.2, 2.3 и 2.4). Таблица 2.1 Восьмеричная таблица умножения 1 2 3 4 5 6 7 10 1 1 2 3 4 5 6 7 10 2 2 4 6 10 12 14 16 20 3 3 6 11 14 17 22 25 30 4 4 10 14 20 24 30 34 40 5 5 12 17 24 31 36 43 50 6 6 14 22 30 36 44 52 60 7 10 7 10 16 20 25 30 34 40 43 50 52 60 61 70 70 100 Таблица 2.2 Таблица 2.3 Таблица 2.4 Двоичная таблица сложения Двоичная таблица вычитания Двоичная таблица умножения 1 1 + + + + 1 1 = = = = 1 1 10 1 1 10 − − − − 1 1 = = = = 1 1 1 1 • • • • 1 1 = = = = 1 С помощью этих таблиц операции сложения, вычитания, умножения и деления двоичных чисел выполняются так же, как и в десятичной системе счисления. Пример: + 1 Сложение: 1 1 0 1 1 0 1 1 1 0 1 1 0 0 1 0 0 0 1 1 Умножение: 1 1 1 0 х 1 1 1 1 1 0 + 1 1 1 0 1 1 + 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 - 1 0 0 1 0 - 1 0 Вычитание: 1 1 0 1 1 0 1 1 1 0 1 1 0 − 1 1 0 1 1 1 Деление: 1 1 1 0 1 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 1 0 1 0 1 1 0 1 1 - 1 0 0 1 1 0 0 1 - 1 0 0 1 0 0 0 0 Что касается умножения, то его можно выполнять как со сдвигом частичных произведений влево (умножение производить с младших разрядов множителей), так и со сдвигом вправо (получая частичные произведения при умножении начиная со старших разрядов множителей). Общее произведение в этом случае не изменится. Предлагаем читателям убедиться в этом самостоятельно. Простота выполнения арифметических операций в двоичной системе счисления делает эту систему счисления особо привлекательной с точки зрения технической реализации. Перевод чисел в различные системы счисления Перевод целых чисел Пусть целое число N задано в p-ичной системе счисления. Необходимо это число перевести в систему счисления с основанием q, где q – это запись основания новой системы счисления в системе счисления с основанием p. Допустим, что изображение числа N в q-ичной системе счисления найдено и имеет вид: N = a(k)  q k+ a(k−1)  q k-1 +...+ a(1)  q1 + a(0)  q0, где a(k), ... , a(0) – цифры q-ичной системы счисления. Заменим в правой части этого выражения цифры a(k), ... , a(0) их p-ичными изображениями b(k), b(k-1), ... , b(0), получим N = b(k)  q k + b(k−1)  q k-1 + ... + b(1)  q 1 + b(0)  q0. Разделив обе части этого равенства на q, имеем N/q = b(k)  q k-1 + b(k−1)  q k-2 + ... + b(0)  q -1, где b(0)  q−1 = b(0)/q представляет собой правильную дробь. Из полученного равенства видно, что при делении числа N на q остаток равен b(0), а частным будет: N1 = b(k)  q k-1 + b(k−1)  q k-2 + ...+ b(1). Если теперь частное N1 разделить на q, то получим в остатке b(1), а новое частное будет равно: N2 = b(k)  q k-2 + b(k−1)  q k-3 + ... + b(2). Выполняя процесс деления k раз, мы последовательно найдем в качестве остатков все цифры b(0), b(1), ..., b(k−1), причем последнее частное будет иметь вид N(k) = b(k). Следовательно, путем последовательного деления числа N и его частных на q получим в виде остатков деления p-ичные записи q-ичных цифр (начиная с младшей), нужных для изображения числа. Последовательное деление производят до тех пор, пока не получится частное, меньшее, чем q. Это последнее частное представляет собой старшую q-ичную цифру числа N. Таким образом, для перевода целого числа из одной позиционной системы в другую необходимо это число разделить на основание новой системы счисления, записанное в старой системе счисления. Остаток, полученный в результате этого деления, представляет собой младшую цифру числа в новой системе счисления, записанную в старой системе счисления. При делении полученного частного от первого деления получают в качестве остатка следующую цифру числа в новой системе счисления. В результате последующих делений вновь получаемых частных на основание новой системы счисления последовательно получают цифры числа вплоть до старшей, которая является последним частным, меньшим основания новой системы счисления. Деления выполняют в старой системе счисления. Деление производят нацело до получения остатка до тех пор, пока последнее частное не окажется меньше основания новой системы счисления. Пример: Требуется десятичное число 191 перевести в двоичную, восьмеричную и шестнадцатеричную системы счисления. а) 1 9 1 - 1 9 0 2 9 5 1 - 9 4 2 4 7 1 - 4 6 2 2 3 1 - 2 2 2 1 1 1 - 1 0 2 5 1 - 4 2 2 1 - 2 2 1 Двоичная запись десятичного числа 191 имеет вид 10111111. б) 1 9 1 - 1 8 4 8 2 3 7 - 1 6 8 2 7 Восьмеричная запись десятичного числа 191 равна 277. в) 1 9 1 - 1 7 6 1 5 1 6 1 1 1 1 = B 1 5 = F В шестнадцатеричной системе счисления десятичное число 191 будет равно BF. Перевод дробей Пусть Q – правильная p-ичная дробь. Допустим, что найдена ее q-ичная запись, которая имеет вид: Q = a( −1)  q−1 + a( −2)  q−2 + a( −3)  q−3 + . . . , где a(−1), a(−2), a(−3), ... – q-ичные цифры, а q - основание новой системы счисления, записанное в старой системе счисления. Заменяя в правой части этого равенства цифры a(−1), a(−2), a(−3) ... их p-ичными изображениями b(−1), b(−2), ... , получим Q = b ( −1)  q −1 + b ( −2)  q −2 + b ( −3)  q −3 + ... Умножая обе части полученного равенства на q, имеем: Q  q = b ( −1) + b ( −2)  q −1 + b ( −3)  q −2 + .... Целая часть полученного в результате умножения числа равна b(−1), а его дробной частью является Q1 = b(−2)  q −1 + b(−3)  q −2 + b(−4)  q −3 ... Умножая новую дробь Q1 на q, мы получим число, целая часть которого дает нам b(−2), а дробная часть имеет вид Q2 = b(−3)  q −1 + b(−4)  q −2 + b(−5)  q −3 + .... Повторяя процесс умножения нужное число раз, мы найдем одну за другой q−ичные цифры для изображения числа Q в p−ичной записи. Следовательно, путем последовательного умножения числа Q и дробных частей получающихся произведений на q, имеем в виде целых частей этих произведений p−ичные записи q−ичных цифр, необходимых для изображения правильной дроби Q. Таким образом, перевод дробей производится последовательным умножением исходной дроби и дробных частей вновь получаемых произведений на основание новой системы счисления, записанное в старой системе счисления. Действия выполняются в исходной системе счисления до получения заданной точности или нулевой дробной части. Получаемые в результате умножения целые части произведений образуют последовательность цифр после запятой числа в новой системе счисления. Проиллюстрируем на примере данный способ перевода правильных дробей. Допустим, дана десятичная дробь 0,6875. Требуется найти ее двоичное, восьмеричное и шестнадцатеричное изображение (рис.2.3). а) 10 →2 0, 6875 х2 1, 3750 х2 0, 7500 х2 1, 5000 х2 1, 0000 б) 10 →8 0, 6875 х8 5, 5000 х8 4, 0000 в) 10 →16 0, 6875 х 16 11, 0000 11=В Двоичная запись исходной дроби имеет вид: 0,1011. Восьмеричная запись исходной дроби имеет вид: 0,54. Шестнадцатеричная запись исходной дроби имеет вид: 0,B. Если исходное число представляет собой неправильную дробь, то отдельно переводят дробную и целую части, а результат объединяют. Перевод целых чисел в том случае, когда основание одной системы счисления является целой степенью основания другой Если p и q – основания систем счисления, причем p = q k (p, q, k – целые числа), то для перевода числа из p-ичной системы в q-ичную каждую цифру p-ичной системы счисления заменим ее k-значным изображением в q-ичной системе счисления. Проиллюстрируем это правило на примере перевода чисел из восьмеричной системы счисления в двоичную (2 3 = 8). Пусть b(n), b(n − 1), ... , b(−m) обозначают цифры системы счисления с основанием восемь (т.е. под каждой из этих букв понимают цифру от 0 до 7). Для удобства примем десятичную запись для оснований восемь и два, а также для показателей степеней. Рассмотрим восьмеричное число: N = b(n) b(n−1)...b(0) = b(n)  8 n+b(n−1)  8 n-1+...+ b(1)  8+b(0). Предположим, что нам удалось найти его двоичную запись: N' = a(k), a(k−1), ... ,a(0) = a(k)  2 k+a(k−1)  2 k-1+...+ a(1)  2+a(0). Так как эти записи изображают одно и то же число, то N = N'. При делении обеих величин N и N' на 8 (с учетом того, что 8 = 23) получим одинаковые остатки и одинаковые частные, т.е. будем иметь: b(0) = a(2)  2 2 + a(1) b(n)  2 + a(0) = a(2) a(1) a(0);  8 n-1 + b(n−1)  8 n-2 + ... + b(2)  8 + b(1) = a(k)  2 k-3 + + a(k−1)  2k-4 + ... + a(5)  2 2 + a(4)  2 + a(3). Из последующего равенства, полученного таким же путем, имеем b(1) = a(5)  2 2 + a(4)  2 + a(3) = a(5) a(4) a(3). Каждое последующее деление будет давать равенство следующей восьмеричной цифры тройке двоичных цифр. Следовательно, для перевода восьмеричного числа в двоичную систему счисления нужно каждую восьмеричную цифру заменить равным ей трехзначным двоичным числом. Это правило сохраняет силу и для перевода восьмеричных дробей в двоичные. Для того, чтобы осуществить перевод числа из двоичной системы счисления в восьмеричную, необходимо, начиная от запятой, влево и вправо от нее разбить набор двоичных цифр, изображающих число, на тройки цифр; каждое полученное трехзначное число заменить равной ему восьмеричной цифрой. Если правая и левая группы цифр не будут полными тройками, их дополняют соответственно справа и слева нулями. Пример: Требуется перевести восьмеричное число 72,36 в двоичную систему счисления. Для этого заменяем каждую восьмеричную цифру ее двоичным эквивалентом: 7 = 111; 2 = 010; 3 = 011; 6 = 110. Следовательно, 72,36(8) = 111 010, 011 110(2). Пример: Решим обратную задачу, переведем двоичное число 1101101,00111 в восьмеричную систему счисления. Для этого дополним наборы двоичных цифр вправо и влево от запятой нулями так, чтобы количество цифр в наборах было кратно трем: 1101101,00111 = 001 101 101,001 110. Заменим теперь каждую восьмеричными эквивалентами: тройку двоичных цифр их 001 = 1; 101 = 5; 101 = 5; 001 = 1; 110 = 6. Следовательно, 110101,00111(2) = 155,16(8). Аналогичным образом переводятся числа из шестнадцатеричной в двоичную систему счисления и обратно. Только в этом случае каждой шестнадцатеричной цифре соответствует четыре двоичных разряда, т.к. 16 =2 4. Рассмотренные способы перевода чисел в двоичную систему счисления позволяют упростить перевод в эту систему счисления десятичных чисел. Для этого десятичные числа сначала преобразуют в восьмеричные, а затем от восьмеричной записи переходят к двоичной. Этот, казалось бы, более сложный путь в действительности является более коротким. Пример: Требуется десятичное число 725,9375 перевести в двоичную систему счисления. Перевод числа в восьмеричную систему счисления: 725 -720 5 8 90 -88 2 8 11 8 3 8 1 0, 9375 х8 7, 5000 х8 4, 0000 Восьмеричная запись исходного числа: 1325,74. Перевод восьмеричного числа в двоичное: 1011010101,1111. В общем случае, когда основание новой системы счисления является целой степенью k основания старой системы счисления, перевод числа в новую систему счисления состоит в замене каждых "k" цифр справа и слева от запятой в старой записи числа одной цифрой в новой системе счисления, отображающей то же количество. Обратный перевод состоит в соответствующей замене одной цифры в старой системе счисления "k" цифрами новой системы счисления. Использование представления числа в форме многочлена для перевода чисел в десятичную систему счисления Для того, чтобы определить количество, отображаемое числом в любой позиционной системе счисления, необходимо значение каждой цифры умножить на весовое значение ее позиции и полученные произведения сложить. Это положение иногда целесообразно использовать при переводе чисел в десятичную систему счисления, когда степени, в которые возводятся основания, невелики. Способы представления чисел в памяти ЭВМ Естественное представление чисел в виде целой и дробной частей имеет ряд недостатков, т.к. при выполнении вычислений на ЭВМ необходимо заранее знать количество разрядов, которое надо отводить для представления целых и дробных частей исходных данных и результатов, что бывает весьма трудно сделать в реальных условиях. При естественном представлении чисел для каждой двоичной цифры отводится один разряд в памяти вычислительной машины. Совокупность разрядов для записи числа носит название ячейки памяти. Естественное представление числа требует, чтобы некоторое постоянное количество разрядов отводилось для хранения дробной части, а остальные – для хранения целой части числа. Для изображения знака числа в машине приняты следующие обозначения: " + " = 0; " − " = 1. Схематичное изображение ячейки памяти при записи чисел с фиксированной точкой представлено на рис.2.3. В этой ячейке запятая (точка) фиксирована после четвертого разряда. Сама точка в ячейке не записывается. Фиксированное положение точки при естественном представлении чисел определяет то, что такое представление числа носит название "С фиксированной точкой". При выполнении арифметических операций с фиксированной точкой могут получаться результаты, целая часть которых содержит больше цифр, чем число разрядов ячейки, отведенных для хранения целой части. При этом происходит переполнение разрядной сетки. Чтобы избежать этого, необходимо все величины, входящие в решаемую задачу, умножить заранее на множители, подобранные с таким расчетом, чтобы в процессе вычислений разрядная сетка не переполнялась. Эти множители носят название масштабных коэффициентов. Подбор масштабных коэффициентов представляет собой нелегкую работу, для упрощения которой в большинстве ЭВМ запятая фиксируется непосредственно после знакового разряда (рис. 2.4). При таком представлении в ячейке могут быть записаны только правильные дроби. Превращение всех величин, фигурирующих в решаемой задаче, в правильные дроби достигается предварительным выбором масштабных коэффициентов. Представление чисел с фиксированной точкой в виде правильных дробей имеет ряд пре- имуществ при выполнении арифметических операций. Так, при сложении двух чисел переполнение может произойти только на один разряд, возникнет единица переноса в знаковый разряд. Чтобы зафиксировать результат переполнения, для записи знака числа надо отводить не один, а два разряда: " + " = 00; " − " = 11. В этом случае при переполнении в знаковых разрядах результата будут записаны противоположные значения: "01" или "10". Переполнения разрядной сетки при выполнении операции умножения вообще никогда не произойдет, т.к. перемножение двух правильных дробей всегда в результате дает правильную дробь. Однако выполнение операций с фиксированной точкой сопровождается серьезным неудобством – необходимостью использования масштабных коэффициентов. Знак числа Целая часть Дробная часть 1 5 2 3 4 6 7 8 9 номера разрядов Рис. 2.3. Схематичное изображение ячейки памяти при записи чисел с фиксированной точкой Знак числа Дробная часть 1 2 3 4 5 6 7 8 9 Рис. 2.4. Схематичное изображение ячейки памяти при записи чисел с точкой, фиксированной после знакового разряда Эти трудности можно устранить, если каждая ячейка памяти машины, кроме знаковых и цифрового разрядов, будет иметь и не- которое количество разрядов, образующих указатель положения точки (рис.2.5). Знак числа Дробная часть 1 2 3 4 Указатель положения точки 5 6 Знак порядка 7 8 9 Порядок Рис. 2.5. Схематичное изображение ячейки памяти при записи чисел с плавающей точкой Чтобы уяснить себе, как изображаются числа в такой ячейке, рассмотрим произвольное число N. Это число всегда может быть представлено в виде: N = m  q p, где q – основание системы счисления, |m| < 1, а p – целое. Например, десятичное число 364,78 может быть представлено как 364,78 = 0,36478  10 3 = 0,036478  10 4 = 0,0036478  10 5 Двоичное число 1101,1001 может также быть представлено в виде: 1101,1001 = 0,11011001  10 100 = 0,011011001  10 101 (основание системы счисления и показатель степени записаны в двоичной системе счисления). Такое представление чисел носит название записи "с плавающей точкой". Из приведенных примеров видно, что при записи числа с плавающей точкой его дробная часть, которая носит название мантиссы (m), может содержать много нулей между точкой и первой значащей цифрой. Поэтому, в целях экономии разрядов ячейки памяти машины для представления мантиссы, ее надо записывать так, что- бы после точки стояла значащая цифра, а не нуль, с соответствующей коррекцией порядка числа p. Такая запись числа носит название нормализованной. Следовательно, запись числа в виде N = m  q p называется нормализованной, если 1/q  |m| < 1. Все числа с плавающей точкой хранятся в памяти ЭВМ в нормализованном виде. Если в результате выполнения арифметических операций получается ненормализованное число, то оно подлежит обязательной нормализации. Следует отметить, что использование такого представления чисел очень удобно, когда их значения изменяются в очень широком диапазоне. При сложении мантисс двоичных чисел может быть получен ненормализованный результат, который устраняется сдвигом мантиссы влево на такое количество разрядов, при котором первой цифрой после запятой станет единица. Умножение чисел, представленных в форме с плавающей точкой, аналогично умножению чисел, представленных в форме с фиксированной точкой, с той лишь разницей, что необходимо еще определить порядок произведения алгебраическим сложением порядков сомножителей. Кроме того, может возникнуть необходимость в нормализации результата. Деление двоичных чисел, представленных в форме с плавающей точкой, предусматривает выполнение следующих действий: • определение знака частного сложением знаковых разрядов делимого и делителя; • определение значения и знака порядка частного вычитанием из порядка делимого порядка делителя; • деление абсолютных значений мантисс по аналогии с делением чисел, представленных в форме с фиксированной точкой; • проверка возможности появления и устранение нарушений нормализации. В некоторых моделях ЭВМ вместо знака порядка и самого порядка используется характеристика. Под характеристикой (x) понимается "смещенный порядок", полученный в результате прибавления к порядку целого положительного числа, называемого смещением (E), т.е. x = p + E. Для моделей ЕС ЭВМ смещение равно 64, а диапазон порядка изменяется от −64 до +63. Следовательно, при характеристике, рав- ной 0, порядок числа будет равен −64, а характеристика, равная 127, означает порядок +63. Рассмотрим в общем случае границы диапазона чисел, представляемых в памяти вычислительной машины. Пусть задано число с фиксированной точкой. Для его хранения отведено n разрядов для записи целой части и k разрядов для записи дробной части. Очевидно, что самое большое положительное число, которое можно записать в такой ячейке, равно: 11...111,11...1 = 100...0,00...0 − 0,00...01 = 2 n − 2 -k , а самое малое положительное число равно: 00...0,0...01 = 2 -k . Таким образом, диапазон чисел, представляемых в ячейке ЭВМ при их записи с фиксированной точкой, определяется неравенством: 2 -k  N  2 n − 2 -k. Подсчитаем для общего случая границы диапазона чисел, записываемых с плавающей точкой. Пусть p − число разрядов ячейки, отведенных для абсолютной величины порядка. Самым большим положительным числом, которое можно записать в такой ячейке, будет p-1 2 0,11...111  10 11...1 = (1 − 2 -p)  2 . Самым малым нормализованным числом, представленным в рассматриваемой ячейке, будет: 0,10...0  10 -11...1 =2 -1 2 -2 =2 p+1 -2 p . Диапазон чисел, представленных в ячейке с плавающей точкой, характеризуется неравенством 2 p -2  |N|  (1 − 2 ) -p 2 p-1 2 . При анализе выполнения арифметических операций в различных системах счисления мы пришли к выводу, что наиболее просто эти операции выполняются в двоичной системе счисления. Наиболее длительными арифметическими операциями являются операции умножения и деления, т.к. при их выполнении необходимо подсчитывать частичные произведения с последующим их сложением или вычитанием. В двоичной системе счисления частичные произведения являются результатом умножения либо на нуль, либо на единицу. Поэтому операция умножения в этой системе счисления сводится к перезаписи и сдвигу множимого с последующим суммированием, а операция деления – к перезаписи и сдвигу с последующим вычитанием. Таким образом, чтобы реализовать выполнение всех арифметических операций на ЭВМ, необходимо иметь устройства, выполняющие сдвиг чисел, и устройства для сложения и вычитания чисел. Чтобы сократить количество устройств, необходимых для выполнения арифметических операций, рассмотрим, каким образом операция вычитания двух чисел может быть заменена операцией сложения. Операция вычитания двух положительных чисел эквивалентна операции алгебраического сложения положительного числа с отрицательным: a − b = a + (−b), a  0, b < 0. Для чисел, представленных в форме с фиксированной точкой после знакового разряда, диапазон возможных значений лежит в интервале от −1 до +1. Причем отрицательные числа лежат в диапазоне от − 1 до 0. Чтобы избавиться от отрицательных чисел, переместим область их значений из интервала (−1,0) на числовой оси в интервал (+1, +2), (в двоичной записи (+1,+10)) таким образом, чтобы граница интервала −1 совпала с +1, а граница 0 − с +2. Это преобразование соответствует увеличению каждого отрицательного числа −b на 2(+10), т.е. b' = −b + 10. Совокупность значений b' образует область изображений отрицательных чисел. Область значений положительных чисел совпадает с их областью изображений. Заметим, что при таком изображении все положительные числа будут иметь “0” в знаковом разряде, т.к. они меньше единицы, а отрицательные числа − “1”. Значение 1, 000...0 соответствует отрицательному нулю "−0". Перейдя таким образом от отрицательных чисел к их положительным изображениям, мы имеем возможность заменить операцию вычитания операцией сложения. Замена операции вычитания сложением требует предварительной замены отрицательных слагаемых их изображениями с последующей обратной заменой суммы, имеющей в знаковом разряде единицу, ее значением. 2.4. Машинные структуры данных Как отмечалось выше, память ЭВМ имеет дискретную структуру и состоит из элементов, называемых ячейками. Эти ячейки нумеруются следующими подряд натуральными числами. Таким образом, память ЭВМ представляет собой линейную последовательность ячеек. Простые переменные. Это самые простые структуры, состоящие из одного элемента. При отображении на память ЭВМ имени простой переменной ей ставится в соответствие номер ячейки памяти, в которой хранится значение этой переменной. В некоторых случаях для записи значения переменной требуется более одной ячейки, такие случаи специально предусмотрены в описании данных для различных языков программирования. Массивы. В языках программирования массивами называют структуры, состоящие из множества элементов. Для их описания используют переменные с индексами, которые принято записывать в скобках после имени переменной, а не в виде подстрочных символов, как это принято в математике. Например: x[i], a[i,j], PRIMER (i,j,n). В зависимости от числа индексов различают массивы одномерные (один индекс), двумерные (два индекса) и т.д. Значения элементов одномерного массива хранятся в виде последовательности. Таким образом, структура одномерного массива однозначно отображается на структуру памяти ЭВМ, при этом индекс i любого элемента массива и номер ячейки памяти, где он находится - N(i), связаны отношением: N(i) = N(1) + i −1, где N(1) номер ячейки памяти, в которой расположено значение 1го элемента массива. Например, если значение 1-го элемента массива хранится в ячейке с номером 101, то значение двадцатого элемента будет храниться в ячейке с номером 120. Двумерный массив состоит из элементов, образующих прямоугольную матрицу (таблицу). В этом случае первый индекс i обозначает номер строки, а второй индекс j - номер столбца, на пересечении которых располагается элемент. При отображении двумерного массива на память ЭВМ (или на одномерный массив, что, как отмечалось выше, одно и то же) элементы двумерного массива располагаются в виде последовательности (строка за строкой или столбец за столбцом). Если принят первый способ (отображение по строкам), тогда номер к-го элемента двумерного массива x[i,j] в последовательности может быть вычислен по формуле: k = (i−1)n + j, где n – число элементов в строке двумерного массива. Подставив в предыдущую формулу k вместо i можно определить номер N(k) ячейки памяти ЭВМ, где он находится. Аналогично на одномерный массив отображаются массивы и большей размерности. Операции выбора элементов массива или записи в массив сводятся к вычислению значений индексов. Таким образом, массив как структура данных характеризуется возможностью прямого доступа к любому его элементу. Очереди. Эти структуры данных организуются по принципу «первым пришел – первым ушел» и представляют собой динамические структуры, число элементов которых может меняться в процессе обработки. Обработка элементов очереди ведется последовательно по одному, начиная с элемента, пришедшего в очередь первым. Вообще говоря, в очереди только два элемента доступны для обработки: первый - для операции чтения и обработки, и последний - для операции записи в очередь. Элементы, находящиеся в середине очереди, не доступны для обработки. Для отображения очереди используется одномерный массив a[1], a[2],..., a[n], причем длина n этого массива выбирается с таким запасом, чтобы длина очереди (число ее элементов) не превышала n. На практике для отображения очереди используют два указателя, один из которых указывает на элемент массива, хранящий «голову» очереди, а другой на элемент массива, предназначенный для записи очередного элемента очереди, «хвост». Пусть i – индекс элемента массива, хранящего «голову», а j – индекс первого свободного элемента массива для записи нового элемента очереди («хвост»). Тогда выборка очередного элемента очереди для обработки сводится к выполнению операций: х: = a[i]; i: = i +1. После этого индекс i указывает на следующий головной элемент очереди, т.е. головой очереди становится следующий по порядку элемент. Запись нового элемента у в очередь означает: a[j]: = y; j: = j + 1, т.е. индекс j снова указывает на первый свободный элемент массива. Длина очереди является переменной величиной, т.к. элементы ее могут поступать и обрабатываться с разной интенсивностью. Возможен также случай, когда очередь окажется пустой. Признаком этого является равенство i = j после чтения головного элемента очереди. При обработке очереди ее элементы смещаются к концу массива, а индекс j увеличивается после каждой записи в очередь. При этом после записи в очередь нового элемента возможен случай j = n. В этом случае необходимо сместить очередь в начало массива, положив i=1 и последовательно переписав все элементы очереди в элементы массива начиная с a[1]. Можно также считать массив замкнутым по кольцу, считая элементом, следующим за последним элементом массива, его первый элемент, т.е. при j = n «хвост» очереди перемещается в начало массива. Отображение очереди на «кольцевой» массив из пяти элементов показано на рис. 2.14. Рис. 2.6. Организация очереди Возможен случай, когда после записи в очередь нового элемента получим j = i. Это условие означает, что «хвост» совпадает с «головой» очереди. В этом случае необходимо выдать соответствующее сообщение о переполнении. Стеки. Стек – это структура данных, организованная по принципу «последний пришел – первым ушел». В отличие от очереди в нем доступен только один элемент, называемый вершиной стека. Очередной элемент при записи в стек заносится в его вершину, а остальные элементы без изменения порядка перемещаются вниз. При очередной выборке из стека выбирается элемент, находящийся в вершине, а все остальные элементы без изменения порядка сдвигаются вниз и в вершину попадает элемент, поступивший в стек предпоследним. Стек отображается на одномерный массив a[1],a[2],...,a[n] по тому же принципу, что и очередь. Для указания вершины стека можно использовать индекс i, при этом значение i = 0 перед чтением из стека служит признаком того, что стек пуст, а значение i = n перед записью в стек – признаком того, что стек переполнен. Строкой называется последовательность символов некоторого алфавита. Над строками, в основном, выполняются операции, состоящие в последовательном переборе символов строки или включения в строку нового символа, или исключения из строки заданного символа, а также во включении или исключении группы подряд идущих символов (подстроки). Поэтому для представления строк используется принцип, по которому каждый элемент строки занимает два соседних элемента массива – в одном из этих элементов записывается символ, а в другом элементе – ссылка на следующий символ строки, т.е. индекс первого из двух элементов массива, на которые отображен следующий символ строки. Каждые два элемента массива, на которые отображается один символ строки, называют звеном. С помощью ссылок звенья соединяются в цепочку. При этом очень важно, что соседние звенья совсем не обязательно должны занимать соседние элементы массива – они могут следовать в произвольном порядке по элементам массива. Истинный порядок элементов в цепочке определяется с помощью ссылок. Пример организации строки из трех символов abc показан на рис. 2.15. Для ее размещения требуется 8 элементов. В первые два элемента массива записывается служебная информация: первый элемент массива содержит ссылку на первое звено цепочки, а второй элемент массива - ссылку на первый свободный элемент массива, куда может быть записано новое звено цепочки. В каждом звене первый элемент содержит ссылку на следующее звено, а второй элемент – символ строки. Рис. 2.7. Организация строки аbc в виде цепочки Последнее звено цепочки имеет нулевую ссылку, что и является признаком конца цепочки. Включение нового символа сводится к образованию нового звена в свободном месте массива и изменению некоторых ссылок. Например, пусть в строку 'abc' нужно вставить символ 'х' после символа 'a', т.е. получить новую строку: 'aхbc'. Новое звено должно разместиться в девятом и десятом элементах массива. Меняется ссылка в звене до разрыва цепочки (в первом звене), а в новом звене указывается ссылка на звено после разрыва цепочки (на третье звено). Кроме того, меняется служебная информация, т. е. ссылка на первый свободный элемент массива (значение ссылки увеличивается на 2). В результате получается цепочка, изображенная на рис. 2.16. Рис. 2.8. Организация строки аxbc после включения символа x Алгоритм включения символа в строку с параметрами р и k, где р - символ, включаемый в строку, а k – индекс звена цепочки, после которого включается новое звено, содержащее этот символ, сводится к последовательному выполнению операторов переадресации ссылок. Этот алгоритм представлен на рис. 2.17. Если применить этот алгоритм к строке 'abc', представленной цепочкой, изображенной на рис. 2.15, при р='х' и k=3, то в результате его исполнения получится цепочка, показанная на рис. 2.16. Для исключения символа из строки достаточно убрать в цепочке ссылки на этот символ. Например, если из строки 'axbc' необходимо исключить третий символ, т.е. перейти к строке 'axc', то в цепочке для строки 'axbc' (см. рис.2.20), должна отсутствовать ссылка на символ 'b', содержащийся в третьем звене. Для этого достаточно задать во втором звене ссылку на символ, следующий за символом 'b' – на символ 'c', т.е. нужно выполнить команду a[9]:=7, после выполнения которой цепочка примет вид, показанный на рис. 2.17. Алгоритм исключения символа имеет один формальный параметр k – индекс звена цепочки, за которым следует исключаемое звено. Этот алгоритм представлен на рис.2.18. Применение этого алгоритма к строке, представленной цепочкой, изображенной на рис.2.15, при k=9 приводит к цепочке, изображенной на рис. 2.17. Исключение символов, таким способом, сводится лишь к уничтожению соответствующей ссылки, хотя сам символ и остается в массиве, но он (символ) недоступен для обработки (в массиве фактически образуется "дырка"). Вообще говоря, на это место можно было бы записать новое звено, но этого обычно не делают, чтобы не осложнять способ вычисления индекса первого свободного элемента массива. Аналогично можно построить и более сложные алгоритмы включения и исключения подстрок. Рис. 2.10. Организация строки 'axc' после исключения символа 'b' если записи упорядочить в соответствии со значениями ключей, расположив, например, записи в массиве в порядке увеличения значений ключей. Если ключи располагаются в последовательных элементах массива c[1],c[2],...,c[n] и упорядочены в порядке возрастания, то в этом случае можно применить дихотомический поиск. Заметим, что метод дихотомии легко можно обобщить и на случай, когда ключи следуют в массиве через один элемент, как это было сделано выше. Суть метода дихотомического поиска состоит в следующем. Допустим, требуется найти ключ K. Поиск строится на сравнении этой величины с ключом, хранящимся в среднем элементе массива. Индекс этого элемента определяется делением нацело, т.е. в качестве индекса среднего элемента массива берем целую часть n/2. Итак, пусть i = n:2 и Ki = c[i] - значение ключа, хранящееся в этом элементе массива. Сравниваем K с Ki. Если K = Ki, то поиск закончен и нужный ключ найден. Если K > Ki, то ключ нужно искать во второй половине массива c[i+1], c[i+2], ... , c[n], в противном случае его нужно искать среди элементов c[1], c[2], ... , c[i-2], c[i-1]. В выбранной половине массива снова берем средний элемент и т.д. При каждом сравнении длина массива, в котором производится поиск, уменьшается в два раза. Следовательно, через 1+log n сравнений останется сделать сравнение с единственным оставшимся элементом массива или ключ будет найден раньше. Последнее сравнение дает окончательный ответ на вопрос, есть ли данный ключ K в таблице. В алгоритме дихотомии (рис. 2.13) используются следующие переменные: i – для хранения индекса элемента массива, в котором содержится ключ K; min и max – для хранения индексов первого и последнего элементов части массива {c}, в которой ведется поиск; d – для хранения сообщения о том, найден ли ключ K. Рис. 2.13. Алгоритм дихотомии Нарушение условия min  max приведет к завершению цикла, так как либо будет найден ключ K, либо нарушится условие minmax, так как после каждого сравнения либо значение min увеличивается, либо значение max уменьшается. При обнаружении ключа выдается сообщение "ключ найден" и значение индекса i элемента массива, в котором он содержится. Если же ключ не будет обнаружен, то выдаются начальные значения i и d, т.е. значение индекса i = 0 и сообщение "ключ не найден". Рассмотренная организация таблицы удобна в том случае, если изменения таблицы достаточно редки. Если же включать и исключать записи приходится часто, то сразу становятся заметными недостатки такой организации. Это связано с тем, что при включении новой записи таблицу ключевых записей приходится раздвигать, а при исключении записи – сжимать, перемещая все записи с места разрыва таблицы по элементам массива, чтобы сохранить упорядоченность ключевых записей. Вопросы и упражнения 1. Что называется системой счисления? 2. Что называется цифрой? 3. Что называется числом? 4. Как определить количество, записанное в системе счисления с основанием «р»? 5. Как представить число в форме многочлена? 6. Что называется основанием системы счисления? 7. Каким преимуществом обладают системы счисления, весовые значения разрядов которых образуют ряд геометрической прогрессии? 8. Какие из систем счисления наиболее полно используют память ЭВМ? 9. Записать многочленную форму представления чисел в системах счисления с основаниями 2, 4, 8, 10, 12, 13, 16. 10. Записать исходные количества в системах счисления с основаниями 3, 7, 12 (основание системы счисления писать у числа в виде индекса). Исходные количества записаны в системе счисления с основанием 10: а) 49(10); д) 81(10); б) 343(10); е) 144(10); в) 147(10); ж) 348(10); г) 27(10); з) 1728(10). 11. Указать, какие из заданных в упр.10 десятичных чисел являются "круглыми" в 3-й, 7-й, 12-й системах счисления, т.е. оканчиваются на 0. 12. Записать заданные количества в 8-й, 2-й, 16-й системах счисления. Сравнить полученные записи и сделать вывод о количестве цифр и длине записей в различных системах счисления: а) 16(10); д) 256(10); и) 63(10); б) 32(10); е) 512(10); к) 65(10); в) 64(10); ж) 15(10); л) 255(10); г) 128(10); з) 17(10); м) 258(10). 13. Представить полученные в упр. 12 записи чисел в различных системах счисления в форме многочлена и проверить их правильность. 14. Получить записи всех цифр 8-й, 10-й, 16-й систем счисления в двоичной системе счисления. Какое количество двоичных разрядов необходимо для записи цифр различных систем счисления? 15. Выполнить указанные действия. Перевести заданные количества в десятичную систему счисления и проверить полученные результаты. а) 243(8) − 47(8) г) 337(8) − 71(8) ж) 167(8) − 37(8) к) 456(8) + 322(8) н) IC(16) + C(16) б) 253(8) − 177(8) д) 253(8) − 37(8) з) 254(8) − 36(8) л) 16(16) + C(16) о) −3A(16) − C(16) в) 156(8) − 47(8) е) 254(8) − 36(8) и) 156(8) − 47(8) м) IF(16) − A(16) п) 2B(16) + F(16) 16. На доске сохранилась полустертая запись: а) 23- 5+1 - 6 4 2 42423 б) 56- 24+4 - 3 7 - 6 1227160 в) 31- 2+1 4 2 3 4 100310 В какой системе счисления записаны слагаемые и сумма? Определить стертые цифры. 17. На вопрос ревизора один продавец ответил: "У меня осталось всего 100 кг овощей, из них 24 кг картофеля и 32 кг моркови. Сначала ответ удивил ревизора, но потом он понял, что продавец пользовался не десятичной системой. Какую систему счисления имел в виду продавец? 18. Какой из способов наиболее удобен для перевода целого числа из восьмеричной системы в десятичную? 19. Какое предположение Вы изначально делаете при выводе правила перевода целых чисел? 20. Какое предположение Вы изначально делаете при выводе правила перевода дробных чисел? 21. При переводе целых чисел из одной системы счисления в другую в какой системе счисления производятся действия? 22. Какой из приведенных способов перевода чисел из произвольной системы счисления в двоичную является наиболее рациональным? 23. Какой из способов перевода чисел из восьмеричной системы счисления в двоичную является наиболее рациональным? 24. Какой из способов перевода числа из восьмеричной системы счисления в шестнадцатеричную является наиболее рациональным? 25. Перевести заданные десятичные целые числа в двоичную систему счисления: а) 37; б) 52; в) 145; г) 452; д) 976; е) 8764. 26. Перевести заданные в упр.8 целые числа в системы счисления с основаниями 5, 8, 16. 27. Перевести заданные правильные десятичные дроби в системы счисления с основаниями 2, 8, 16. а) 0,125; б) 0,34375; в) 0,65625; г) 0,1875; д) 0,8125; е) 0,046875; ж) 0,953125; з) 0,140625; и) 0,859375; к) 0,165625; л) 0,734375; м) 0,390625; н) 0,609375; о) 0,390625; п) 0,359625; р) 0,640625; с) 0,484375; т) 0,515625; у) 0,3125; ф) 0,6875. 28. Перевести заданные целые числа из десятичной системы счисления в систему счисления с основаниями 2, 8, 16: а) 125; б) 131; в) 134; г) 141; д) 142; е) 144; ж) 147; з) 155; и) 209; к) 215; л) 217; м) 224; н) 226; о) 233; п) 234; р) 241; с) 246. 29. Перевести в десятичную систему счисления числа с основаниями: 29.1. два: а) 1000011,110; б) 10001111,011; в) 1101010,11; г) 10010100,011; д) 1101010,11. 29.2. восемь: а) 247,13; б) 242,53; д) 222,21; е) 163,17; в) 237,51; ж) 160,11; г) 231,37; з) 250,17. 29.3. шестнадцать: а) 2A; б) 1F1; в) 16A; г) 1F2; д) 15C; е) 25C; ж) 150. 30. Разработайте блок-схему алгоритма перевода дробных чисел из одной системы счисления в другую. 31. Разработайте блок-схемы алгоритмов перевода целых дробных чисел из системы счисления с основанием 16 в систему счисления с основанием 2. 32. Какое количество разрядов ячейки памяти отводится для записи целой части числа при представлении его с фиксированной точкой? 33. В подавляющем большинстве ЭВМ для представления числа с фиксированной точкой все числа представляются в виде правильных дробей, т.е. точка фиксируется после знакового разряда. Что достигается использованием такого формата для представления чисел с фиксированной точкой? 34. Какой формат ячейки используется для представления чисел в плавающей точкой? 35. Какой способ представления чисел является более предпочтительным по быстродействию выполнения арифметических операций на ЭВМ? 36. Для каких чисел область значений совпадает с областью изображений чисел? 37. Для чего нужно представление чисел с фиксированной и плавающей точкой? В каких случаях нужно пользоваться каждым из этих представлений? 38. Каким образом в ЭВМ автоматически фиксируется переполнение разрядной сетки? 39. Для чего нужна нормализация чисел? 40. Сложить заданные десятичные числа в двоичной системе счисления с использованием обратного кода в следующем формате ячейки: 1 разряд - знаковый, 15 разрядов - информационные. Точка фиксируется после знакового разряда. а) −0,65625 и 0,34375; б) 0,8125 и −0,1875; в) 215 и 147; г) −125 и 246. Результат представить в восьмеричной и десятичной системах счисления. Сделать проверку в десятичной системе счисления. 41. Сложить заданные числа с использованием дополнительного кода с плавающей точкой в формате ячейки: 1 разряд - знак чис- ла, 15 разрядов - мантисса, 1 разряд - знак порядка, 5 разрядов порядок. а) −144,65625 и 224,34375; б) −234,8125 и 134,1875. Результат представить в восьмеричной и десятичной системах счисления. Сделать проверку в десятичной системе счисления. 42. Каким образом можно представить структуру памяти ЭВМ? 43. Какие типы массивов Вы знаете? Каким образом элементы двумерного массива отображаются на память ЭВМ? 44. С какого элемента начинается обработка элементов очереди и стека? 45. Каким образом производится включение нового символа в строку и исключение символа из строки? Что в этих процедурах общего с включением и исключением записи в список? 46. Какие из рассмотренных в данном параграфе структур данных наиболее пригодны для выдачи информации по запросам? Аргументируйте Ваши предложения. 47. Каким образом можно сократить время выполнения основных информационных операций с таблицами? 48. Каким образом производится включение нового ключа в таблицу? Поясните это примером на рис.2.14.