Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.astro.spbu.ru/staff/ilin2/EDU/KURS/l1-5.ps Дата изменения: Fri Nov 19 16:15:14 2010 Дата индексирования: Tue Oct 2 02:11:46 2012 Кодировка: Windows-1251 Поисковые слова: п п п п п п п п п

ВВЕДЕНИЕ В ИНФОРМАТИКУ ДЛЯ АСТРОНОМОВ
Я думаю, что информатика (computer science), достигшая
зрелого возраста, становится кровосмесительной: людей
обучают люди, думающие односторонне. В результате так
называемые ортогонально мыслящие встречаются все
реже и реже...
Кен Томпсон
1 Цели и задачи курса. Притча Дейкстры
Данный курс является введением в информатику. Информатика  фундаментальная естественная наука,
изучающая структуру и свойства информации, а также методы ее обработки, хранения, поиска, передачи
и т.д.
Информатика как наука сформировалась в середине прошлого века. Теперь это большая наука, и мы
коснемся в этом курсе лишь некоторой ее части. Суть предмета, который мы будем изучать, поясним на
примере известной притчи Дейкстры, но сначала несколько слов об ее авторе.
Эдсгер Дейкстра (Edsger W. Dijkstra, 11.05.193006.08.2002)  один из тех людей, с именем которых
связано превращение программирования из шаманства в науку. Работы Дейкстры уже сегодня можно
назвать классическими. Одной из форм научной деятельности Дейкстры являлись письма, которые
он время от времени посылал своим корреспондентам, призывая распространять их дальше. Сборник,
содержащий некоторые из этих писем, был опубликован в 1982 г. Когда взгляды Дейкстры стали известны
широкому кругу программистов, они вызвали сильную (и далеко не всегда положительную) реакцию.
Теперь приведем полностью перевод письма Дейкстры, содержащего притчу.
Недавно среди старых моих бумаг я нашел следующий рукописный текст. Должно быть я написал
его в середине 1973, но не думаю, что по прошествии трех лет его смысл хоть в чем-то изменился.
Следовательно, я включаю его в EWD-серию.
Притча о первом программисте
В незапамятные времена была организована железнодорожная компания. Один из ее руководителей, вероятно
малый не промах, обнаружил, что начальные инвестиции могут быть значительно снижены, если снабжать
туалетом не каждый железнодорожный вагон, а лишь половину из них. Так и порешили.
Однако вскоре после начала пассажирских перевозок посыпались жалобы. Провели расследование и
обнаружили, что причина крайне проста: хотя компания была только что создана, неразберихи уже хватало,
и о распоряжении дирекции о туалетах ничего не знали на сортировочных станциях, где все вагоны считались
одинаковыми, и в результате в некоторых поездах туалетов почти совсем не было.
Чтобы исправить положение, каждый вагон снабдили надписью, говорящей, есть ли в нем туалет, и сцепщикам
было велено составлять поезда так, чтобы около половины вагонов имели туалеты. Хотя это и осложнило
работу сцепщиков, но проблему решили и вскоре ответственные за сцепку с гордостью сообщили, что тщательно
выполняют новую инструкцию.
Хотя новый порядок сцепки выполнялся неукоснительно, тем не менее неприятности с туалетами
продолжались. Новое расследование их причин показало, что хотя действительно половина вагонов в поезде
снабжена туалетами, иногда выходит так, что все они оказываются в одной половине поезда. Чтобы спасти дело,
были выпущены инструкции, предписывающие чередовать вагоны с туалетами и без них. Это добавило работы
сцепщикам, однако, поворчав(!), они и с этим справились.
Жалобы, однако, продолжались. Как оказалось, причина в том, что поскольку туалеты располагаются в одном
из концов вагона, расстояние между двумя соседними туалетами в поезде могло достигать трех длин вагонов и для
пассажиров с детьми  особенно если коридоры были заставлены багажом  это могло привести к неприятностям.
Тогда вагоны с туалетами были снабжены стрелкой, и были изданы новые инструкции, предписывающие, чтобы
в каждом поезде(!) все стрелки были направлены в одну сторону. Нельзя сказать, чтобы эти инструкции были
встречены на сортировочных станциях с энтузиазмом  количество поворотных кругов(!) было недостаточным, и,
по правде говоря, мы должны восхищаться тем, что несмотря на существующие стандарты и нехватку поворотных
кругов, напрягшись, сцепщики сделали и это.
Теперь, когда все туалеты находились на равных расстояниях, компания была уверена в успехе, однако
пассажиры продолжали беспокоиться: хотя до ближайшего туалета было не больше одного вагона, но не было
ясно, с какой стороны он находится. Чтобы решить и эту проблему, внутри вагонов были нарисованы стрелки с
надписью ТУАЛЕТ, сделавшие необходимым правильно ориентировать и вагоны без туалетов.
На сортировочных станциях новая инструкция вызвала шок: сделать требуемое вовремя было невозможно(!).
В этот критический момент кто-то, чье имя сейчас невозможно установить, заметил следующее. Если мы
сцепим вагон с туалетом и без оного так, чтобы туалет был посередине, и никогда их не будем расцеплять, то
сортировочная станция будет иметь дело не с N ориентированными объектами, а с N=2 объектами, которые можно
во всех отношениях и со всех точек зрения считать симметричными. Это наблюдение решило проблему ценой двух
1

