Информатика: Программа и методические указания к самостоятельной работе студентов

ÌÈÍÈÑÒÅÐÑÒÂÎ ÎÁÐÀÇÎÂÀÍÈß ÐÎÑÑÈÉÑÊÎÉ ÔÅÄÅÐÀÖÈÈ

Ñàíêò-Ïåòåðáóðãñêèé ãîñóäàðñòâåííûé óíèâåðñèòåò àýðîêîñìè÷åñêîãî ïðèáîðîñòðîåíèÿ

ИНФОРМАТИКА Программа и методические указания к самостоятельной работе студентов

Ñàíêò-Ïåòåðáóðã 2003

Составитель В. А. Галанина Рецензент канд. техн. наук Л. Н. Бариков

Приводится программа дисциплины «Информатика», составленная в соответствии с требованиями государственного образовательного стандарта по направлению 654600 «Информатика и вычислительная техника». К основным разделам программы даются рекомендации по работе с литературой. Предназначены для студентов заочной формы обучения специальности 220300, изучающих дисциплину «Информатика». Подготовлены кафедрой компьютерных систем автоматизации и рекомендованы к изданию редакционно-издательским советом Санкт-Петербургского государственного университета аэрокосмического приборостроения.

© Санкт-Петербургский государственный университет аэрокосмического приборостроения, 2003

Подписано к печати 26.09.03. Формат 60×84 1/16. Бумага офсетная. Печать офсетная. Усл. печ. л. 0,74. Уч. -изд. л. 0,8. Тираж 100 экз. Заказ №

Редакционно-издательский отдел Отдел электронных публикаций и библиографии библиотеки Отдел оперативной полиграфии СПбГУАП 190000, Санкт-Петербург, ул. Б. Морская, 67

1. ПРОГРАММА ДИСЦИПЛИНЫ «ИНФОРМАТИКА» Введение Цель и задачи дисциплины. Понятие информатики. История развития информатики. Место информатики в ряду других фундаментальных наук. Обзор литературы. Раздел 1. Основные положения теории информации Понятие информации и ее измерение. Количество и качество информации. Единицы измерения информации. Информации и энтропия. Источники и носители информации. Виды и характеристики носителей. Раздел 2. Основы представления и обработки сигналов Сообщения и сигналы. Общая характеристика сигналов. Спектральное представление сигналов. Квантование сигналов. Теорема Котельникова. Модуляция и кодирование. Корректирующие коды. Систематические коды. Контроль по четности, по Хэммингу. Полиномиальные коды. Каналы передачи данных и их характеристики. Методы повышения помехоустойчивости передачи и приема. Современные технические средства обмена данных и каналообразующей аппаратуры. Раздел 3. Компьютерная обработка информации Основные виды обработки данных. Технические средства для хранения данных. Обработка аналоговой и цифровой информации. Устройства обработки данных и их характеристики. Представление информации в цифровых автоматах. Позиционные системы счисления. Методы перевода чисел. Форматы представления чисел с фиксированной и плавающей запятой. Двоичная арифметика. Коды: прямой, обратный, дополнительный, модифицированный. Выполнение арифметических операций с числами с фиксированной и плавающей запятой. Информационные основы контроля работы цифровых автоматов. 1

Раздел 4. Организация данных Типы и структуры данных. Способы организации данных. Оперативные структуры данных. Статические и динамические структуры данных. Деки, стеки, очереди, списки. Файловые структуры. Организация данных на устройствах с прямым и последовательным доступом. Базы данных. Рекомендуемая литература Основная 1. Кузьмин И. В., Кедрус В. А. Основы теории информации и кодирования. Киев: Вища шк., 1986. 2. Информатика: Учебник/ Под. ред. проф. Н. В. Макаровой. М.: Финансы и статистика, 1997. 3. Исаев И. П., Перова А. А. и др. Вычислительная техника в инженерных и экономических расчетах. М.: Транспорт, 1977. 295 с. 4. Костин А. Е., Шаньгин В. Ф. Организация и обработка структур данных в вычислительных системах: Учеб. пособие. М.: Высш. шк., 1987. Дополнительная 1. Брой М. Информатика: В 4 ч.: Пер. с нем. М.: Диалог – МИФИ, 1996. 2. Блейхут Р. Теория и практика кодов, корректирующих ошибки: Пер. с англ. М.: Мир, 1986. 3. Сергеев Н. П., Вашкевич Н. П. Основы вычислительной техники: Учеб. пособие. М.: Высш. шк., 1988. 4. Хемминг Р. Теория кодирования и теория информации. М.: Радио и связь, 1983. 2. МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ К ОСВОЕНИЮ ПРОГРАММЫ ДИСЦИПЛИНЫ Введение Литература: [2]. Вопросы для самопроверки 1. Что входит в понятие «информатика»? 2. Что входит в понятие «информация»? 2

