Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

КАЗПОТРЕБСОЮЗ

КАРАГАНДИНСКИЙ ЭКОНОМИЧЕСКИЙ УНИВЕРСИТЕТ

Кафедра ИВС

Лабораторный практикум

по курсу: ИНФОРМАТИКА

для студентов всех специальностей

Караганда - 2010



Кафедра Информационно-вычислительных систем.

Автор: Муканова Ж.А., ст.преп. кафедры ИВС

Рецензент: Омарова Ш.Е., к.э.н., профессор кафедры ИВС

Лабораторный практикум по курсу «Информатика» обсужден на заседании учебно-методического семинара кафедры.

Протокол № 2 от 7 октября 2010 г.

Рекомендован к опубликованию научно-методическим и редакционно-издательским Советом КЭУ.



Содержание

• Тема 1. Информация и информационные процессы
• Тема 2. Булева алгебра. Логические операции
• Тема 3. Графы и деревья
• Тема 4. Архитектура компьютера
• Тема 5. Системы счисления
• Тема 6. Организация машины. Хранение информации
• Тема 7. Алгоритмы. Основы разработки алгоритмов
• Тема 8. Структуры данных. Блок-схемы
• Тема 9. Языки программирования
• Тема 10. Парадигмы программирования
• Тема 11. Основные элементы языка программирования Visual Basic for Application (VBA)
• Тема 12. Операторы, выражения, операции
• Тема 13. Операторы управления
• Тема 14. Программирование циклов
• Тема 15. Основные элементы операционных систем
• Тема 16. Утилиты
• Тема 17. Текстовый редактор Word
• Тема 18 Табличный процессор Exсel. Работа с таблицами
• Тема 19 Функции в Exсel
• Тема 20. Работа со списками данных в Exсel
• Тема 21. СУБД Access. Создание таблиц в Access
• Тема 22. Разработка запросов в Access
• Тема 23. Разработка форм и отчетов в Access
• Тема 24. Работа с пакетом PowerPoint
• Тема 25. Локально-вычислительные сети
• Тема 26. Глобальная сеть Internet
• Тема 27. Графические системы
• Тема 28. Работа с графическими приложениями
• Тема 29. Работа в среде графической программы
• Тема 30. Основы защиты информации

• Лабораторное занятие 1 (1час)

Тема: Информация и информационные процессы

Цель занятия: Изучить структуру информатики, виды и свойства информации, информационные процессы

Задание:

1. Рассмотреть информатику как единство науки и технологии и изучить структуру информатики.

2. Ознакомиться с видами и свойствами информации. Привести структуру информации

3. Измерить объем информации

4. Дать характеристику информационным процессам. Произвести операции с данными

5. Изучить носители данных

6. Составить отчет

Теоретические сведения

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

Теперь остановимся на основных информационных процессах.

1. Поиск

Поиск информации - это извлечение хранимой информации.

Методы поиска информации:

· непосредственное наблюдение;

· общение со специалистами по интересующему вас вопросу;

· чтение соответствующей литературы;

· просмотр видео, телепрограмм;

· прослушивание радиопередач, аудиокассет;

· работа в библиотеках и архивах;

· запрос к информационным системам, базам и банкам компьютерных данных;

· другие методы.

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

2. Сбор и хранение

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

Хранение информации - это способ распространения информации в пространстве и времени.

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

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

3. Передача

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

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

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

Декодирующее устройство - устройство для преобразования кодированного сообщения в исходное.

Деятельность людей всегда связана с передачей информации.

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

Рисунок 1.1 Процесс передачи информации

Каналы передачи сообщений характеризуются пропускной способностью и помехозащищенностью.

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

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

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

С точки зрения теории информации все то, что делает литературный язык красочным, гибким, богатым оттенками, многоплановым, многозначным,- избыточность. Например, как избыточно с таких позиций письмо Татьяны к Онегину. Сколько в нем информационных излишеств для краткого и всем понятного сообщения «Я Вас люблю!»

4. Обработка

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

Таблица 1.1

Примеры обработки информации

Примеры	Входная информация	Выходная информация	Правило
Таблица умножения	Множители	Произведение	Правила арифметики
Определение времени полета рейса "Москва-Ялта"	Время вылета из Москвы и время прилета в Ялту	Время в пути	Математическая формула
Отгадывание слова в игре "Поле чудес"	Количество букв в слове и тема	Отгаданное слово	Формально не определено
Получение секретных сведений	Шифровка от резидента	Дешифрованный текст	Свое в каждом конкретном случае
Постановка диагноза болезни	Жалобы пациента + результаты анализов	Диагноз	Знание + опыт врача

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

Рисунок 1.2 Обработка информации по принципу «черного ящика»



5. Использование

Информация используется при принятии решений.

· Достоверность, полнота, объективность полученной информации обеспечат вам возможность принять правильное решение.

· Ваша способность ясно и доступно излагать информацию пригодится в общении с окружающими.

· Умение общаться, то есть обмениваться информацией, становится одним главных умений человека в современном мире.