уступок. Во-первых, поезда могли теперь состоять лишь из четного числа вагонов  недостающие вагоны могли
быть оплачены за счет экономии от сокращения числа туалетов, и, во-вторых, туалеты были расположены на
чуть-чуть неравных расстояниях. Но кого беспокоит лишний метр?
Хотя во времена, к которым относится наша история, человечество еще не было осчастливлено ЭВМ,
неизвестный, нашедший это решение, заслуживает звания первого компетентного программиста.
Я рассказывал эту историю в разных аудиториях. Как правило, программисты восхищались ею, а
менеджеры неизменно становились тем более раздраженными, чем ближе подходил рассказ к концу;
настоящим математикам, однако, не удавалось ухватить соль.
EWD, 1976
Мораль притчи  нужно уметь не только кодировать (верно записывать операторы программы), но и
правильно подходить к решению задачи в целом, т.е. адекватно выбирать структуры данных и алгоритмы
работы с ними.
Литература для дополнительного чтения
1. Д.Кнут. Искусство программирования, том 1. Основные алгоритмы. 3-е изд. М.: Вильямс, 2000.
2. Н.Вирт. Алгоритмы + структуры данных = программы. М.: Мир, 1985.
3. Н.Вирт. Алгоритмы и структуры данных. СПб: Невский диалект, 2001.
4. Т.Кормен, Ч.Лейзерсон, Р.Ривест. Алгоритмы: построение и анализ. М.: МЦНМО, 2001.
2 Информация
2.1 Введение. Сообщение и информация
Информатика была определена нами с использованием понятия информация. Термин информация (от
лат. informatio  разъяснение, изложение) был введен в середине прошлого века Клодом Шенноном
применительно к теории связи (передаче кодов) и в настоящее время получил очень широкое
распространение.
Строгого определения понятия информация нет, и обычно считается, что информация  это
передаваемые сведения, при этом информация (нечто абстрактное) передается от одного объекта другому
в виде конкретных сообщений.
Отсюда следует, что:
1. При передаче информации всегда существует объект, передающий ее (например, авторы этого
текста) и принимающий (в данном случае читатель).
2. Информация преобразуется передающим объектом в сообщение (в данном случае текст).
3. Сообщение, поступившее принимающему объекту (читателю), преобразуется им обратно в
информацию.
Сообщение без информации, т.е. само по себе, не существует. Любое сообщение несет информацию
(отрицание чего-то в сообщении  тоже информация).
Информация может преобразовываться передающим объектом в сообщения разными способами.
В нашем случае текст мог быть также произнесен и записан на магнитную ленту. Аналогично и
принимающий объект может получать сообщения по-разному: прочитать написанный текст, воспринять
его на слух и т.д.
Как в роли передающего объекта, так и в роли принимающего может выступать и живое существо,
и прибор. Если передающим и принимающим объектами являются приборы, рассмотрение сообщений и
информации не представляет сложностей, т.к. все происходящие при этом физические процессы хорошо
известны. Сложнее, когда передающим и/или принимающим объектом является орган чувств живого
существа. Но и здесь при передаче информации всегда присутствует физический носитель.
2