Раздел 1. Основные положения теории информации Литература: [1, гл.6]. При изучении темы следует обратить внимание на следующее. Несмотря на совпадение выражений для определения энтропии и количества информации, эти два понятия принципиально различны. Энтропия является объективной характеристикой источника сообщений и может быть вычислена априорно, т. е. до получения сообщения. Количество же информации является апостериорной характеристикой и определяет количество информации, получаемое с поступлением сообщений. Вопросы для самопроверки 1. Поясните сущность понятий энтропии и количества информации. 2. В каких единицах измеряется энтропия? 3. Сформулируйте основные свойства энтропии. 4. Как определяется энтропия дискретной системы с равновероятными и неравновероятными состояниями? Раздел 2. Основы представления и обработки сигналов Литература: [1, гл. 2, 4; 5; 7]. Сигнал рассматривается как материальный носитель информации. Все сигналы делятся на детерминированные и случайные. С точки зрения передачи информации представляют интерес лишь случайные сигналы. В то же время математический аппарат, используемый для анализа детерминированных сигналов, гораздо проще аппарата анализа случайных сигналов, а выводы, полученный в результате исследований детерминированных сигналов, могут быть использованы для анализа случайных сигналов. Поэтому в данной теме рассматриваются детерминированные сигналы. Кроме того, в информационных системах применяются преимущественно электрические сигналы. В связи с этим ограничимся рассмотрением именно этих сигналов. При изучении данной темы следует обратить внимание на следующее. Основную информацию о сигнале можно получить из его спектрального представления, поэтому следует обратить внимание на различие спектров периодических и непериодических сигналов, на понятие практической ширины спектра. Для успешной передачи сигналов по линии связи осуществляется операция модуляции. Следует обратить внимание на амплитудную и частотную модуляции. 3

С целью обеспечения более надежной передачи информации осуществляется преобразование непрерывных сообщений в дискретные с помощью операции квантования. Существуют два способа квантования сигналов: квантование по времени и квантование по уровню. Следует обратить внимание на сущность равномерного и неравномерного квантования по времени, на значение теоремы Котельникова для равномерного квантования по времени, на возможность использования совместного квантования как по времени, так и по уровню для передачи сообщений с помощью кодоимпульсной модуляции. Для обеспечения достоверной передачи информации по каналам связи используется операция кодирования. Для повышения помехоустойчивости передачи используются корректирующие коды. При изучении данной темы следует обратить внимание на принципы помехоустойчивого кодирования, на способы построения корректирующих кодов, среди которых предлагается рассмотреть систематические коды, коды Хэмминга и циклические коды. Вопросы для самопроверки 1. Какие детерминированные сигналы относятся к элементарным сигналам? 2. Какие способы представления моделей сигналов известны? 3. В чем заключаются преимущества частотного метода представления информации? 4. При каких условиях периодическая функция может быть представлена рядом Фурье? 5. Что понимается под спектром амплитуды и спектром фаз? 6. Каковы характерные особенности спектра периодического сигнала? 7. При каких условиях непериодическая функция может быть представлена интегралом Фурье? 8. Что понимается под практической шириной спектра периодического и непериодического сигналов? Какие известны критерии выбора практической ширины спектра сигналов? 9. В чем сущность квантования непрерывного сигнала по времени и уровню? 10. Какова цель квантования сигналов? 11. Сформулируйте критерий Котельникова, в чем заключается его фундаментальное значение для теории и техники передачи сообщений? 12. В чем заключаются трудности практической реализации критерия Котельникова? 4