Компьютерная грамотность предполагает:

· знание назначения и пользовательских характеристик основных устройств компьютера;

· Знание основных видов программного обеспечения и типов пользовательских интерфейсов;

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

Информационная культура пользователя включает в себя:

· понимание закономерностей информационных процессов;

· знание основ компьютерной грамотности;

· технические навыки взаимодействия с компьютером;

· эффективное применение компьютера как инструмента;

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

· применение полученной информации в практической деятельности.

6. Защита

Защитой информации называется предотвращение:

· доступа к информации лицам, не имеющим соответствующего разрешения (несанкционированный, нелегальный доступ);

· непредумышленного или недозволенного использования, изменения или разрушения информации.

Более подробно о защите информации мы остановимся далее.

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

Контрольные вопросы

1. Поиск, какой информации вы осуществляете при работе со словарями: орфографическим, толковым, энциклопедическим?

2. Назовите, какие методы поиска информации использовал Шерлок Холмс в своей работе?

3. Является ли поиск решения конкретной математической или физической задачи поиском информации?

4. Опишите процедуру вашего поиска в виде последовательности действий.

5. Что такое эвристический метод поиска информации?

6. Как люди могут узнать о жизни своих предков, живших много лет назад?

7. Как хранится информация на фотопленке? В каком виде представлена эта информация?

8. Приведите примеры передачи информации в природе и обществе.

9. Приведите примеры из истории и литературы, когда при передачи информация преднамеренно искажалась. К чему это привело?

10. На уроке информатики. Вовочка (думает Очень хочется пить!») говорит Вера Ивановна, можно выйти?» Вера Ивановна (думает Наверное, он не знает урока и надеется, что за оставшиеся 5 минут до конца урока я не успею его спросить».) говорит Вовочка к доске!» Определите в данном примере источник информации, кодирование и декодирование, канал связи, приемник информации, помехи и причину их возникновения.

Лабораторное занятие 2 (1час)

Тема: Булева алгебра. Логические операции

Цель занятия: рассмотреть основы дискретной математики (функции, отношения, множества, основы логики, графы и деревья)

Задания:

1. Изучить функции, отношения, множества

2. Ознакомиться с основами логики (булевой алгеброй), логикой высказываний, логическими связками, таблицей истинности

3. Произвести логические операции. Рассмотреть формулы и их преобразование

4. Составить отчет

Теоретические сведения

Используется аппарат алгебры логики. Основные положения алгебры логики разработал в XIX в. английский математик Джордж Буль. Алгебру логики называют также булевой алгеброй.

В булевой алгебре различают двоичные переменные и переключательные функции.

Двоичные переменные могут принимать два значения: 0 и 1. Они называются также логическими или булевыми переменными и обозначаются символами х₁,x₂,х₃,...

Переключательные функции (ПФ) зависят от двоичных переменных. Они, как и аргументы, могут принимать лишь два значения: 0 или 1. ПФ называют также логическими или булевыми функциями. Будем обозначать ПФ в виде f(х₁,x₂,х₃,...). указывая в скобках аргументы, либо в виде y₁,y₂,y₃,... . ПФ в свою очередь могут служить аргументами еще более сложных логических функций. Следовательно, можно построить ПФ любой заранее заданной сложности, пользуясь ограниченным числом логических связей.

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

Набор переменных -- это совокупность значений двоичных переменных, каждая из которых может быть равна 0 или 1. Если число аргументов (независимых переменных) ПФ равно n (т.е. х₁,x₂,х₃,...x_n), то существует 2 различных сочетаний этих переменных, т. е. наборов.

Таблица 2.1 представляет собой таблицу истинности для некоторых ПФ f₁ и f₂, зависящих от двоичных переменных х₁,x₂,х₃. Так как n = 3 (три переменных), таблица 2.1 содержит 8 строк, соответствующих 2³ = 8 наборам переменных х₁,x₂,х₃. Для каждого набора в таблица 2.1 записаны значения ПФ f₁ и f₂, равные 0 или 1. По таблице истинности записывается аналитическое выражение для ПФ.

Таблица 2.1

х1	х2	х3	f1	f2
0	0	0	0	1
0	0	1	1	0
0	1	0	0	1
0	1	1	1	0
1	0	0	0	0
1	0	1	1	0
1	1	0	0	1
1	1	1	0	1

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

Логическое отрицание (функция НЕ). Логическим отрицанием переменной х называется такая ПФ f₁(x), которая имеет значение 1, когда x = 0 и значение 0, когда х= 1. ПФ НЕ обозначается в виде и читается f₁ есть (эквивалентно) не х».

Таблица 2.2 представляет собой таблицу истинности логической функции НЕ.

Таблица 2.2

х	f1
0	1
1	0

Логическое умножение (конъюнкция). Конъюнкция двух (или любого другого числа) переменных х₁ и х₂ принимает значение 1 только на наборе, в котором все переменные имеют значения 1. На остальных наборах эта функция имеет значение 0.