2.1.1 Связь сообщения и информации, их интерпретация и обработка
Связь между информацией и сообщением не является однозначной. Одна и та же информация может
быть передана различными сообщениями (например, на разных языках). Сообщение может содержать
ненужную информацию. Одно и тоже сообщение может нести разную информацию. Пример  известная
фраза Над всей Испанией безоблачное небо, переданная в сообщении о погоде, но означавшая начало
военных действий.
Следовательно, для однозначного восприятия информации объект, передающий сообщение, и
объект, его получающий, должны действовать в соответствии со строго определенными правилами
интерпретации сообщений, т.е. необходимо определить некоторое взаимно-однозначное отображение 
сообщений N в информацию I
I = (N)
Например, в фильме Бриллиантовая рука для сообщения N , равного фразе Черт побери!, было
определено правило , согласно которому (N) означало, что нужно прятать бриллианты в гипс.
Непосвященный человек интерпретировал бы эту фразу по-другому.
Обработка сообщений, в случае если один из объектов  человек, происходит в коре головного мозга,
и происходящие при этом процессы далеко не все изучены. Поэтому упрощенно будем считать, что при
передаче информации происходит изменение некоторой физической величины, называемой сигналом.
Характеристику сигнала, используемую для представления сообщения, будем называть параметром
сигнала. Если, например, рассмотреть светофор, то сигнал  световые волны, а параметр сигнала 
длина волны (соответствующая цвету  красному, желтому, зеленому).
2.1.2 Дискретные сообщения. Знаки. Алфавит
Сигнал называется дискретным, если параметр сигнала может принимать лишь конечное число значений.
Сообщения, переданные с помощью такого сигнала, называются дискретными сообщениями.
При обмене сообщениями обычно используются некоторые соглашения относительно их формы. Будем
рассматривать языковую форму, то есть случай, когда сообщения составлены на некотором языке.
Языковые сообщения состоят из последовательности знаков. При этом под знаками понимаются не
только буквы и цифры.
Знак  элемент некоторого конечного множества, которое называется набором знаков.
Набор знаков, в котором определен некоторый порядок, называется алфавитом.
Приведем несколько примеров наборов знаков:
1. Десятичные цифры: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
2. Шестнадцатиричные цифры: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F.
3. Знаки мужского и женского начала:  , 
4. Знаки планет (и Солнца): , ',  , & ,  , X, Y, Z, [, \
5. Знаки зодиака: , ], ^, _, , `, a, b, c, d, e, f
6. Фазы Луны: #, $, , %
7. Греческие буквы: ; ; ; Ж; ; ; ; ; ; ; ; ; ; ; o; ; ; ; ; ; ; ; ; !.
8. Наконец, наборы двоичных знаков (01, данет и т.п.), имеющие в информатике большое
значение.
Заметим, что алфавитами не являются наборы 3 и 6 (в них не определен порядок), а также то, что
некоторые знаки входят в разные наборы (алфавиты).
Как правило, дискретные сообщения из технических соображений либо из соображений чувственного
восприятия разбиваются на конечные последовательности знаков  слова. В свою очередь каждое слово
можно рассматривать тоже как знак, при этом набор знаков, элементы которого слова, будет шире
первоначального набора знаков, из которого составлены слова.
2.1.3 Наборы двоичных знаков. Слова. Коды. Символы
Слова над набором двоичных знаков называются двоичными словами. Вообще говоря, они не обязаны
иметь постоянную длину (азбука Морзе тому пример, хотя и с некоторой оговоркой), но если длина слов
постоянна, то говорят о n-разрядных двоичных словах.
Кодом или кодировкой называется правило, описывающее отображение одного набора знаков в другой
набор знаков (или слов). Так же называют и множество образов этого отображения. В частности, к таким
отображениям относятся шифры, и в этом случае образы  это шифровки.
Поясним на примере кодирования десятичных цифр двоичными словами. Здесь мы имеем два набора
знаков ({0, 1, 2, 3, 4, 5, 6, 7, 8, 9} и {0, 1}) и следующее правило отображения первого набора в слова над
вторым набором:
3

