Теоретические основы информатики

Москва
Горячая линия – Телеком
2016

Допущено УМО вузов по университетскому политехническому образованию 
в качестве учебника для студентов высших учебных заведений,
 обучающихся по направлению подготовки  «Информационные системы и технологии»

3-е издание, переработанное и дополненное

УДК 004:621.391(075) 
ББК 32.81 
     С77 
 

 
Стариченко Б. Е. 
С77  Теоретические основы информатики. Учебник для вузов. – 
3-е изд. перераб. и доп. – М.: Горячая линия – Телеком, 
2016. – 400 с.: ил. 
ISBN 978-5-9912-0462-0. 

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

ББК 32.81 

 
Адрес издательства в Интернет WWW.TECHBOOK.RU 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
ISBN 978-5-9912-0462-0                        ©  Б. Е. Стариченко, 2014, 2016 
©  Издательство «Горячая линия – Телеком», 2016 

Предисловие

Любая наука начинается с определения круга рассматриваемых и решаемых в ней проблем теоретического и практического
характера. Далее логика развития научного знания требует построения строгого понятийного аппарата — языка, принятого в
данной науке и обеспечивающего однозначную трактовку дефиниций специалистами. В научном языке определение новых терминов возможно двумя путями: аксиоматическим и операционным. B первом случае, принятом, в частности, в математике,
в виде постулатов вводится некоторый набор исходных определений, а уже через них выражаются все остальные понятия. Экспериментальные науки предложили другой тип определения —
операционный, когда понятие задается описанием способа нахождения количественной меры, характеризующей это понятие. Например, когда определяют скорость как перемещение, совершаемое материальной точкой за единицу времени, то подразумевается, что имеются способы измерения перемещения и времени, а
их отношение определит новую величину. Как правило, в естественнонаучных дисциплинах считается целесообразным вводить
в научный язык только те величины (понятия), которые могут
быть определены операционно.
После того как понятия и характеризующие их величины определены, необходимо выяснить наличие и характер связей между ними — в этом состоит основная задача любой науки. Связи
эти могут иметь характер законов, закономерностей или тенденций. Использование этих законов для решения задач практики
неизбежно связано еще с одним этапом научного исследования —
выделением естественных или абстрактных систем и построением их моделей. Все прикладные, «технические» аспекты и решения основываются на построенном таким образом теоретическом
фундаменте и, если угодно, являются его следствием.
Особенность информатики как научной и учебной дисциплины состоит в том, что прикладная ее составляющая оказывается
востребованной многими людьми, в том числе весьма далекими
от научной сферы. Такую ситуацию ни в коем случае не следует считать неправильной или нежелательной — напротив! Успехи информатики и технологий привели к возможности создания

Предисловие

уникального устройства — компьютера (и, в первую очередь, персонального), а также удобного программного обеспечения, позволяющего работать с ним в режиме черного ящика, т. е. решать
с его помощью прикладные задачи, не вникая в реализацию механизма решения. Именно благодаря этому обстоятельству компьютер и получил столь широкое распространение в современном
обществе; появился даже термин «пользовательский уровень
владения компьютером». По-видимому, этим объясняется тот
факт, что многие пособия по информатике ограничиваются лишь
рассмотрением элементов устройства компьютера, его программного обеспечения и, в последнее время, работы в сети Интернет. Не умаляя важности и необходимости подобных книг, автор
данного учебника поставил перед собой иную задачу — обсудить
теоретические основы науки информатики (что отражено в названии), оставляя за рамками рассмотрения прикладные аспекты.
При этом особое внимание автор постарался уделить терминологическому аппарату информатики, предлагая возможно более
строгие и корректные определения базовых понятий и демонстрируя логику их взаимосвязи, развития и взаимообусловленности.
Данное пособие написано на основе курса лекций, прочитанного студентам 1–2-го курсов Института математики, информатики и информационных технологий Уральского государственного педагогического университета (г. Екатеринбург). Это сказалось, в первую очередь, на использовании математического аппарата — он сведен к минимально приемлемому, с точки зрения
автора, уровню, когда доказательность соотношений не является самоцелью, а в качестве приоритетного выдвигается существо
вопроса. Для интересующихся доказательной стороной, а также
процессом развития идей теории информации учебник содержит
ссылки на работы «классиков» — Шеннона, Бриллюэна, Хэмминга, Бауэра и Гооза, Брассара, Глушкова и др; современные подходы легко найти самостоятельно в Интернете, но, как правило,
они сводятся к трактовке и пересказу прошлых работ.
Элементы теории вероятностей и математической логики, необходимые для понимания основного материала, изложены в приложениях.
Информатика — наука мировоззренческая уже хотя бы потому, что предметом ее изучения является одна из исходных категорий мироздания — информация. Учащиеся (любого уровня)
должны осознать фундаментальность и универсальность законов

