Информатика (конспект лекций)

Введение

Учебная дисциплина «Информатика» читается студентам направления 552800 «Информатика и вычислительная техника» и, в частности, студентам специальности «Автоматизированные системы обработки информации и управления» с целью обу- чения теоретическим положениям и практическим умениям, которые составляют основу их будущей профессиональной деятельности.

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

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

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

Разделы 1 и 2 написаны В.Н. Задорожным, раздел 3 – О.Н. Каневой. Авторы вы- ражают благодарность своим коллегам, сотрудникам и студентам кафедры АСОИУ ОмГТУ, оказавшим практическую помощь в подготовке конспекта лекций.

3

1 СИСТЕМЫ СЧИСЛЕНИЯ

1.1 Позиционные и непозиционные системы счисления

Системой счисления (нумерацией) обычно называют способ записи чисел с по- мощью специальных знаков или цифр. Так, общепринятая десятичная система ис- пользует 10 цифр: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. В вычислительных машинах чаще приме- няется двоичная система, использующая только две цифры: 0 и 1.

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

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

дилась. Так, буква I в любой позиции означает единицу, буква V – пять, X – десять, L – пятьдесят, C – сто, D – пятьсот, M – тысячу. Например, число 394 будет за-

писано в римской системе счисления как CCCXCIV, а число 666 – как DCLXVI. Самое большое число, которое может быть записано в классической римской систе- ме счисления, – это MMMCMXCIX, т.е. 3999. Для того чтобы в этой системе мож- но было записать любое число, нужно было бы иметь в распоряжении бесконечно много разных специальных символов. В позиционных системах счисления, подоб- ных десятичной системе, достаточно использовать конечный набор цифр.

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

лишь с точностью до знаков ±. Например, в записи числа VI буква I обозначает плюс единицу, а в записи числа IV – минус единицу. Аналогично могут меняться значения и других символов. Рассуждая логически строго, римскую нумерацию сле- довало бы относить к позиционным системам счисления. Но поскольку этого все же не делают, то тем самым границу между позиционными и непозиционными систе- мами устанавливают достаточно условно, определяют не точно. Мы в дальнейшем будем рассматривать лишь позиционные системы, подобные десятичной системе счисления, которые определим более строго.

Современная десятичная позиционная система была изобретена, по всей видимо- сти, в Индии, в начале новой эры. В Европу она проникла вместе с трудами араб- ских ученых и здесь повсеместно распространилась лишь в течение XVI–XVIII ве- ков (включая десятичную запись дробных чисел) [1].

4

1.2 Позиционные системы счисления

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

Пьер Симон Лаплас

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

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

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

Наиболее совершенным принципом записи чисел ныне считается позиционный принцип, на котором основана наша десятичная система счисления. Числа до десяти обозначаются цифрами 0, 1, … , 9. Такие числа записываются в виде одноразрядно- го числа, т. е. запись числа состоит из одной цифры. Следующее за девятью число десять не может быть записано в одном разряде, т. к. для его обозначения цифры нет. Поэтому десять единиц объединяются и составляют единицу второго разряда, так что число десять записывается как двухразрядное: 10. В записи десятичного числа 10 второй (считая справа) разряд числа содержит цифру 1, указывающую чис- ло десятков. Вместе с первым разрядом – разрядом единиц – двухразрядные деся- тичные числа могут обозначать количества от 10 до 99. Следующее за 99 число – десять десятков, т. е. сотня, составляет единицу третьего разряда и записывается, соответственно, как 100.

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

5

Всякое натуральное число n, записываемое в десятичной системе счисления по-

следовательностью цифр

Каждый символ ai (цифра) получает значение, определяемое: 1) его начертанием, 2) его положением в записи числа. Если, например, мы хотим записать семь тысяч, мы должны поставить цифру 7 на четвертое место, считая справа; остальные три разряда в данном случае отсутствуют, поэтому на их место ставятся нули: 7000. Та- ким же образом символ 7 может означать 7 единиц, 7 десятков, 7 сотен и т. д., смот- ря по тому положению, которое он занимает.

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

Здесь am, … ,a1,a0 – цифры целой части числа, a-1a-2…a-k – цифры дробной части

числа.