0 1 2 3 4 5 6 7 8 9
0 1 10 11 100 101 110 111 1000 1001
Очевидно, при кодировании должны приниматься во внимание свойства кодируемых объектов, при
кодировании чисел должны учитываться возможные действия с ними, при кодировании букв  их порядок
и т.д. Например, если действие, которые предполагается производить с числами, состоит только в их
сложении, римские цифры (с некоторой оговоркой)  самое простое представление. Сложение во многих
случаях сводится к механическому приписыванию слагаемых: I + II = III.
Знак вместе с его смыслом называется символом. Например, знак * часто используется в литературе
как символ звездочка, в математике  как символ умножения, в программировании  как символ
разыменования (Си) и т.д.
2.1.4 Шенноновские сообщения. Количество информации. Теорема кодирования Шеннона
Как ни странно это покажется на первый взгляд, но количество информации, содержащейся в сообщении,
можно измерить.
Пусть сообщения состоят только из знаков какого-то алфавита, и эти знаки появляются в сообщениях
с определенной вероятностью. Сообщения, в которых вероятности появления знаков не меняются со
временем, называются шенноновскими сообщениями. Именно такие сообщения и будем рассматривать
в дальнейшем.
По существу, количество информации  это мера затрат, необходимых для того, чтобы раскодировать
все знаки сообщения. Это несколько отличается от интуитивных представлений об информации, но дает
удобную для анализа модель.
Наиболее простой алфавит  двоичный, т.е. состоящий из двух знаков (например, 0 и 1 или точка и
тире). Количество информации, содержащееся в сообщении, состоящем из одного двоичного знака, примем
за единицу и будем называть битом. Очевидно, что при раскодировании такого сообщения требуются
минимальные затраты  следует сделать только один выбор между двумя альтернативными вариантами.
Рассмотрим, как может производиться анализ более сложных сообщений и как при этом измерить
затраты (количество информации). Для простоты будем считать, что информация  это текст, состоящий
только из букв {a, b, c, d, e, f, g}, которые кодируется в сообщениях двоичными словами следующим
образом:
a b c d e f g
.... .-.. -... -.-. --.. ---. ----
Разделим данное множество кодов на два {.... .-..} и {-... -.-. --.. ---. ----}. Полученные подмножества
снова разделим надвое и для подмножеств, содержащих более одного двоичного слова, будем повторять
процедуру деления, пока не получим одноэлементные подмножества. Результаты можно представить в
виде дерева, состоящего из подмножеств,
{.... .-.. -... -.-. --.. ---. ----}
|
/ \
/ \
{.... .-..} {-... -.-. --.. ---. ----}
| |
/ \ / \
/ \ / \
{....} {.-..} {-... -.-.} {--. ---. ----}
a b | |
/ \ / \
/ \ / \
{-...} {-.-.} {--..} {---. ----}
c d e |
/ \
/ \
{---.} {----}
f g
Предположим, что поступило сообщение
.-.. --.. ----
4

