Основы информатики_Савельев А.Я_Учебник_2001
.pdfИнформатика в техническом университете
Информатика в техническом университете
Серия основана в 2000 году
РЕДАКЦИОННАЯ! КОЛЛЕГИЯ:
д-р техгг. наук И. Б. Федоров — главный редактор д-р техн. наук И. П. Нореиков — зам. главного редактора
д-р техн. наук Ю. М. Смирнов — зам. главного редактора д-р техн. науки, Ф. Горнее д-р техн. наук В. В. Девятков канд. техн. наук И. П. Иванов
д-р техн. наук А. А. Марков
д-р техн. наук В. А. Матвеев д-р техн. науки. В. Сюзев д-р техн. наук Б. Г, Трусов
д-р техн. наук В. М. Черненький
д-р техн. наук В. А. Шахнов
А.Я.Савельев
Основы
информатики
Допущено Министерством образования Российской Федерации
вкачестве учебника для студентов высших учебных заведений,
обучающихся по направлению подготовки дипломированных специалистов «Информатика и вычислительная техника»
Москва Издательство МГТУ имени Н.Э.Баумана
2001
УДК 002 (075.8) ББК73
Ci2
Рецензенты:
Кафедра «Автоматизарованные системы и вычислительная техника» |
|
|
Московского государственного университета (зав. кафедрой академик |
МАИ |
Bill, |
д-р техн. наук, проф. В- //. Карпов): |
|
|
д-р техн. наук. проф. В. В. Семенов (МАИ) |
|
|
Савельев А. Я. Основы информатики: Учеб. для вузов. — |
М.: Изд-во |
|
МГТУ им. Н. Э. Баумана, 2001. — 328 с,ил. (Сер. Информатика в техниче ском университете).
ISBN 5-7038-1515-0
Излагаютcя основные понятия информатики, методы измерения и представлеиня информации, спoсобы представления числовой информации в информаиионных системах, методы и алгоритмы выполнения арифметических и логических операций в различных системах счисления. Уделяется вниманиe методам контроля правильности функционирования цифровых автоматов как основному элементу информанцинных систем, а также способам защиты информации в вычислительных и информационных системах. Рассматриваются методы логического описания и проектирования на основе использования aппapaтa теории булевых функций, теории автоматов и автоматных языков.
Содержание учебника cooтветcтвyeт курсу лекций, который автор читает в МГТУ имН.Э.Бaумaна. Для студетов высших технических учебных заведений.
ББК 73
|
©А . Я.Савельев. 2001 |
|
® Московский юсуларсгвеиный (схинческнй |
|
университет им II Э Баумана, 2001 |
ISBN 5 703R 1515-0 |
© Издательство МГТУ им И Э Г>я\мзня, 20()| |
Оглавление |
|
Предисловие |
9 |
i. baiuBMC иинигия информатики |
i i |
1.1. Общие сведения об информации |
11 |
1.2. Структурная мера информации |
13 |
1.3. Статистическая мера информации |
15 |
1.4. Семантическая мера информации |
17 |
1.5. Преобразование информации |
19 |
1.6. Формы представления информации |
24 |
1.7. Передача информации |
26 |
Задание для самоконтроля |
29 |
2. Автомат как основной элемент информационных систем |
30 |
2.1. ЭВМ как автомат |
30 |
2.2. Лбстрактные автоматы и понятие алгоритма |
34 |
2.3. Основные понятия алгебры логики |
3S |
2.4. Свойства элементарных функций алгебры логики |
45 |
2.5. Аналитическое представление функций алгебры логики |
51 |
2.6. Совершенные нормальные формы |
5А |
2.7. Системы функций алгебры логики |
55 |
Задание для самоконтроля |
6J |
3. Представление чнсловой информации в информационных сис- |
|
iCMax |
6: |
3.1. Выбор системы счисления для представления числовой инфор |
|
мации |
6: |
3.2.11еревод числовой информации из одной позиционной системы в |
Ы |
другую |
|
3.3. Разновидности двоичных систем счисления |
7.' |
3.4. Системы счисления с отрицательным основанием |
7' |
3.5. Формы представления числовой информации |
79 |
3.6. Представление отрицательных чисел |
83 |
3.7. Погрешности представления числовой информации |
.86 |
Задание для самоконтроля |
88 |
4. Алгоритмы выполнения операций сложении и вычшания чисел на
двоичных сумматорах |
9{) |
4.1. Формальные правила двоичной арифметики |
90 |
4.2. Сложение чисел, представленных в форме с фиксированной заня |
|
той, на двоичных сумматорах |
93 |
4.3. Переполнение разрядной сетки |
98 |
4.4. Особенности сложения чисел, представленных в форме с плаваю |
|
щей запятой |
100 |
4.5. Методы ускорения операции сложения |
105 |
4.6. Оценка точности выполнения арифметических операций |
107 |
Задание для самоконтроля |
I 1 I |
5. Выполнение операций умножения чисел на двоичных сум |
|
маторах |
I 12 |
5.1. Методы умножения двоичных чисел |
112 |
5.2. Умножение чисел, представленных в форме с фиксированно!! запя |
|
той, на двоичном сумматоре прямого кода |
115 |
5.3. Особенности умножения чисел, представленных в форме с пла |
|
вающей запятой |
117 |
5.4. Умножение чисел, представленных в форме с фнксирова1нюй запя |
|
той, на двоичном сумматоре дополнительного кода |
119 |
5.5. Умножение чисел на двоичном сумматоре обратного кода |
121 |
5.6. Метод сокращенного умножения |
124 |
5.7. Ускорение операции умножения |
125 |
5.8. Матричные методы умножения |
133 |
5.9. Методы параллельного умножения с использованием игераитных |
|
структур. |
136 |
5.10. Систолический метод вычислений |
1 38 |
Задание для самоконтроля |
139 |
6. Выполнение операций деления чисел на двоичных сумматорах |
140 |
6-1- Методы деления двоичных чисел |
140 |
6-2. Деление чисел, представленных в форме с фиксированной запятой, |
|
на сумматорах обратного и дополнительного кода |
143 |
Оглавление
6.3. Особенности деления чисел, представленных в форме с плавающей
запятой |
148 |
6.4. Ускореине операции деления |
149 |
6.5. Параллельные методы деления с использованием |
итеративных |
cipyKiyp |
152 |
6.6. Операция извлечения квадратного корня |
15'/ |
Задание для самоконтроля |
159 |
7. Выполнение операций над десятичными числами в цифровых авто
магах.. |
16( |
7.1.11редставлепие десятичных чисел в Д-кодах |
16( |
7.2. Формальные правила поразрядного сложения в Д-кодах |
16^ |
7.3. Представление отрицательных чисел в Д-кодах |
16( |
7.4. BbiHOjnieHHe операций сложения и вычитания чисел в Д-кодах.. 16i |
|
7.5. Умножение чисел в Д-кодах |
П( |
7.6. Деление чисел в Д-кодах |
\Т. |
7.7. Извлечение квадратного корня в Д-кодах |
17: |
7.8. Перевод чисел в Д-код |
171 |
Задание для самоконтроля |
17! |
8. Кон I роль работы цифровою автомата |
181 |
8.1. Кодирование информации как средство обеспечения контроля ра |
|
боты автомата |
18' |
8.2. Основные понятия теории кодирования |
18! |
8.3. Методы эффективного кодирования информации |
18 |
8.4. Кодирование по методу четности-нечетности |
18 |
8.5. Коды Хэминга |
18 |
8.6. Контроль по модулю |
19 |
8.7. Выбор модуля для контроля |
19 |
8.8. Контроль логических операций |
19 |
8.9. Контроль арифметических операций |
20 |
8.10. Арифметические коды |
20 |
Задание для самоконтроля |
21 |
9. Способы защиты информации |
21 |
9.1. Особенности систем защиты информации |
21 |
9.2. Крипзографические методы защиты информации |
21 |
9.3. Л[п1аратные средства защиты |
22 |
9.4. 1 Ipoi раммные средства защиты |
22 |
9.5. Палежность средств защиты информации |
22 |
|
Оглавлети |
|
10. Методы логическою проектпрованпя |
228 |
|
10.1. Числовое и геометрическое представление функций алгебры ло |
||
гики |
: |
228 |
10.2. Минимизация логических функций. Метод неопределенных ко |
||
эффициентов для базиса И — ИЛИ — НЕ |
230 |
|
10.3. Метод Квайна |
|
232 |
10.4. Метод Квайна—Мак-Класки |
236 |
|
10.5. Метод минимизирующих карт |
239 |
|
10.6. Минимизация логических функций в базисе |
|
|
Ф , л , 1 |
|
241 |
10.7. Минимизация функций в базисах Шеффера и Пирса |
245 |
|
10.8. Реализация частотно-минимального метода |
248 |
|
11. Логическое опнсзние и анализ электронных схем |
260 |
|
11.1. Логические операторы электронных схем |
260 |
|
11.2. Электронные схемы с одним выходом |
265 |
|
11.3. Электронные схемы с несколькими выходами |
268 |
|
11.4. Не полностью определенные функции ашебры логики |
271 |
|
11.5. Синтез электронных схем с использованием свойств не полно |
|
|
стью определенных функций |
274 |
|
1 1.6. Времеинйе булевы функции |
276 |
|
11.7. Последовательностный автомат |
279 |
|
11.8. Анализ гтоследовательностиых автоматов с помощью реккуренг- |
||
ных булевых функций |
|
283 |
11.9. Разновидности триггерных схем |
285 |
|
Задание для самоконтроля |
290 |
|
12. Методы описания и синтеза цифровых автоматов |
292 |
|
12.1. Основные понятия теории автоматов |
292 |
|
12.2. Начальные языки описания цифровых автоматов |
297 |
|
12.3. Автоматные языки для задания автоматных отображений |
301 |
|
12.4. Соединение автоматов |
|
305 |
12.5. Синтез управляющего автомата |
310 |
|
12.6. Логическое проектирование управляющего автомата |
3 13 |
|
Задание для самоконтроля |
326 |
|
Список литературы |
|
327 |
ПРЕДИСЛОВИЕ
i 1редс!анлеипая вниманию чи1ателей книга «Введение в информати ку» — первая книга из многотомной серии «Информатика в техническом уиивсрси|е1е».
Н учебных планах подготовки дипломированного специалиста по на правлению «Информатика и вычислительная техника» дисциплина «Ин форматика» входит в состав фундаментального цикла дисциплин. Она соз дает теоретическую базу для изложения и понимания таких дисциплин, как «Организация ЭВМ и систем», «Алгоритмические языки и программироваmie», « 1еория автоматов» и других специальных курсов.
Основная uejib книги — познакомить студента с понятиями информа1ИКП, изложи 1ь методы и средства представления информации в компьюте рах и ин(|)ормационных системах, методы реализации арифметических и лот ических операций в цифровых автоматах, а также основы анализа и син теза логических схем Э В М и информационных систем.
Следуег натгомнить читателю, что термин «информатика» впервые был исЕюльзован французскими специалистами для определения комплекса за дач, связан1н>1х с применением Э В М для обработки, хранения и преобразо вания разнообразного вида информации. Однако этот термин не является общепризнанным, так как ряд стран, а именно — С Ш А , Канада и некото рые лагиноамерикаиские государства — придерживаются термина «ком пьютерные пауки». Вместе с тем, на Международном Конгрессе «Образо вание и информатика» (1996 год, Москва) отмечалось, что «информатика сегодня — это одна нз важных и перспективных «точек роста» мировой пауки, вокруг которой формируется новый комплекс наук об информации».
1'лавнь[М понятием курса «Информатика» является понятие цифрового автомата как средства для представления и обработки любых видов инфор мации. Автор здесь придерживается классического определения, введенно го академиком В. М. Глушковым: «Электронные цифровые машины с про граммным утгравлением представляют собой пример одного из наиболее распространенных в настоящее время преобразователей дискретной ин формации, называемых дискретными или цифровыми автоматами».
llf4'(UiCJiORue
В главах I, 3. 8 и 9 изложены способы представления н кодирования информации, методы конгроля и защиты информации. Эюч матернш! осно ван на результатах работ К. Шеннона, В. А. Котельникова. Р. Хэминга и др.
Главы 4, 5, 6 и 7 содержат описание методов и алгоритмов выполнения арифметических операций на двоичных и десятичных суммаюрах. Их ос новой послужили работы С. А. Лебедева, Р. К. Ричардса, В. А. Ме;и,инкова и др. Материал изложен таким образом, чтобы достичь максимальной общ ности содержания при возможности практического использования pe3yjrbтатов теории. При этом используется некая гипотетическая ЭВМ. обла дающая определенной структурой, описанной в примерах.
Главы 2, 10 и ! I посвящены логическим основам анализа и сингеза цифровых автоматов. Этот материал книги базируется на трудах Д. Буля,
В.И. Шестакова, Э. Мак-Класки и др.
Вглавах 2, 11 и 12 изложены некоторые положения теории цифровых автоматов, которые найдут дальнейшее развитие в специальном курсе «Теория цифровых автоматов». Основой материала этих глав являются труды В, М. Глушкова, Дж. фон-Иеймана, Э. Tlocia, А. Тыориига, С. В. Яб лонского и др. Читатель, интересующийся более глубоко вопросами анали за и синтеза цифровых автоматов, найдет эти сведения в специальной литературе.' iUifl лучшего усвоения материала глава 12 допо;и|ена конкрешыми примерами синтеза двух управляющих автоматов.
Воснову книги положен курс лекций но данной дисциплине, читаемый автором в течение нескольких лет в Московском государственном техниче ском университете имени Н. Э. Баумана.
Автор