Таблица 2.3

x1	x2	f2
0	0	0
0	1	0
1	0	0
1	1	1

Таблица 2.3 представляет собой таблицу истинности конъюнкции двух переменных х₁ и x₂. ПФ конъюнкция обозначается в виде и читается f₂ есть (эквивалентно) х₁ и x₂».

Для обозначения конъюнкции можно использовать символы или &. Конъюнкция называется также функцией И, так как она имеет значение 1, только если первый и второй аргументы имеют значения 1.

Логическое сложение (дизъюнкция). Дизъюнкция двух (или любого другого числа) переменных х₁ и х₂ имеет значение 0 только на наборе, в котором все переменные имеют значение 0. Если хотя бы одна из переменных равна 1, функция будет иметь значение 1.

Таблица 2.4 есть таблица истинности для дизъюнкции двух переменных х₁ и х₂. ПФ дизъюнкция записывается в виде и читается f₃ есть (эквивалентно) х₁ или x₂». Кроме символа + , для дизъюнкции употребляется символ V.

Так как функция дизъюнкции имеет значение 1, если первый или второй аргументы имеют значение 1, операция дизъюнкции называется также операцией ИЛИ.

Таблица 2.4

x1	x2	f3
0	0	0
0	1	1
1	0	1
1	1	1

Элементарные логические функции НЕ, И, ИЛИ являются основными логическими функциями. Имеется еще несколько логических функций, производных от основных функций (т.е. выражающихся через функции НЕ, И, ИЛИ), которые реализуются соответствующими электронными элементами и так часто встречаются в схемотехнике ЭВМ, что им были даны собственные названия. Рассмотрим эти функции.

Отрицание конъюнкции (операция И -- НЕ). Эта функция образуется путем отрицания результата, получаемого при выполнении операции И. Таблица 2.5 есть таблица истинности операции И -- НЕ для двух переменных. Из сравнения таблиц 2.3 и 2.5 видно, что ПФ И -- НЕ является отрицанием (операцией НЕ) конъюнкции. ПФ И -- НЕ записывается в виде



Таблица 2.5

x1	x2	f4
0	0	1
0	1	1
1	0	1
1	1	0

Отрицание дизъюнкции (операция ИЛИ -- НЕ). Эта операция образуется путем отрицания результата, полученного при выполнении операции ИЛИ. Таблица 2.6 представляет собой таблицу истинности операции ИЛИ -- НЕ для двух переменных. Из сравнения таблиц 2.4 и 2.6 видно, что ПФ ИЛИ -- НЕ является отрицанием (операцией НЕ) дизъюнкции. ПФ ИЛИ -- НЕ записывается в виде

Таблица 2.6

x1	x2	f5
0	0	1
0	1	1
1	0	1
1	1	0

ИСКЛЮЧАЮЩЕЕ ИЛИ (операция НЕРАВНОЗНАЧНОСТЬ или СЛОЖЕНИЕ ПО МОДУЛЮ ДВА). Данная функция имеет значение 1 на тех наборах переменных, в которых число единиц нечетно. Для двух переменных операция НЕРАВНОЗНАЧНОСТЬ иллюстрируется таблицей истинности (таблица 2.7). Эта операция записывается для двух переменных в виде /

Операция НЕРАВНОЗНАЧНОСТЬ выражается через операции НЕ, И, ИЛИ в виде .



Таблица 2.7

x1	x2	f6
0	0	0
0	1	1
1	0	1
1	1	0

Операция ИСКЛЮЧАЮЩЕЕ ИЛИ -- НЕ (РАВНОЗНАЧНОСТЬ). Функция РАВНОЗНАЧНОСТЬ представляет собой отрицание операции ИСКЛЮЧАЮЩЕЕ ИЛИ.

Данная операция имеет значение 1 на тех наборах переменных, которые содержат четное число единиц. Для двух переменных операция ИСКЛЮЧАЮЩЕЕ ИЛИ -- НЕ представлена таблицей истинности (таблица 2.8). Эта операция записывается для двух переменных в виде

Таблица 2.8

x1	x2	f6
0	0	1
0	1	0
1	0	0
1	1	1

Операция ИСКЛЮЧАЮЩЕЕ ИЛИ -- НЕ выражается через операции НЕ, И, ИЛИ в виде .

Задания для самостоятельного выполнения:

Даны двоичных числа А и В (данные в таблице). Выполнить операции:

- отрицание

- логическое сложение

- отрицание ИЛИ

- логическое умножение

- отрицание И

- исключающее ИЛИ

- отрицание исключающего ИЛИ

Вариант	А	В
1.	1111	0101
2.	1011	0110
3.	1010	1011
4.	1010	1101
5.	1101	1011
6.	0110	0110
7.	0001	1001
8.	1001	0010
9.	1010	1100
10.	1011	1101
11.	1001	0111
12.	1011	0011
13.	1001	1111
14.	0001	1010
15.	1101	1110

Лабораторное занятие 3 (1час)