и его необходимо раскодировать.
Поскольку первый символ сообщения  точка, то первое двоичное слово попадает в подмножество {....
.-..}, а не альтернативное ему. Таким образом, один шаг по дереву вниз, в направлении отождествления
полученного первого слова, сделан.
Рассмотрение следующего знака (тире) позволяет выбрать одноэлементное подмножество {.-..},
соответствующее букве b, что и оканчивает анализ. Дальнейшее исследование знаков сообщения приводит
к выявлению букв e и g.
Таким образом, чтобы раскодировать первое слово (.-..), нам потребовалось сделать два шага вниз по
дереву, т.е. произвести два альтернативных выбора между его подмножествами, и при раскодировке всего
сообщения было сделано 9 альтернативных выборов (2 для отождествления буквы b, 3  e, и 4  g),
Из определения единицы информации (бита), видно, что один альтернативный выбор соответствует
1 биту информации. Поэтому можно сказать, что первое полученное двоичное слово дало 2 бита
информации, а все сообщение содержало 9 битов информации.
Очевидно, что отождествление  поиск определенного слова в множестве из n слов (n  2) всегда
можно представить посредством конечного числа следующих друг за другом альтернативных выборов.
Если символ встречается часто, то разумно количество выборов, требующихся для его распознавания,
сделать по возможности меньшим. Этого можно достичь, разбивая множество знаков на равновероятные
подмножества. В нашем примере это имело бы место при следующих вероятностях появления букв в
исходном тексте или, что тоже самое, соответствующих двоичных слов в сообщениях:
a b c d e f g
1/4 1/4 1/8 1/8 1/8 1/16 1/16
Средняя вероятность обращения при отождествлениях ко всем подмножествам второго горизонтального
уровня (т.е. {.... .-..} и {-... -.-. --.. ---. ----}) равна 1/2, третьего  1/4 и т.д.
Наблюдающиеся в реальных случаях вероятности не всегда позволяют разбивать множества точно на
равновероятные подмножества. Тем не менее, рассмотрим более детально множества знаков, для которых
это возможно. Если i-й знак в них выделяется после k i альтернативных выборов, то вероятность его
появления в (длинных) сообщениях p i = 1=2 k i (например, для знака g  i = 7; k i = 4; p i = 1=16 = (1=2) 4 ).
И соответственно наоборот для отождествления знака, вероятность появления которого p i , требуется
k i = log 2 (1=p i ) альтернативных выборов.
По определению количество информации (в битах), даваемой знаком Z i в сообщении, равно числу
выборов k i , т.е.
I i = log 2

1
p i

:
Среднее количество информации, приходящееся на один знак, равно произведению вероятности
появления знака p i на указанное выше количество информации
H =
X
i
p i I i =
X
i
p i log 2 (p i ):
Эту величину также называют энтропией источника сообщений. Термин энтропия был введен
Шенноном по совету фон Неймана, который заметил, что формулы, полученные для этой величины,
совпали с соответствующими формулами для энтропии в физике.
Если каждый выбор представить в виде двоичного знака (например, при выборе левого подмножества
в дереве брать 0, а при выборе правого  1), то отождествлению каждого знака в сообщении будет
соответствовать последовательность двоичных знаков, т.е. двоичное слово, которое можно рассматривать
как кодировку знака. В нашем примере это выглядит так
a b c d e f g
00 01 100 101 110 1110 1111
Как видно, подобные двоичные слова имеют разную длину, и знак, вероятность появления которого
p i , кодируется словом длиной N i , совпадающей с количеством сделанных альтернативных выборов, т.е.
N i = k i = log 2 (p i ). Поскольку отсюда следует, что
H =
X
i
p i N i ;
то становится ясным физический смысл H как средней длины слов при двоичном кодировании в
рассматриваемом (идеальном) случае.
5

