В. Ю. Наумов Введение в информатику
 Скачать 2.05 Mb.
|
|
ПРИМЕР Возьмем число 1247 для перевода в двоичный вид. Договоримся, в десятичном виде число записывать – как есть, а в двоичном виде указывать нижний индекс 2. Составим таблицу натуральных степеней двойки (табл. 1.2). Таблица 1.2 Целые степени двойки n 0 1 2 3 4 5 6 7 8 9 10 11 2 n 1 2 4 8 16 32 64 128 256 512 1024 2048 Разложим число 1247 на степени двойки. Для этого сначала найдем в табл. 1.2 число, ближайшее к 1247 снизу; таким числом является 1024. 1247=1024+223. Теперь найдем в табл. 1.2 число, ближайшее к 223 снизу – число 128 и так далее, т. е.: 1247=1024+128+95=1024+128+64+31=1024+128+64+16+15= =1024+128+64+16+8+4+2+1=2 10 +2 7 +2 6 +2 4 +2 3 +2 2 +2 1 +2 0 = =10000000000 2 +10000000 2 +1000000 2 +10000 2 +1000 2 +100 2 +10 2 +1 2 Для того чтобы сложить эти числа, запишем их в столбик: + 10000000000 + 10000000 + 1000000 + 10000 + 1000 + 100 + 10 ___________1 10011011111 Итак, получили 1247=10011011111 2 16 Возвращаясь к определению бита, переформулируем его так: бит – один разряд двоичного числа. 1.3. Понятие информации Данные выше определения, связанные с понятием информации, не совсем удачны, поскольку выражают некое субъективное отношение к информатике, в общем, и к информации, в частности. Субъективизм, конечно, вполне оправдан, однако, его нужно почувствовать. Информатика является наукой точной и потому требует более строгого подхода к определению своего ключевого понятия. Для этого следует сделать информацию измеряемой. Подход, описанный далее, впервые был осуществлен Д. Хартли 4 в 1928 г. Пусть у нас имеется некий канал, по которому мы получаем сообщение в виде двоичных кодов (есть сигнал – «1», нет сигнала – «0»). Иллюстрация к описанному процессу представлена на рис. 1.2. Предположим, что наше сообщение состоит из четырех принятых цифр. Тогда полное количество различных его вариантов есть 2 4 = 16. Допустим, что наше сообщение хотят перехватить. Зададимся вопросом: «Какова неопределенность полученного нами сообщения при известном числе переданных знаков?». Если мы получаем четыре знака, то неопределенность равна 16. А если мы к этим четырем знакам прибавим, скажем, еще четыре, то неопределенность составит 16×16=256. Вот что получается, если просто прибавить к исходному сообщению еще несколько знаков; общая неопределенность сообщения умножается на неопределенность, внесенную этими знаками. Хотя логичным кажется не умножение, а складывание неопределенности. 4 Дуглас Хартли (1897 – 1958) – английский физик; занимался вопросами вычислительной математики, квантовой механики. Один из пионеров внедрения в Великобритании цифровых вычислительных машин. 17 В математике для ухода от операций умножения к эквивалентным операциям сложения часто применяют логарифмирование. Действительно, логарифм произведения равен сумме логарифмов: 1 2 1 2 ln ln ln ... ln k k p p p p p p Согласно Хартли, количество информации, находящейся в одном сообщении, кодированном «0» или «1», равно 2 log 1/ H p , где p – вероятность возникновения некоторого события. Если событие состоит из последовательности равновероятных, то общая вероятность их последовательности будет 1 2 k p p p p . Для равновероятного выпадения «0» или «1» это будет 1 1 1 1 2 2 2 2 k p , и 2 log 2 k H k Если кодирование происходит большим числом знаков, скажем тремя: «0», «1» и «3», а мера неопределенности сообщения есть 1 W p , то информационная емкость сообщения будет определяться как 3 log H W Однако на практике наибольшее распространение получила система, основанная на двоичном счете, и потому для бинарного сообщения, состоящего из k , знаков информационная емкость составляет 2 log 2 k H k . (1.1) Эта формула справедлива только для таких сообщений, у которых возникновение «0» или «1» на любом этапе приема сообщения равновероятно. Это происходит далеко не всегда. Так, например, для сообщения, состоящего из четырех двоичных знаков, информационная емкость составит 4 2 log 2 4 H (рис. 1.2). Если, к примеру, мы пишем текст на русском языке и пользуемся для его передачи кодировкой ASCII, то каждый передаваемый символ будет содержать 8 бит информации. Общая мера неопределенности составит 256 вариантов на символ. Очевидно, что наиболее часто встречающимся 18 символом будет «пробел», который имеет номер 32 10 =20 16 =100 000 2. Особенностью любого языка (и русского, в частности) является неравномерность вероятности появления различных букв. Так, например, буква «о» в русском языке является наиболее частой, а буква «ф» – наиболее редкой. 5 То есть если мы будем передавать, скажем, роман Льва Николаевича Толстого «Война и мир», то вероятность "1" p встретить в двоичном коде сообщения «1» будет отличной от вероятности "0" p встретить «0». Равные вероятности, для которых применима формула (1.1), – это такие вероятности, при которых "1" "0" 1/ 2 p p , так как полная вероятность единица (т. е. "1" "0" 1 p p ). Обобщение для случая "1" "0" p p было введено в 1948 г. К. Шенноном 6 : 1 1 "1" 2 "1" "0" 2 "0" "1" 2 "1" "0" 2 "0" "1" "0" log log log log 1 J p p p p p p p p p p (1.2) " " 1 " " 1 log 1 n i n i i n i i J p p p , (1.3) где i p – вероятность встречи i -го знака. При "1" "0" p p 1 J . Если же "1" "0" p p , то эта величина будет меньше. В частности, при "1" 0 p и "0" 1 p , получим 0 J Если перейти от двоичной формы представления информации к форме представления произвольным числом знаков n , то получим для 1, 2, ... , i n обобщение выражения (1.2): 5 Ради интереса можете просто взять и посчитать встречаемость букв, скажем, на этой странице. 6 Клод Шеннон (1916 – 2001), - американский инженер и математик, один из создателей математической теории информации 19 Если всего было передано m знаков, то нужно просуммировать информацию, переносимую каждым знаком. Если вероятности " " i p одинаковы для всех цифр, то суммарная информация будет в m раз больше чем значения, полученные по формуле (1.3). Запишем случай для двоичного сообщения: "1" "1" "0" "0" 1 log log m k k k k k J m p p p p 0 1 2 3 4 t 0 0 0 0 1 0 1 2 3 4 t 0 0 0 1 2 0 1 2 3 4 t 0 0 1 0 3 0 1 2 3 4 t 0 0 1 1 4 0 1 2 3 4 t 0 1 0 0 5 0 1 2 3 4 t 0 1 0 1 6 0 1 2 3 4 t 0 1 1 0 7 0 1 2 3 4 t 0 1 1 1 8 0 1 2 3 4 t 1 0 0 0 9 0 1 2 3 4 t 1 0 0 1 10 0 1 2 3 4 t 1 0 1 0 11 0 1 2 3 4 t 1 0 1 1 12 0 1 2 3 4 t 1 1 0 0 13 0 1 2 3 4 t 1 1 0 1 14 0 1 2 3 4 t 1 1 1 0 15 0 1 2 3 4 t 1 1 1 1 16 Рис. 1.2. Кодирование всех возможных вариантов 4-битного сообщения 20 "1" "1" "0" "0" "1" "1" "2" "2" "1" "0" log log при , при k k m p p p p p p p p J m m p p Величину, введенную Шенноном (1.2) и (1.3), часто называют энтропия информации. 1.4. Программное обеспечение Следует отметить, что в современных вычислительных системах выделяют два основных компонента: программная часть (software) и аппаратная часть (hardware). На особенностях реализации аппаратной части остановимся чуть позже. Здесь же дадим классификацию программной части. Программное обеспечение (ПО) – это определенный набор информации, с которой приходится работать аппаратной части (ЭВМ). Вся информация в ЭВМ делится на две группы: 1) программы – последовательность инструкций или команд (ал- горитмов), предназначенных для выполнения определенных действий; 2) данные – объект воздействия программ. Информация называ- ется данными, если существует программа, в которой эта информация по- ступает на ее вход, либо генерируется на ее выходе (т. е. данными для тек- стового редактора является текстовый документ). Для мультимедийного плеера данными будет музыка или видеоролик. А, например, для програм- мы записи информации на диск, данными могут быть другие программы. Так что приведенная классификация достаточно условна и зависит от того, как вся эта информация используется. ПО принято делить на три группы (рис. 1.3): 1) системное – ПО для управления ресурсами и технического обслуживания ЭВМ. К системному ПО относят, прежде всего, операционные системы (ОС) – специальный комплекс программ для обеспечения взаимодействия 21 пользователя и аппаратных ресурсов, а также для управления взаимодействием программ с аппаратными ресурсами и между собой. Можно сказать, что операционная система – это главная программа в компьютере. Для разных аппаратных платформ существуют разные ОС. Так, например, существуют свои ОС для сотовых телефонов, карманных ПК, маршрутизаторов, серверов и прочих сложных устройств, способных производить вычисления. Свои ОС разрабатываются даже для самолетов, автомобилей и другой техники. Для персональных ЭВМ наибольшее распространение получило семейство ОС Windows. Стоит отметить, что в качестве альтернативы Windows существуют и другие достаточно удачные ОС, самые известные из которых – это семейство ОС GNU Linux. Достоинством Linux является бесплатная лицензия на использование и открытый исходный код системы. Кроме этих двух семейств существуют и другие ОС, способные работать на большинстве персональных ЭВМ. Это, например: MacOS, DOS, OS/2, QNX, FreeBSD, OpenBSD и др. Кроме ОС к системному ПО можно отнести драйверы – специальные программы, которые обеспечивают взаимодействие конкретной ОС и конкретного аппаратного устройства. Например, драйвер видеокарты, драйвер сканера, драйвер платы мониторинга радиационного фона и т. д. Аппаратная часть Системное ПО Прикладное ПО Инструментальное ПО Пользо- ватель Рис. 1.3. Взаимодействие между различными видами программного обеспечения и человеком 22 Далее, к системному ПО относят программные кодеки (ogg, mp3, mpeg4, mpeg2 и т. д.), различные оболочки ОС (файловые менеджеры, диспетчеры процессов, редакторы системного реестра и т. д.), утилиты (дефрагментаторы дискового пространства, средства индексации файлов, оптимизаторы памяти и т. д.), программные средства защиты (антивирусы, межсетевые экраны, средства аутентификации и разграничения доступа, антиспам фильтры и т. д.); 2) прикладное – основная масса ПО, ради которого вообще существует ЭВМ. С помощью этого вида ПО пользователи решают свои задачи в некоторой проблемной области, не прибегая при этом к программированию. К прикладному ПО относят офисные приложения, системы управления и мониторинга бизнес-процессов, системы проектирования и производства, научное ПО, игры, мультимедиа приложения и т. д.; 3) инструментальное – программное обеспечение, предназначенное для использования в ходе проектирования, разработки и сопровождения программ, в отличие от прикладного и системного программного обеспечения). К инструментальному ПО прежде всего относят интегрированные среды разработки (IDE – Integrated Development Environment). Это такие среды, как Eclipse, Visual Studio, Delphi, Builder, Turbo C, Turbo Pascal, Composer Studio, Code Warrior и другие. Вышеперечисленные среды являются средствами написания, отладки и компиляции программного кода. Причем многие из упомянутых IDE в своем составе имеют компиляторы для различных языков программирования (Pascal, Assembler, Java, C, C++, Visual Basic). В качестве практических заданий для настоящей книги выступают различные алгоритмические задачи. Потому именно инструментальным ПО придется в наибольшей степени пользоваться читателю для полноценного усвоения материала. Основным языком программирования 23 выступает С++, для которого существует достаточно много компиляторов и сред разработки. Тексты всех программ из настоящего пособия набирались и компилировались в Microsoft Visual Studio C++. Следует отметить, что приведенная классификация достаточно условна, поскольку конкретное ПО не всегда можно однозначно отнести в ту или иную группу. Так, например, современные текстовые редакторы имеют в своем составе средства программирования; мультимедийные системы могут, помимо программных плееров, также включать в свой состав драйверы устройств и программные кодеки. И таких примеров можно привести достаточно много. 1.5. Архитектура персональной ЭВМ Компьютер (ЭВМ) – универсальное, электронное, программно- управляемое устройство для хранения, обработки и передачи информации. Архитектура ЭВМ – общее описание структуры и функции ЭВМ на уровне, достаточном для понимания принципов работы ЭВМ и ее системы команд. Основные компоненты архитектуры ЭВМ – процессор, внутренняя и внешняя память, и различные периферийные устройства (рис. 1. 4). Процессор – главное устройство ЭВМ, обеспечивающее обработку и передачу данных, управление внешними устройствами. Разрядность процессора – число одновременно обрабатываемых битов информации. Различают разрядность по командам и разрядность по данным. Чем выше командная разрядность процессора, тем больше элементарных команд ему доступно и, соответственно, тем эффективнее он сможет обработать информацию. Чем выше разрядность по данным, тем больший объем памяти доступен процессору для адресации. Если данные и команды хранятся в разных областях памяти, то такие 24 процессоры называются процессорами с Гарвардской архитектурой. Если данные и команды могут храниться в одной области памяти, тогда архитектура будет называться фон Неймановской 7 . У Гарвардских процессоров разрядность команд и данных может быть различной. У фон Неймановской же архитектуры разрядности данных и команд одинаковые. Быстродействие процессора – число выполняемых элементарных операций в единицу времени. Часто используют показатель MIPS (Millions of Instructions Per Second) – величину, которая показывает, сколько миллионов инструкций в секунду выполняет процессор в некотором синтетическом тесте. Тактовая частота – величина, показывающая, сколько раз в единицу времени происходит смена состояния процессора. Имеет линейную связь с производительностью процессора определенной архитектуры; измеряется в Герцах. Как правило, тактовые частоты современной электроники большие, а потому применяют кратные величины: МГц, ГГц. Память компьютера – электронные ячейки, в которых хранится информация. Делится на внутреннюю (ОЗУ, ПЗУ) и внешнюю (гибкие и жесткие магнитные диски, оптические диски, ленточные накопители, флэш-карты и т. д.). ОЗУ – оперативное запоминающее устройство, в котором располагаются программы, выполняемые в данный момент, а так же дан- ные, к которым необходим быстрый доступ. При выключении питания компьютера информация в ОЗУ теряется. В английском варианте ОЗУ называется RAM (Random Access Memory – память произвольного доступа). 7 Джон фон Нейман (1903–1957) – немецкий математик и физик, эмигрировавший в США. Занимался вопросами квантовой механики, функциональным анализом, логикой и метеорологией. Большой вклад внес в создание первых ЭВМ и методов их применения. Его теория игр сыграла важную роль в экономике. |