Предисловие
5

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

таким образом выделяются определения понятий;

.
Помимо теоретического материала каждая глава содержит
примеры решения задач, иллюстрирующих рассматриваемые положения; в конце главы содержатся контрольные вопросы и задания для самостоятельной работы читателя — их выполнение
может служить критерием успешности освоения теории.
Следует также отметить, что данный теоретический курс
поддержан компьютерным лабораторным практикумом, который
охватывает практически все основные разделы дисциплины.
Предыдущее издание данного учебника состоялось довольно
давно — более 10 лет назад. Все эти годы курс читался студентам и, естественно, накопливались пожелания по его совершенствованию. Автор получил от читателей ряд замечаний, касавшихся содержания, изменилась учебная программа дисциплины,
возникла необходимость рассмотреть некоторые новые разделы
(например, элементы криптографии) — все это послужило причинами переработки, исправления и дополнения материала.
Автор будет признателен читателю за отзывы, замечания и
предложения по улучшению содержания учебника.
620219, г. Екатеринбург, ул. К. Либкнехта, 9, Уральский государственный педагогический университет, Ин-т математики, информатики и информационных технологий, кафедра информационно-коммуникационных технологий в образовании.
e-mail: bes@uspu.ru

Введение

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

Введение
7

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

∗ Интересующихся этой проблемой можно адресовать к книгам К. Поппера, Ф. Хайека, Г. Громова. См. например, К. Поппер. Логика и рост научного знания. М.: Прогресс, 1983; Ф. Хайек. Контрреволюция науки (этюды
о злоупотребления разумом). М.: Три квадрата, 2003; Г. Громов. От гиперкниги к гипермозгу. Информационные технологии эпохи Интернета. —
М.: Радио и связь, 2004.

Введение

• организация передачи информации во времени, т. е. накопление и хранение информации, накопленной предыдущими
поколениями людей, в интересах будущих;
• организация обработки информации, т. е. преобразование
имеющейся информации с целью ее использования для решения задач практики — управления, обучения, создания новой
информации (наука и искусство) и пр.
По ходу истории человечества улучшение показателей, характеризующих уровень развития перечисленных процессов, происходило неравномерно, что повлекло возникновение и затем преодоление нескольких информационных барьеров. Информационные барьеры образовывались в результате противоречий между информационными запросами общества и техническими возможностями их обеспечения. Эти барьеры оказывались препятствием на пути прогресса общества, и потому, как и в случае барьеров материальных или энергетических, человечество всегда
находило способ их преодоления. Таких информационных барьеров можно указать три.
I информационный барьер был преодолен приблизительно
в V тысячелетии до н.э. До того времени единственным хранилищем информации был мозг человека. Передача информации
была связана с механическим перемещением самого человека, и,
следовательно, скорость передачи оказывалась весьма низкой, а
передача ненадежной. Обработка информации также производилась человеком. Противоречие состояло в том, что человечеству
требовалась возможность сохранять во времени опыт и знания,
накопленные предыдущими поколениями, с тем, чтобы они могли
быть переданы поколениям последующим. Барьер был преодолен благодаря появлению письменности. Носителями информации стали камни, глиняные таблички, папирус, пергамент, береста, материя; позднее (во II веке н.э.) появилась бумага.
II информационный барьер сформировался к XV в. из-за
того, что в связи с развитием производства — появлением цехов,
мануфактур — возникла потребность в большом числе образованных людей, способных этим производством управлять. Противоречие состояло в том, что количество источников информации — рукописей, рукописных книг — не могло обеспечить обучение большого количества людей. Изобретение книгопечатания
(т. е. тиражирования информации на бумаге) в Европе в XV в.
И. Гутенбергом и в России в XVI в. И. Федоровым позволило
преодолеть данное противоречие. B то время скорость передачи

Введение
9