В нашем примере первая кодировка (4-разрядными двоичными словам над набором знаков  точка и
тире) имела среднюю длину слова тождественно равную 4, вторая кодировка (двоичными числами разной
длины)  2.625 (H = 1/4*2 + 1/4*2 + 1/8*3 + 1/8*3 + 1/8*3 + 1/16*4 + 1/16*4), что в 1.5 раза меньше.
Обратимся теперь к более реальной ситуации, когда вероятности появления знаков не позволяют
разбить множества на равновероятные подмножества. При кодировании в этом случае код i-го знака
имеет некоторую длину ~
N i , и средняя длина двоичного слова равна
L =
X
i
p i ~
N i :
При известных вероятностях появления знаков p i ничто не мешает нам вычислить здесь и энтропию
источника H по приведенной ранее формуле. Соотношение между энтропией H и средней длиной слова
L для любых наборов знаков определяется теоремой Шеннона.
Теорема.
1. Имеет место неравенство H  L.
2. Для всякого источника сообщений можно найти такую кодировку, что разность L H будет
меньше любого заданного наперед числа.
Разность L H называется избыточностью кода. Если набор знаков можно точно разбить на
равновероятные подмножества, то, как мы видели, можно выбрать код с ~
N i = N i , и следовательно с
L = H .
Заметим, что на практике отдельные знаки редко встречаются с одинаковой вероятностью, и поэтому
кодирование с постоянной длиной кодовых слов, часто применяемое из технических соображений, в
большинстве случаев заведомо избыточно.
2.1.5 Обработка сообщений
Очевидно, что всякое правило обработки сообщений можно трактовать как отображение , которое
сообщениям N из некоторого множества сообщений S ставит в соответствие новые сообщения N 0 из
множества S 0 . Сообщения N и N 0  это последовательности знаков, которые могут рассматриваться
как последовательности букв, слов или предложений. Таким образом, обработку сообщений можно
представить как некоторое кодирование.
Чтобы правило служило основой для обработки сообщений, оно должно задавать определенный способ
построения сообщения N 0 = (N). Если множество S велико и задавать отображение  посредством
перечисления всех соответствий неэффективно, то необходимо задать конечное множество операций
(элементарных шагов) так, чтобы каждый переход можно было осуществить с помощью конечного числа
таких шагов. Таким элементарным шагом может быть, например, такой:
заменить подслово a 1 a 2 : : : a k 1 a k a k+1 : : : an на a 1 a 2 : : : a k 1 ba k+1 : : : an
Кроме того, нужно задать порядок выполнения элементарных шагов и условия завершения
преобразования.
2.2 Простейшие данные
Сведения, информацию, передаваемую компьютеру или получаемую от него, будем называть данными.
Сначала рассмотрим простейшие типы данных. Как правило, это группы данных, работа с которыми в
той или иной степени поддерживается на уровне инструкций, непосредственно выполняемых процессором.
Последнее накладывает определенные ограничения на представление этих данных или, иными словами,
на используемые правила интерпретации.
По техническим причинам для представления данных при их хранении и обработке в компьютере
используются двоичные знаки 0 и 1. Напомним, что любую информацию можно закодировать с
помощью двоичного алфавита (набора двоичных знаков). При этом, как мы знаем, необходимо установить
правила интерпретации. Эти правила будут разные для данных разного типа. Как следствие, одна и та же
последовательность двоичных знаков будет интерпретироваться по-разному. Например, слово 0100 0001
может означать и десятичное число 65, и символ латинского алфавита A.
6