Тема: Графы и деревья

Цель занятия: изучить графы и деревья

Задание:

1. Рассмотреть графы и деревья

2. Изучить неориентированные и ориентированные графы, стратегии обхода графов

3. Привести примеры графов и деревьев

4. Оформить отчет

Теоретические сведения

Граф - это двойка <V, E>, где V - непустое множество вершин, а Е - множество ребер, соединяющих эти вершины попарно. Две вершины, связанные между собой ребром, равноправны, и именно поэтому такие графы называются неориентированными: нет никакой разницы между «началом» и «концом» ребра.

Таблица 3.1

Примеры неориентированных графов

Граф	Вершины	Ребра
Семья	Люди	Родственные связи
Город	Перекрестки	Улицы
Домино	Костяшки	Возможность

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

Например, три графа на рисунке 3.1 совпадают, а два графа на рисунке 3.2 - различны.

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

Рисунок 3.1 Три способа изображения одного графа

Ребро е и вершина v называются инцидентными друг другу, если вершина v является одним из концов ребра е.



Рисунок 3.2 Пример двух разных графов

Рисунок 3.3 Псевдограф

Любому ребру инцидентно ровно две вершины, а вот вершине может быть инцидентно произвольное количество ребер, это количество и определяет степень вершины. Изолированная вершина вообще не имеет инцидентных ей ребер (ее степень равна 0).

Две вершины называются смежными, если они являются разными концами одного ребра (иными словами, эти вершины инцидентны одному ребру). Аналогично, два ребра называются смежными, если они инцидентны одной вершине.

Путь в графе - это последовательность вершин (без повторений), в которой любые две соседние вершины смежны. Например, в графе, изображенном на рисунке 3.1, есть два различных пути из вершины a в вершину с: adbc и abc.

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

Граф называется связным, если все его вершины взаимно достижимы.

Компонента связности - это максимальный связный подграф. В общем случае граф может состоять из произвольного количества компонент связности. Заметим, что любая изолированная вершина является отдельной компонентой связности. На рисунке 3.4 изображен граф, состоящий из четырех компонент связности: [abhk], [gd], [c] и [f].

Длина пути - количество ребер, из которых этот путь состоит. Например, длина уже упомянутых путей adbc и abc (рисунок 3.1) - 3 и 2 соответственно.

Рисунок 3.4. Несвязный граф

Говорят, что вершина v принадлежит k-му уровню относительно вершины u, если существует путь из u в v длиной ровно k ребер. Одна и та же вершина может относиться к разным уровням. Например, в графе, изображенном на рисунке 3.1, относительно вершины a существует 4 уровня:

0) a;

1) b, d;

2) b, d, c (пути adb, abd, abc);

3) c (путь adbc).

Расстояние между вершинами u и v - это длина кратчайшего пути от u до v. Из этого определения видно, что расстояние между вершинами a и c в графе на рисунке 3.1 равно 2.

Цикл - это замкнутый путь. Все вершины в цикле, кроме первой и последней, должны быть различны. Например, циклом является путь abda в графе на рисунке 3.1.

Эйлеров граф - это граф, в котором существует цикл, содержащий все ребра графа (вершины могут повторяться). Именно такие графы положительно решают упомянутую в начале лекции задачу о кенигсбергских мостах. Например, граф на рисунке 3.5 является Эйлеровым: искомым циклом в нем будет dbacfbcd.



Рисунок 3.5 Граф Эйлера

Гамильтонов граф - это граф, в котором существует цикл (без повторений), содержащий все вершины графа (рисунок 3.5; искомый цикл: abdfca).

Ориентированный граф (орграф) - это граф, все ребра которого имеют направление. Такие направленные ребра называются дугами. На рисунках дуги изображаются стрелочками (рисунок 3.6).

Рисунок 3.6 Орграф

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

Если в графе присутствуют и ребра, и дуги, то его называют смешанным.

Все основные понятия, определенные для неориентированных графов (инцидентность, смежность, достижимость, длина пути и т.п.), остаются в силе и для орграфов - нужно лишь заменить слово «ребро» словом «дуга». А немногие исключения связаны с различиями между ребрами и дугами.

Степень вершины в орграфе - это не одно число, а пара чисел: первое характеризует количество исходящих из вершины дуг, а второе - количество входящих дуг.

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

Таблица 3.2

Примеры ориентированных графов

Граф	Вершины	Дуги
Чайнворд	Слова	Совпадение последней и первой букв (возможность связать два слова в цепочку)
Стройка	Работы	Необходимое предшествование (например, стены нужно построить раньше, чем крышу, т. п.)

Взвешенный (другое название: размеченный) граф (или орграф) - это граф (орграф), некоторым элементам которого (вершинам, ребрам или дугам) сопоставлены числа. Наиболее часто встречаются графы с помеченными ребрами. Числа-пометки носят различные названия: вес, длина, стоимость.

Замечание: Обычный (не взвешенный) граф можно интерпретировать как взвешенный, все ребра которого имеют одинаковый вес 1.