Как видно из выражения (4), числовое значение единицы любого i-го разряда де- сятичного числа равно 10 i, где i – номер разряда – равен нулю или положителен (влево от разделительной запятой), либо отрицателен (вправо от запятой). Всякая цифра ai показывает число единиц i-го разряда, поэтому в общей сумме (4) эта цифра берется с множителем 10 i. Запись десятичного числа цифрами в виде (3) эквива- лентна его записи в виде полинома (4).

Количество цифр B, используемое в любой позиционной системе счисления, по- добной десятичной системе, называется основанием системы счисления. В десятич- ной системе основание B = 10. В качестве основания позиционной системы могут быть взяты и другие числа, отличные от 10, например, B = 2, 3, … .

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

Запись любого числа в позиционной системе счисления с основанием B имеет вид последовательности цифр amam-1…a1a0 , a-1a-2…a-k и эквивалентна выражению

am Bm + am-1 Bm-1 + … + a1 B1 + a0 B0 +

Верхняя строка здесь определяет значение целой части числа, а нижняя – значение дробной части.

6

Выражение (5) отличается от выражения (4) только тем, что на месте числа 10 – основания десятичной системы, здесь записано в общем виде основание B, которое может быть любым целым положительным числом, большим единицы: B ³ 2. Все позиционные системы счисления, о которых будет идти речь в данном пособии, бу- дут отличаться только основанием B, т. е. числом используемых цифр. Свойства за- писи чисел в различных позиционных систем счисления можно вывести из алгеб- раического представления (5), играющего, следовательно, своего рода ключевую роль.

Решим, например, с помощью представления (5) следующий вопрос. В двоичной системе счисления (B = 2) записано число:

x = 101 1001 1011.

Какое это число?

Чтобы ответить на этот «наивный» вопрос, нужно, видимо, записать указанное двоичное число x в естественной для нас десятичной форме. Расшифровывая смысл двоичной записи числа x с помощью выражения (5), получаем:

x = 101 1001 1011 =

= 1×210 + 0×29 + 1×28 + 1×27 + 0×26 + 0×25 + 1×24 + 1×23 + 0×22 + 1×21 + 1×20 =

=210 + 28 + 27 + 24 + 23 + 21 + 20 = = 1024 + 256 + 128 + 16 + 8 + 2 + 1 = 1435.

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

Кроме вопросов, касающихся записи чисел в различных системах счисления, с практической точки зрения для нас небезразличен и вопрос чтения чисел, т. е. назы- вания, произношения чисел в виде имен числительных. Поскольку мы все уже при- выкли имена числительные соотносить с десятичным представлением чисел, то можно смело использовать их и в других системах счисления, подобных десятичной системе. Не нужно только забывать, в какой именно системе счисления записано именуемое нами число. Например, рассмотренное двоичное число 101 1001 1011 можно читать так: «сто один тысяча один тысяча одиннадцать, двоичное».

В качестве упражнения предлагаем проверить, что число «сто один тысяча один тысяча одиннадцать, троичное» в десятичной системе счисления запишется так: 67909.

1.3Перевод чисел из одних систем счисления в другие

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

1011001 10112 = 143510.

Впредыдущем параграфе установлено, что 101 1001 10113 = 6790910. Нижний и

7

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

1.3.1 Перевод чисел в десятичную систему счисления

Выражение (5) дает нам ключ к переводу числа из любой позиционной системы счисления в десятичную систему: для такого перевода достаточно записать и вы- числить это выражение. Для иллюстрации этого правила переведем в десятичную систему число с дробной частью 11011,1012:

x= 11011,1012 =

=1×24 + 1×23 + 0×22 + 1×21 + 1×20 + 1×2-1 + 0×2-2 + 1×2-3 =

=24 + 23 + 21 + 20 + 2-1 + 2-3 =

=16 + 8 + 2 + 1 + 0,5 + 0,125 = 27,62510.

Получаем, что 11011,1012 = 27,62510.

Ввосьмеричной системе счисления основание системы B = 8. Для представления цифр разрядов нужно использовать восемь различных символов, в качестве которых

возьмем 0, 1, 2, ... , 7. Тогда, например, восьмеричное число 735,468 переведется в десятичную систему счисления следующим образом:

x= 735,468 =

=7×82 + 3×81 + 5×80 + 4×8-1 + 6×8-2 =