2.2.1 Биты. Булевы алгебры. Операции
Да будет слово ваше: да, да; нет, нет; а что сверх этого,
то от лукавого
Евангелие от Матфея 5,37
Первое, что мы рассмотрим,  это биты. Слово бит уже встречалось нам ранее. Оно означало
единицу количества информации, содержащейся в сообщении. Теперь же мы сузим это понятие и
будем подразумевать под битом объект, который может принимать только два значения 0 или 1. В
англоязычной терминологии эти понятия различают  Bit и bit соответственно. Еще раз подчеркнем,
что алфавит, используемый для представления информации один и тот же (набор двоичных знаков),
но правила интерпретации для данных разного типа различны. Разными будут также и операции,
разрешенные для данных того или иного типа. Применительно к битам это логические операции. Свяжем
значение 1 с истиной (TRUE), а 0  с ложью (FALSE). Для данных этого (логического) типа
определены следующие операции:
И (умножение) 1 and 1 = 1; 1 and 0 = 0; 0 and 1 = 0; 0 and 0 = 0;
ИЛИ (сложение) 1 or 1 = 1; 1 or 0 = 1; 0 or 1 = 1; 0 or 0 = 0;
НЕ (дополнение) not 1 = 0; not 0 = 1
исключающее ИЛИ 1 xor 1 = 0; 1 xor 0 = 1; 0 xor 1 = 1; 0 xor 0 = 1.
(eXcluding OR)
Множество элементов с определенными таким образом тремя первыми операциями называют булевой
алгеброй в честь Джорджа Буля, издавшего в 1854 году сочинение Исследование законов мысли, на
которых основаны математические теории логики и теории вероятностей.
Булевой функцией является выражение, полученное из ее аргументов (элементов некоторой булевой
алгебры) путем сложения, умножения и взятия дополнения. Известно, что для каждой булевой алгебры
существует ровно 2 2n различных булевых функций n аргументов. В нашем случае возможны 4 булевы
функции одного аргумента  две постоянные, равные 0 и 1, тождественная f(x) = x и единственная
нетривиальная функция, представляющая собой операцию НЕ. Это легко видеть из следующей таблицы,
показывающей аргумент и значения этих функций:
x f 1 (x) f 2 (x) f 3 (x) f 4 (x)
0 0 1 0 1
1 0 1 1 0
Если рассмотреть булевы функции двух аргументов, то мы найдем только 10 нетривиальных функций.
Интересно, что все булевы функции одного и двух аргументов можно выразить через одну булеву
функцию. Такой функцией может быть и так называемый штрих Шеффера x 0
1 x 2 = not(x 1 and x 2 )
(неверно, что x 1 и x 2 ), и функция Пирса, равная (not x 1 ) and (not x 2 ) (ни x 1 и ни x 2 ). Выражения для
основных функций через штрих Шеффера таковы:
x 1 and x 2 = (x 0
1 x 2 ) 0 (x 0
1 x 2 );
x 1 or x 2 = (x 0
1 x 1 ) 0 (x 0
2 x 2 );
not x 1 = x 0
1 x 1 :
Это означает, что для представления всех логических операций в компьютере достаточно реализовать
только одну функцию (или штрих Шеффера, или функцию Пирса), а использование четырех приведенных
выше функций  явная избыточность. Она обусловлена простотой и близостью этих четырех функций
человеческому мышлению.
2.2.2 Байты. Символы. Кодирование (отображение одного набора знаков в другой)
Любые данные можно представить в виде последовательности битов. Однако на каждом этапе решения
реальной задачи мы должны использовать типы данных, наиболее подходящие для этого. Для элементов
булевых алгебр (например, логических переменных) это, конечно, биты, но для описания, скажем,
какой-нибудь внесолнечной планеты использование только битов сильно затруднило бы дело. Уровень
абстрагирования здесь должен быть много выше.
Предположим, мы обрабатываем тексты, написанные на каком-то языке. Если это английский язык,
то соответствующий алфавит должен содержать 62 различных кода (26 для латинских строчных букв, 26
для заглавных и 10 арабских цифр), а также коды для знаков препинания и некоторых других символов.
7