Длина пути во взвешенном (связном) графе - это сумма длин (весов) тех ребер, из которых состоит путь. Расстояние между вершинами - это, как и прежде, длина кратчайшего пути. Например, расстояние от вершины a до вершины d во взвешенном графе, изображенном на рисунке 3.7, равно 6.

Рисунок 3.7. Взвешенный граф



N-периферия вершины v - это множество вершин, расстояние до каждой из которых (от вершины v) не меньше, чем N.

Таблица 3.3

Примеры взвешенных графов

Граф	Вершины	Вес вершины	Ребра (дуги)	Вес ребра (дуги)
Таможни	Государства	Площадь территории	Наличие наземной границы	Стоимость получения визы
Супер-чайнворд	Слова	-	Совпадение конца и начала слов(возможность "сцепить" слова)	Длина пересекающихся частей

Существует довольно большое число разнообразных способов представления графов. Однако мы изложим здесь только самые полезные с точки зрения программирования.

Матрица смежности S_m - это квадратная матрица размером NЧN (N - количество вершин в графе), заполненная единицами и нулями по следующему правилу: Если в графе имеется ребро e, соединяющее вершины u и v, то S_m[u,v] = 1, в противном случае S_m[u,v] = 0.

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

Задать взвешенный граф при помощи матрицы смежности тоже возможно. Необходимо лишь внести небольшое изменение в определение:

Если в графе имеется ребро e, соединяющее вершины u и v, то S_m[u,v] = ves(e), в противном случае S_m[u,v] = 0.

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

В качестве примера приведем матрицы смежности для трех графов, изображенных на рисунке 3.5, рисунке 3.6 и рисунке 3.7.

Таблица 3.4

Примеры матриц смежности

Граф Эйлера (рисунок 3.5)	Орграф (рисунок 3.6)	Взвешенный граф (рисунок 3.7)
	a	b	c	d	f		1	2	3	4	5		a	b	c	d
a	0	1	1	0	0	1	0	1	0	1	0	a	0	1	10	0
b	1	0	1	1	0	2	0	0	0	0	0	b	1	0	2	10
c	1	1	0	1	1	3	1	1	0	0	1	c	10	2	0	3
d	0	1	1	0	1	4	0	0	1	0	0	d	0	0	3	0
f	0	0	1	1	0	5	0	0	0	0	0

Удобство матрицы смежности состоит в наглядности и прозрачности алгоритмов, основанных на ее использовании. А неудобство - в несколько завышенном требовании к памяти: если граф далек от полного, то в массиве, хранящем матрицу смежности, оказывается много «пустых мест» (нулей). Кроме того, для «общения» с пользователем этот способ представления графов не слишком удобен: его лучше применять только для внутреннего представления данных.

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

<номер_начальной_вершины> <номер_конечной_вершины> [<вес_ребра>]

В качестве примера приведем списки ребер (дуг), задающие те же три графа с рисунка 3.5, рисунка 3.6 и рисунка 3.7.



Таблица 3.5

Примеры списков ребер (дуг)

a b a c b c b d c d c f f d b f	1 2 1 4 3 1 3 2 3 5 4 3	a b 1 a c 10 b c 2 b d 10 c d 3

Если задается ориентированный граф, то номера вершин понимаются как упорядоченная пара, а если граф неориентированный - как неупорядоченная.

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

<номер_начальной_вершины>: <номера_смежных_вершин>

Наиболее естественно применять этот способ для задания орграфов, однако и для остальных вариантов он тоже подходит.

В качестве примера приведем списки смежности, задающие все те же три графа, изображенные на рисунке 3.5, рисунке 3.6 и рисунке 3.7.

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



Таблица 3.6

Примеры списков смежности

a: b c b: c d f c: d f d: f	1: 2 4 3: 1 2 5 4: 3	b: a 1 c 2 d 10 c: a 10 d 3

Дерево - это частный случай графа, наиболее широко применяемый в программировании.

Существует довольно много равносильных определений деревьев, вот лишь некоторые из них.

1. Дерево - это связный граф без циклов.

2. Дерево - это связный граф, в котором при N вершинах всегда ровно N-1 ребро.

3. Дерево - это граф, между любыми двумя вершинами которого существует ровно один путь.

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

Таблица 3.7

Примеры деревьев

Дерево	Вершины	Ребра (дуги)
Армия	Солдаты и офицеры	Иерархия (командир - подчиненный)
Династия (родословная по мужской4 линии)	Монархи	Отношение "отец - сын"

Рисунок 3.8 Корневое дерево высоты 3

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

Корневое дерево - это ориентированное дерево, в котором можно выделить вершины трех видов: корень, листья (другое их название: терминальные вершины) и остальные вершины (нетерминальные); причем должны выполняться два обязательных условия:

1. из листьев не выходит ни одна дуга; из других вершин может выходить сколько угодно дуг;

2. в корень не заходит ни одна дуга; во все остальные вершины заходит ровно по одной дуге.