информации определялась скоростью механического перемещения ее бумажного носителя. Обработка производилась человеком. Поскольку основным носителем информации являлась бумага и именно этим определялись технологии накопления и распространения информации, по определению В.М. Глушкова, это
состояние можно назвать бумажной информатикой.
К началу XX в. ситуация изменилась, в первую очередь, в
отношении скорости распространения информации: сначала появилась почта; в XIX в. — телеграф, затем телефон; в 1905 г. —
радио; в 1920–1930-е годы — телевидение. В результате этих изобретений информация практически мгновенно могла быть доставлена в любую точку земного шара. Появились и новые устройства, обеспечивавшие иные (по сравнению с бумагой) принципы
записи информации для хранения — фотография, затем кино,
затем магнитная запись. Без существенных изменений оставалась лишь ситуация, связанная с переработкой информации, — эту
функцию по-прежнему выполнял только человек.
К III информационному барьеру человечество подошло во
второй половине XX столетия, когда общий объем информации,
которым оно располагало, вырос настолько, что суммарной пропускной способности человеческого мозга оказалось недостаточно
для ее переработки. Прогресс человечества стал зависеть от того,
удастся ли решить проблему автоматизации обработки информации. Варианты решения появились в 1945–46 гг., когда американские инженеры П. Экерт и Дж. Мокли построили первую цифровую вычислительную машину ЭНИАК∗, математик Дж. фон
Нейман описал принципы работы автоматических вычислительных устройств, а в 1948 г. К. Шеннон опубликовал знаменитую
работу «Математическая теория связи», где изложил математические принципы кодирования и передачи информации, а также
предложил метод объективного измерения количества информации — именно эти идеи и составили основу новой науки — ин
∗ Ранее, в 1943 году, британскими инженерами Т. Флауэрсом и М. Ньюманом была создана вычислительная машина «Колосс» (Colossus) для расшифровки сообщений немецких шифровальных машин, но из-за режима
секретности изобретение Colossus не было упомянуто в трудах по истории.
Однако еще ранее, в 1942 г., Дж. Атанасов и К. Берри разработали первый в
США цифровой компьютер ABC. B 1973 г. федеральный суд США аннулировал патент, ранее принадлежавший Экерту и Мокли, признав Атанасова
изобретателем первого электронного компьютера. — Прим. ред.

Введение

форматики. Итак, преодоление нового информационного барьера породило необходимость создания устройств, обеспечивающих
автоматизированную обработку информации, а это, в свою очередь, вызвало к жизни науку, которая определила бы принципы
работы таких устройств и общие принципы представления и преобразования информации.
Термин «информатика», обозначающий название новой науки, появился и прижился не сразу. B нашей стране в 60-е гг.
XX в. вопросы, связанные с разработкой, функционированием
и применением автоматизированных систем обработки информации, объединялись термином «кибернетика», хотя это было не
вполне верно, поскольку, по определению Н. Винера, кибернетика — это наука о законах управления в живой и неживой
природе, т. е. сфера ее интересов охватывает лишь часть (хотя
обширную и важную) используемых человеком информационных
процессов и систем. Более общую научную дисциплину, связанную с исследованием информации, в англоязычных странах стали называть Computer Science — «вычислительная наука». На
самом деле это название охватывает группу дисциплин, занимающихся различными аспектами применения и разработки компьютерной техники, — программирование, прикладная математика,
операционные системы и языки программирования, архитектура
компьютера и т. п.
В 1962 г. во Франции впервые появился термин Informatique — «информатика», он был позаимствован и с середины
1970-х гг. прочно вошел сначала в научно-технический обиход,
а затем стал общеизвестным и общепринятым. Однако предметную область дисциплины информатика установившейся считать
нельзя. Международный конгресс по информатике 1978 г. предложил следующее определение: «Понятие информатики охватывает области, связанные с разработкой, созданием, использованием и материально-техническим обслуживанием
систем обработки информации, включая машины, оборудование, математическое обеспечение, организационные аспекты, а также комплекс промышленного, коммерческого,
административного и социального воздействия». Сращивание информатики со средствами телекоммуникаций, как отмечает академик В.М. Глушков [14], привело к появлению нового
термина — телематика, хотя пока он не получил такого же
распространения, как информатика.
Для нашего рассмотрения вполне приемлемым можно считать определение академиков