=7×64 + 3×8 + 5×1 + 4×(1/8) + 6×(1/64) =

=477,5937510.

Вшестнадцатеричной системе счисления B = 16 и для записи цифр разрядов принято использовать набор из следующих 16 символов: 0, 1, 2, ... , 9, А, B, С, D, E, F. Он содержит 10 арабских цифр и еще шесть цифр, в качестве которых использу- ются начальные буквы латинского алфавита. При этом цифра А обозначает число

1010, аналогично В = 1110, С = 1210, D = 1310, Е = 1410 и F = 1510. Зная эти цифры ше- стнадцатеричной системы счисления, нетрудно определить, что, например,

AB9,C2F16 = 10×162+11×161+9×160+12×16–1+2×16–2+15×16–3 = 2745,76147460937510.

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

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

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

Всоответствии с этим правилом в десятичной системе все натуральные несо- кратимые дроби вида M/(2K5 L) представляются конечными позиционными дробями, остальные – периодическими. Например, числа 40 и 25 разлагаются только на мно-

8

жители 2 и 5, поэтому дроби 1/40 и 1/25 в десятичной записи конечные: (1/40)10 = 0,02510; (1/25)10 = 0,0410. Числа 7 и 81 не являются произведениями только чисел 2 или 5, поэтому их десятичная запись – бесконечная периодическая: (1/7)10 = 0,14285714285710…; (1/81)10 = 0,01234567901234567910.

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

Однако не всякая конечная десятичная дробь переведется в конечную же двоич- ную (восьмеричную, шестнадцатеричную) дробь, т. к. в общем случае знаменатель ее натурального представления может содержать и множитель 5. Например, дробь 0,110 после перевода в двоичную форму будет бесконечной периодической.

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

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

Например, стандартная программа «калькулятор» операционной системы Microsoft Windows выполняет простые четыре арифметических действия с дробями вида

23 , 101 и т.п. точно за счет их внутреннего хранения в виде обыкновенных дробей.

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

Тем не менее, при проверке точности калькулятора путем вычисления прямых и обратных функций он демонстрирует как будто бы полное отсутствие погрешно- стей: он покажет, например, что (Ö2)2 = 2 точно, что exp(ln(10)) = 10 точно и т. д.

И все же можно без особого труда убедиться, что такая видимость отсутствия погрешностей достигается просто за счет скрытого использования в расчетах до- полнительных десятичных разрядов. Всего используется, по-видимому, около 38 разрядов, но выдаваемые на экран результаты вычисления округляются до 32 деся- тичных разрядов. Это создает впечатление отсутствия погрешностей. Благодаря этому в результате вычисления (Ö2)2 на экране калькулятора появляется целое чис- ло 2. На самом же деле результат отличен от 2. Действительно, отнимите от него 2, и вы не получите нуля: при вычислении (Ö2)2-2 калькулятор выдаст не 0, а приблизи-

тельно -2,97×10-38 (в разных версиях рассмотренной программы калькулятора его точность может несколько различаться).

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

9

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

1.3.2 Перевод чисел из десятичной системы счисления

Выражение (5) дает нам также ключ и для перевода чисел из десятичной систе- мы счисления в любую другую позиционную систему с основанием B. Для такого

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

Рассмотрим перевод целой и дробной части числа по отдельности.

Перевод целой части числа

Целая часть заданного числа должна быть записана в системе счисления с осно- ванием B (с помощью ее цифр) в виде последовательности amam-1…a1a0, которая

сокращенно представляет сумму

Если разделить эту сумму на B, то в остатке получится a0 – значение цифры младшего разряда B-ичного числа. Частным от деления (6) на B будет сумма

am Bm-1 + am-1 Bm-2 + … + a2 B1 + a1.

Если теперь разделить и это частное на B, то в остатке получится a1, т. е. значе- ние цифры следующего разряда B-ичного числа. Величина частного составит

am Bm-2 + am-1 Bm-3 + … + a2 ,

и его снова можно разделить на B, чтобы найти остаток a2 и т. д.

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

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

Примеры. Переведем в двоичную систему число 2010.

Выполним для этого следующую последовательность операций деления числа 20 на основание двоичной системы B = 2:

Полученная последовательность остатков в обратном порядке запишется как

10100. Таким образом, 2010 = 101002.

10