13. Что понимается под кодированием в широком и узком смысле? 14. Какова цель кодирования? 15. Какова особенность равномерных и неравномерных кодов? 16. В чем сущность помехоустойчивого кодирования? 17. Что понимается под значностью и весом кодовой комбинации? 18. Как определяется расстояние между кодовыми комбинациями? 19. Что такое вектор ошибки? 20. Какова связь корректирующей способности кода с кодовым расстоянием? 21. Какими показателями можно оценивать качество корректирующих кодов? 22. Каким требованиям должны удовлетворять исходные комбинации систематического кода? 23. Как строится производящая матрица систематического кода? 24. Каковы условия построения проверочной подматрицы? 25. Каков алгоритм определения проверочных символов по информационным с помощью проверочной матрицы? 26. Как определяется состав контрольных равенств с помощью проверочной матрицы? 27. Каковы корректирующие свойства кода с четным числом единиц? 28. Как строится код с удвоенным элементом, каковы его корректирующие свойства? 29. Какова логика построения и проверки инверсного кода, каковы корректирующие свойства этого кода? 30. Каков принцип построения кодов Хэмминга? 31. Каким образом составляются проверочные группы кода Хэмминга? 32. Каковы свойства циклического кода? 33. Какие известны способы построения циклических кодов? 34. Каким образом выбирается образующий полином циклического кода. По данной теме выполняется курсовая работа. По курсовой работе предусмотрены методические рекомендации, которые выдаются студентам на втором семестре. Раздел 3. Компьютерная обработка информации Литература: [3, гл. 2]. При изучении данной темы следует обратить внимание на способы представления чисел в различных системах счисления, на перевод чисел 5

из одной системы счисления в другую. Особое внимание следует уделить переводу дробных чисел, представлению чисел в ЭВМ, двоичной арифметике: сложению, вычитанию, умножению и делению чисел в ЭВМ. По данной теме выполняется контрольная работа. Раздел 4. Организация данных Литература: [4, гл. 2–4]. В данной теме рассматриваются типы и структуры представления данных в ЭВМ, а также способы организации данных. Вопросы для самопроверки 1. Какие структуры данных относятся к оперативным структурам? 2. Что такое статические, динамические и полустатические структуры? 3. Чем различаются структуры дек и очередь? 4. Какие существуют методы организации и обработки файлов данных? 5. Что такое база данных? 6. Какие функции выполняет система управления базой данных? По данной дисциплине для заочников предусмотрено выполнение одной контрольной работы в первом семестре и курсовой работы во втором семестре. Кроме того, в первом семестре предусмотрено выполнение лабораторной работы, отчет по которой может быть представлен в качестве реферата, написанного по любой из приведенных тем. После выполнения и сдачи контрольной работы и защиты отчета (реферата) в первом семестре студент допускается к экзамену. 3. МЕТОДИЧЕСКИЕ УКАЗАНИЯ К ВЫПОЛНЕНИЮ КОНТРОЛЬНОЙ РАБОТЫ При выполнении перевода чисел из одной системы счисления в другую следует обратить внимание на следующее. В случае, если используется способ деления на основание той системы, в которую переводится число, необходимо соблюдать следующее правило: все вычисления нужно производить в исходной системе счисления, т. е. в той, из которой данное число переводим. Основание системы, на которое делим переводимое число и результат, полученный при делении, т. е. разряды искомого числа, записываем в той системе, из которой переводим. 6

Рассмотрим типовое задание на контрольную работу. Пример 1. Перевести А8 = (753)8 из восьмеричной системы счисления в десятичную. Следуя правилу перевода с помощью деления на основание новой системы, необходимо делить А8 на число 10, представленное в восьмеричной системе счисления, т. е. на 12. Кроме того, все промежуточные действия проводятся также в восьмеричной системе. Следовательно, имеем ×

753 74 13 12

12 6

74

1 6⋅2 = (12)10 = (14)8

12 61 50 11

12 4

×

12 4 50

4⋅2 = (8)10 = (10)8

9

Таким образом, имеем (753)8 = (491)10 П р о в е р к а. Переведем (491)10 в восьмеричную систему. 491 48 11 8 3

8 61 56 5

8 7

Таким образом, получили (491)10 = (753)8 , т. е. перевод выполнен правильно. При использовании иного способа перевода из одной системы счисления в другую, основанного на представлении исходного числа в виде ряда А = аnqn–1 + аn–1qn–2 +…+ а1q + a0 + а–1q–1+ a–2q–2 +…+ a–mq–m, где аi – цифры переводимого числа; q – основание системы, из которой число переводим, записанное цифрами новой системы; n – число разрядов целой части переводимого числа, m – число значимых разрядов дробной части числа, действует следующее правило: все действия следует проводить в той системе, в которую данное число переводим. Пример 2. Перевести А10 = (2904)10 в восьмеричную систему. (2904) 10 = 2⋅123 + 11⋅122 + 0⋅121 + 4⋅120 = 2⋅1750 + 11⋅144 + 4⋅1 = (5530) 8 (8)10 = (12)8