Не все символы равновероятны, а некоторые и вовсе могут отсутствовать в текстах, и чтобы уменьшить
избыточность кодирования, было бы правильно кодировать символы, встречающиеся чаще, меньшим
количеством битов (см. подробнее п. 2.1.4).
Однако практически все современные компьютеры работают только с данными фиксированного
размера, и наименьший размер  8 битов или 1 байт. Байт является также наименьшей адресуемой
частью памяти компьютера. Если бы адресовался каждый бит, адреса были бы чрезмерно длинными.
Итак, технические требования диктуют нам фиксированный размер кода символа (8 битов), и
поэтому мы затрачиваем для представления текстовой информации больше битов, чем это необходимо. В
этом заключается резерв для сжатия данных (точнее файлов), которое мы рассмотрим ниже.
Остается только смириться с навязанной равновероятностью всех символов. Для представления
латинских символов достаточно 7 битов (так называемый ASCII код), остальные 128 значений
(возникающие благодаря использованию 8-го бита) применяются для кодирования дополнительных
символов латинского алфавита (умляуты и т.п.), символов псевдографики или символов кириллицы.
Для того, чтобы закодировать стандартные и дополнительные символы латинского алфавита и
символы кириллицы одновременно 256 символов (8 битов) недостаточно. А ведь есть еще и большое
количество иероглифов, букв древних алфавитов и т.д.
Заметим, что отсутствие единого стандарта кодировки кириллицы приводит к определенным
проблемам при работе с русскоязычными текстами. В частности, в системе MS DOS используется
кодировка cp866, в MS Windows  cp1251, в Linux  koi8-r, на компьютерах Macintrosh  MAC,
в международной организации стандартов (ISO)  ISO-8859-5 и т.д. В результате имеем, например,
следующие представления символа кириллицы а (двоичные коды записаны в виде шестнадцатиричных
чисел):
cp866 A0
cp1251 E0
MAC E0
koi8-r C1
ISO D0
Unicode 0430
Развитие компьютеров привело к возможности выделять под символы 2 байта (16 битов), что
позволяет кодировать как минимум 65536 знаков. Первая кодировка, использующая 2 байта, получила
название Unicode. При этом для совместимости со старым программным обеспечением были разработаны
различные методы представления номеров символов в Unicode: UTF8, UTF16, UTF16LE, UTF16BE.
Сейчас разрабатывается четырехбайтовая кодировка UCS-4 (Universal Character Set).
2.2.3 Целые числа. Позиционные системы счисления. Дополнительный и обратный коды.
Операции. Переполнение
Вспомним, что такое позиционная система счисления. Обычные (десятичные) числа, как известно, можно
записать в виде (для простоты рассмотрим трехзначное число):
abc = a
10 2 + b
10 1 + c;
где 0  a; b; c < 10, а 10  это основание системы счисления.
Вместо 10 в качестве основания можно взять любое натуральное число (кроме 1), например 8
127 8 = 1
8 2 + 2
8 1 + 7 = 87 10
или 16
57 16 = 5
16 1 + 7 = 87 10
Разумеется, в позиционной системе с основанием N должно быть N цифр, включая 0. Например, в
шестнадцатеричной системе имеем следующие цифры: 0; 1; 2; 3; 4; 5; 6; 7; 8; 9; A; B; C; D;E;F . Пример не
позиционной системы  римские цифры.
Для перевода чисел из одной системы счисления в другую существуют простые правила. Проще
всего переводить числа в десятичную систему. Действуем прямо по определению (см. предыдущие три
формулы), выполняя все действия по правилам десятичной арифметики
1357 8 = 1
8 3 + 3
8 2 + 5
8 1 + 7 = 512 + 3
64 + 5
8 + 7 = 512 + 192 + 40 + 7 = 751
Для перевода десятичного числа M в систему счисления с основанием N следует разделить M нацело
на N , записанное также в десятичной системе, затем полученное частное снова разделить на N и делить
8

так, пока последнее частное не станет равным нулю. Представлением числа M в системе счисления N
будет обратная последовательность остатков деления. Можно было бы поступить точно также как и при
переводе в десятичную систему, если бы мы знали таблицу умножения, скажем, восьмеричной системы
также хорошо, как десятичной. Но нам легче делить в десятичной системе, чем умножать в восьмеричной.
Компьютеры используют двоичную с