Традиционно в математике и в родственных ей науках (в том числе и в теоретическом программировании) деревья «растут» вниз головой: это делается просто для удобства наращивания листьев в случае необходимости. Таким образом, на рисунках корень дерева оказывается самой верхней вершиной, а листья - самыми нижними.

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

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

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

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

Задания для самостоятельного выполнения:

1. Построить неориентированный граф и вычислить длину пути от одной из вершин ко всем остальным.

2. Построить ориентированный граф и вычислить длину пути от одной из вершин ко всем остальным.

Лабораторное занятие 4 (1 час)

Тема: Архитектура компьютера

Цель занятия: изучить представление данных в компьютере, логические элементы компьютера.

Задание:

1. Ознакомиться с историей архитектуры компьютеров

2. Рассмотреть логические элементы компьютера: вентили, триггеры, счетчики, регистры

3. Изучить представление данных в компьютере

4. Освоить представления числовых и нечисловых данных, знаковые представления и представления в дополнительном коде

5. Привести примеры представления данных

6. Составить отчет

Теоретические сведения

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

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

История вычислительной техники началась едва ли не раньше, чем окончательно сформировалась понятие числа. Неспроста в некоторых языках слово "цифра" происходит от слова "палец" - поначалу счет был неотделим от загибания пальцев. Пальцы стали первой вычислительной техникой. Великий переворот в вычислительной технике произошел с изобретением абака. Даже если вы не слышали этого слова, вы встречали, и не раз, русскую разновидность этого прибора - счеты. Абак долгое время играл особую роль в арифметике (как в геометрии - циркуль и линейка): задача считалось решенной, только если было указано, как необходимые вычисления выполнить на абаке. Существовала целая наука о счете на этой машине; особенно большой вклад в ее развитие внес французский ученый Герберт (950-1003), под конец жизни ставший папой римским Сильвестром II.

Но вычисления с развитием торговли, банковского дела, техники становились все более трудоемкими, и мысль поручить счет машине оставалось привлекательной. Многие умы занимались этой проблемой. Около 1632 году немецкий ученый Вильгельм Шиккард, профессор математики и восточных языков в Тюбингене, сконструировал первый в истории счетный механизм. Вскоре, в 1642 году, великий французский ученый Блез Паскаль (1623-1662) создал свою счетную машину, которая умела складывать и вычитать. Но другой ученый Готфнид Вильгельм Лейбниц (1646-1716) создал машину которая еще умела умножать и делить. Наконец, в первой половине XIX века англичанин Чарльз Бэббидж (1791-1871) разработал конструкцию машины, во многим причинам достойной называться первым компьютером.

Первый компьютер и был, и не был. Не был потому, что его автор Чарльз Бэббидж не смог его построить: в то время (он начал свою работу в 1834 году) подобная машина могла быть только механической. Но точность изготовления деталей была слишком высока по их меркам. Поэтому финансирование проекта прекратилась. Но все же первый компьютер был - не осуществленный, но продуманный до мелочей и тщательно вычерченный. Кроме чертежей, осталась еще и подробное словесное описание, составленной сотрудницей Бэббиджа Августой Адой Лавлейс, разработанная ею язык программирования и несколько первых в истории программ (перфокарты, машина Бэббиджа была способна выполнять программы). Его основные части были теми же, что и в каждом современном компьютере: устройства ввода данных (клавиатура); запоминающее устройство, способное хранить исходные данные; арифметическое устройство (-,+,·,:); устройство для вывода результата.

Дальнейшее развитие науки и техники позволили в 1940-х годах построить первые вычислительные машины. В феврале 1944 на одном из предприятий IBM в сотрудничестве с учеными Гарвардского университета по заказу ВМС США была создана машина "Марк-1". Это был монстр весом около 35 тонн. "Марк-1" был основан на использовании электромеханических реле и оперировал десятичными числами, закодированными на перфоленте. Машина могла манипулировать числами длиной до 23 разрядов. Для перемножения двух 23-разрядных чисел ей было необходимо четыре секунды. Но электромеханические реле работали недостаточно быстро. Поэтому уже в 1943 американцы начали разработку альтернативного варианта -- вычислительной машины на основе электронных ламп. В 1946 была построена первая электронная вычислительная машина ENIAC. Ее вес составлял 30 тонн, она требовала для размещения 170 квадратных метров площади. Вместо тысяч электромеханических деталей ENIAC содержал 18 тысяч электронных ламп. Считала машина в двоичной системе и производила пять тысяч операций сложения или триста операций умножения в секунду. Но лампы часто ломались и для их замены в 1947 американцы Джон Бардин, Уолтер Браттейн и Уильям Брэдфорд Шокли предложили использовать изобретенные ими стабильные переключающие полупроводниковые элементы -- транзисторы.