(9)10 = (11)8 (1728)10 = (1750)8

7

Пример 3. Перевести А2 = (10111110)2 в десятичную систему. (10111110) = 1⋅2 7 + 0⋅2 6 + 1⋅2 5 + 1⋅2 4 + 1⋅2 3+ 1⋅2 2+ 1⋅2 1+ 0⋅2 0 = = 128 + 32 + 16 + 8 + 4 + 2 = (190)10 При переводе дробных чисел следует придерживаться тех же правил. Пример 4. Перевести число 0,25 из восьмеричной системы в десятичную.

8

0, 25×12 3 22 2 64 10 10 1 20

(10) 8 = (12)10 (10)10 = (12)8

25 × 12 52 25 322

Таким образом, имеем (0,25)8 = (0,3281)10 П р о в е р к а. Произведем обратное преобразование 0,

3281 × 8

2

6248

4

9984

7

9872

Таким образом, (0,3281)10 с точностью до второго знака равно (0,25)8, т. е. преобразование выполнено правильно. Следует обратить внимание на то, что при переводе чисел из системы счисления с большим основанием в систему счисления с меньшим основанием проще использовать первый способ. При обратном переводе – второй способ. Так, примеры 3.1 и 3.4 проще было выполнить, используя второй способ. (753) переведем из восьмеричной системы счисления в десятичную систему вторым способом: 7538 = 7' 82 +5' 8 + 3 = 49110. (0,25) переведем из восьмеричной системы счисления в десятичную: 0,258 = 2' 8–1 + 5' 8–2 = 0,32810. Соответственно, пример 3.2 проще выполнять первым способом. При выполнении заданий к контрольной работе можно пользоваться любым способом перевода чисел. Приведенные примеры взяты из литературы [3, § 6] . 8

4. ЗАДАНИЯ К КОНТРОЛЬНОЙ РАБОТЕ Задание 1. Перевести число А10 из десятичной системы в двоичную. Задание 2. Перевести число А10 из десятичной системы в восьмеричную. Задание 3. Перевести число А11 из десятичной системы в шестнадцатеричную. Задание 4. Перевести число А8 из восьмеричной системы в десятичную. Задание 5. Перевести число А 8 из восьмеричной системы в двоичную. Задание 6. Сложить числа А и В в двоичных кодах. Задание 7. Вычесть числа А и В в двоичных кодах. Задание 8. Умножить числа А и В в двоичных кодах. Задание 8. Разделить числа А и В в двоичных кодах. Произвести проверку правильности всех действий с помощью операции обратного перевода. Значения чисел А10, А11, А8, А и В для различных вариантов приведены в табл. 4.1. Таблица 4.1 № варианта

А10

А11

А8

А

В

1

5,25

754

753

7

–5

2 3 4 5 6 7

6,34 9,23 7,89 2,65 3,65 1,89

659 842 380 856 276 1265

462 371 163 1352 341 427

–9 15 6 9 7 8

8 –17 –24 –16 –25 –31

8

4,67

1047

352

23

–8

9 10 11 12 13 14 15

5,34 8,23 7,34 6,45 9,25 8,12 5,78

942 1865 765 476 1178 597 937

1462 263 1036 541 425 361 31,45

–8 –6 –16 25 11 9 –32

21 32 –21 –7 16 28 8

Примечание При выполнении перевода чисел А10 операцию производить до четвертого знака

При выполнении деления операцию производить с точностью до второго знака

9

5. ТЕМАТИЧЕСКИЙ ПЛАН ЛАБОРАТОРНЫХ РАБОТ 1. Квантование сигналов. Использование теоремы Котельникова. 2. Кодирование информации. Систематические коды. 3. Коды Хэмминга. 4. Циклические коды. 5. Алгоритмы преобразования чисел из одной системы счисления в другую. 6. Сложение и вычитание чисел c фиксированной и плавающей точкой. 7. Умножение двоичных чисел с фиксированной и плавающей точкой. 8. Деление двоичных чисел с фиксированной и плавающей точкой.

ОГЛАВЛЕНИЕ 1. Программа дисциплины «информатика» .......................................................... 1 2. Методические рекомендации к освоению программы дисциплины ......................................................................................................... 2 3. Методические указания к выполнению контрольной работы ....................... 6 4. Задания к контрольной работе .......................................................................... 9 5. Тематический план лабораторных работ ........................................................ 10

10