С активным внедрением транзисторов в 1950-х годах связано рождение второго поколения компьютеров. Один транзистор был способен заменить 40 электронных ламп. В результате быстродействие машин возросло в 10 раз при существенном уменьшении веса и размеров. В компьютерах стали применять запоминающие устройства из магнитных сердечников, способные хранить большой объем информации. В 1959 были изобретены интегральные микросхемы (чипы), в которых все электронные компоненты вместе с проводниками помещались внутри кремниевой пластинки. Применение чипов в компьютерах позволяет сократить пути прохождения тока при переключениях, и скорость вычислений повышается в десятки раз. Существенно уменьшаются и габариты машин. Появление чипа знаменовало собой рождение третьего поколения компьютеров.

В середине 1970-х годов начинают предприниматься попытки создания персонального компьютера -- вычислительной машины, предназначенной для частного пользователя. Во второй половине 1970-х годов появляются наиболее удачные образцы микрокомпьютеров американской фирмы Эппл (Apple), но широкое распространение персональные компьютеры получили с созданием в августе 1981 фирмой IBM модели микрокомпьютера IBM PC. Применение принципа открытой архитектуры, стандартизация основных компьютерных устройств и способов их соединения привели к массовому производству клонов IBM PC, широкому распространению микрокомпьютеров во всем мире.

В 1993 фирма Intel объявила о начале промышленных поставок процессора Pentium с тактовой частотой 66 и 60 МГц. Системы, построенные на базе Pentium, полностью совместимы с персональными компьютерами, использующими микропроцессоры ранних поколений i8088, i80286, i80386, i80486. Новая микросхема содержала около 3,1 млн. транзисторов и имела 32-разрядную адресную и 64-разрядную внешнюю шину данных. Архитектура Pentium содержит два арифметико-логических устройства, благодаря чему две команды могут быть выполнены за один такт синхронизации. Уже первый Pentium имел два раздельных кэша по восемь килобайт: один для команд, другой -- для данных. Pentium стал первым массовым процессором Intel с суперскалярной архитектурой и динамическим предсказанием переходов в исполняемых программах. При разработке Pentium была существенно повышена производительность модуля вычислений с плавающей запятой, добавлена аппаратная поддержка самотестирования, текущего контроля производительности и расширенной отладки. Благодаря встроенному в Pentium контроллеру прерываний многопроцессорных систем получили распространение двухпроцессорные серверы и рабочие станции на его основе. Первые Pentium выпускались до конца 1997. В дальнейшем фирма Интел производила модификации этого микропроцессора -- Pentium 2, Pentium 3, Pentium 4.

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

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

Чтобы получить внутреннее представление целого положительного числа N, хранящегося в k-разрядном машинном слове, необходимо:

1) перевести число N в двоичную систему счисления;

2) полученный результат дополнить слева незначащими нулями до k разрядов.

Например, получим внутреннее представление целого числа 1607 в 2-х байтовой ячейке. Переведем число в двоичную систему: 1607₁₀ = 11001000111₂. Внутреннее представление этого числа в ячейке будет следующим: 0000 0110 0100 0111.

Для записи внутреннего представления целого отрицательного числа (-N) необходимо:

1) получить внутреннее представление положительного числа N;

2) обратный код этого числа заменой 0 на 1 и 1 на 0;

3) полученному числу прибавить 1.

Например, получим внутреннее представление целого отрицательного числа -1607. Воспользуемся результатом предыдущего примера и запишем внутреннее представление положительного числа 1607: 0000 0110 0100 0111. Инвертированием получим обратный код: 1111 1001 1011 1000. Добавим единицу: 1111 1001 1011 1001 - это и есть внутреннее двоичное представление числа -1607.

Формат с плавающей точкой использует представление вещественного числа R в виде произведения мантиссы m на основание системы счисления n в некоторой целой степени p, которую называют порядком: R = m * n ^p.

Представление числа в форме с плавающей точкой неоднозначно. Например, справедливы следующие равенства: 12.345 = 0.0012345x10⁴ = 1234.5x10^-2 = 0.12345x10².

Чаще всего в ЭВМ используют нормализованное представление числа в форме с плавающей точкой. Мантисса в таком представлении должна удовлетворять условию: 0.1_p <= m < 1_p. Иначе говоря, мантисса меньше 1 и первая значащая цифра не ноль (p - основание системы счисления).

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

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

- прямой код - знак кодируется нулем для положительных и единицей для отрицательных. 510= 0 000101; -510= 1 000101

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

Данный код позволяет унифицировать сложение и вычитание с оговоркой, что если при суммировании чисел в обратном коде длина результата превысит стандартную длину цепочки, то происходит циклический перенос старшего разряда в младший, например: (+5) +(-3)=0000101+1111100=1 "0000001"= "0000010"=210.

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

Дополнительный код (или дополнение до двух) для положительных чисел совпадает с прямым, а для отрицательных чисел получается из обратного кода сложением с 1. Например: -5=1 111011.

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

Множество символов, используемых при записи текста, называется алфавитом. Количество символов в алфавите называется его мощностью.

Для представления текстовой информации в компьютере чаще всего используется алфавит мощностью 256 символов. Один символ из такого алфавита несет 8 бит информации, т. к. 28 = 256. Но 8 бит составляют один байт, следовательно, двоичный код каждого символа занимает 1 байт памяти ЭВМ.

Все символы такого алфавита пронумерованы от 0 до 255, а каждому номеру соответствует 8-разрядный двоичный код от 00000000 до 11111111. Этот код является порядковым номером символа в двоичной системе счисления.

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

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

Стандартными в этой таблице являются только первые 128 символов, т.е. символы с номерами от нуля (двоичный код 00000000) до 127 (01111111). Сюда входят буквы латинского алфавита, цифры, знаки препинания, скобки и некоторые другие символы. Остальные 128 кодов, начиная со 128 (двоичный код 10000000) и кончая 255 (11111111), используются для кодировки букв национальных алфавитов, символов псевдографики и научных символов.

Сейчас существует несколько различных кодовых таблиц для русских букв (КОИ-8, СР-1251, СР-866, Mac, ISO), причем тексты, созданные в одной кодировке, могут неправильно отображаться в другой. Решается такая проблема с помощью специальных программ перевода текста из одной кодировки в другую.

Альтернативная кодировка не подошла для ОС Windows. Пришлось передвинуть русские буквы в таблице на место псевдографики, и получили кодировку Windows 1251 (Win-1251).

В течение долгого времени понятия "байт" и "символ" были почти синонимами. Однако, в конце концов, стало ясно, что 256 различных символов - это не так много. Математикам требуется использовать в формулах специальные математические знаки, переводчикам необходимо создавать тексты, где могут встретиться символы из различных алфавитов, экономистам необходимы символы валют ($, Ј, Ґ). Для решения этой проблемы была разработана универсальная система кодирования текстовой информации - Unicode. В этой кодировке для каждого символа отводится не один, а два байта, т.е. шестнадцать бит. Таким образом, доступно 65536 (2¹⁶) различных кодов. Этого хватит на латинский алфавит, кириллицу, иврит, африканские и азиатские языки, различные специализированные символы: математические, экономические, технические и многое другое. Главный недостаток Unicode состоит в том, что все тексты в этой кодировке становятся в два раза длиннее. В настоящее время стандарты ASCII и Unicode мирно сосуществуют.

Почти все создаваемые, обрабатываемые или просматриваемые с помощью компьютера изображения можно разделить на две большие части - растровую и векторную графику. Для представления графической информации растровым способом используется так называемый точечный подход. На первом этапе вертикальными и горизонтальными линиями делят изображение. Чем больше при этом получилось элементов (пикселей), тем точнее будет передана информация об изображении. Как известно из физики, любой цвет может быть представлен в виде суммы различной яркости красного, зеленого и синего цветов. Поэтому надо закодировать информацию о яркости каждого из трех цветов для отображения каждого пикселя. В видеопамяти находится двоичная информация об изображении, выводимом на экран. Таким образом, растровые изображения представляют собой однослойную сетку точек, называемых пикселями (pixel, от англ. picture element), а код пикселя содержит информацию о его цвете.

Для черно-белого изображения (без полутонов) пиксель может принимать только два значения: белый и черный (светится - не светится), а для его кодирования достаточно одного бита памяти: 1 - белый, 0 - черный.

Пиксель на цветном дисплее может иметь различную окраску, поэтому одного бита на пиксель недостаточно. Для кодирования 4-цветного изображения требуются два бита на пиксель, поскольку два бита могут принимать 4 различных состояния. Может использоваться, например, такой вариант кодировки цветов: 00 - черный, 10 - зеленый, 01 - красный, 11 - коричневый.

На RGB-мониторах все разнообразие цветов получается сочетанием базовых цветов: красного (Red), зеленого (Green), синего (Blue), из которых можно получить 8 основных комбинаций:

R	G	B	цвет		R	G	B	цвет
0	0	0	черный		1	0	0	красный
0	0	1	синий		1	0	1	пурпурный
0	1	0	зеленый		1	1	0	желтый
0	1	1	голубой		1	1	1	белый

Разумеется, если иметь возможность управлять интенсивностью (яркостью) свечения базовых цветов, то количество различных вариантов их сочетаний, порождающих разнообразные оттенки, увеличивается. Количество различных цветов - К и количество битов для их кодировки - N связаны между собой простой формулой: 2^N = К.

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

Объекты векторного изображения, в отличие от растровой графики, могут изменять свои размеры без потери качества (при увеличении растрового изображения увеличивается зернистость).

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

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

Рисунок 4.1

На качество воспроизведения закодированного звука в основном влияют два параметра: частота дискретизации - количество измерений амплитуды за секунду в герцах и глубина кодирования звука - размер в битах, отводимый под запись значения амплитуды. Например, при записи на компакт-диски (CD) используются 16-разрядные значения, а частота дискретизации равна 44032 Гц. Эти параметры обеспечивают превосходное качество звучания речи и музыки. Для стереозвука отдельно записывают данные для левого и для правого канала.

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

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