ЛАБОРАТОРНЫЙ ПРАКТИКУМ по дисциплине информатика и икт

ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ НАЧАЛЬНОГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ ИРКУТСКОЙ ОБЛАСТИ ПРОФЕССИОНАЛЬНОЕ УЧИЛИЩЕ № 68 ЛАБОРАТОРНЫЙ ПРАКТИКУМ по дисциплине информатика и икт Улькан, 2013 Рассмотрена и одобрена  на заседании методической комиссии «____» _________2013 г. Протокол  №___ Автор: Оборина Наталья Сергеевна                                            Преподаватель  Лабораторный   практикум   составлен   на   основании:  примерной   программы   учебной дисциплины «Информатика и ИКТ»  для профессий начального профессионального образования. Согласно «Рекомендациям  по реализации образовательной программы среднего (полного) общего образования   в   образовательных   учреждениях   начального   профессионального   образования   в соответствии   с   федеральным   базисным   учебным   планом   и   примерными   учебными   планами   для образовательных учреждений Российской Федерации, реализующих программы общего образования» (письмо Департамента государственной политики и нормативно­правового регулирования в сфере образования Минобрнауки России от 29.05.2007 № 03­1180) СОДЕРЖАНИЕ Тема 1. Информация и информационные процессы                                                                                ...............................................................................4 Тема 2. Булева алгебра. Логические операции.......................................................................................7 Тема 3. Графы и деревья.........................................................................................................................10 Тема 4. Архитектура компьютера..........................................................................................................15 Тема 5. Системы счисления....................................................................................................................21 Тема 6. Организация машины. Хранение информации.........................................................................28 Тема 7. Алгоритмы. Основы разработки алгоритмов...........................................................................31 Тема 8. Структуры данных. Блок­схемы...............................................................................................35 Тема 9. Языки программирования..........................................................................................................39 Тема 10. Парадигмы программирования................................................................................................42 Тема 11. Основные элементы языка программирования Visual Basic for Application (VBA) ..........44 Тема 12. Операторы, выражения, операции...........................................................................................47 Тема 13. Операторы управления............................................................................................................49 Тема 14. Программирование циклов......................................................................................................50 Тема 15. Основные элементы операционных систем............................................................................54 Тема 16. Утилиты       .............................................................................................................................55 Тема 17. Текстовый редактор Word.......................................................................................................57 Тема 18 Табличный процессор Exсel. Работа с таблицами..................................................................64 Тема 19 Функции в Exсel.........................................................................................................................67 Тема 20. Работа со списками данных в Exсel........................................................................................69 Тема 21. СУБД Access. Создание таблиц в Access...............................................................................69 Тема 22. Разработка запросов в Access..................................................................................................73 Тема 23. Разработка форм и отчетов в Access......................................................................................74 Тема 24. Работа с пакетом PowerPoint...................................................................................................76 Тема 25. Локально­вычислительные сети..............................................................................................79 Тема 26. Глобальная сеть Internet...........................................................................................................81 Тема 27. Графические системы..............................................................................................................84 Тема 28. Работа с графическими приложениями..................................................................................86 Тема 29. Работа в среде графической программы................................................................................89 Тема 30. Основы защиты информации...................................................................................................92 ТЕМА: ИНФОРМАЦИЯ И ИНФОРМАЦИОННЫЕ ПРОЦЕССЫ Цель   занятия:  Изучить   структуру   информатики,   виды   и   свойства   информации, информационные процессы Задание: 1. Рассмотреть   информатику   как   единство   науки   и   технологии   и   изучить   структуру информатики. 2. Ознакомиться с видами и свойствами информации. Привести структуру информации 3. Измерить объем информации 4. Дать характеристику информационным процессам. Произвести операции с данными 5. Изучить носители данных 6. Составить отчет Теоретические сведения Процессы,   связанные   с   поиском,   хранением,   передачей,   обработкой   и   использованием информации, называются информационными процессами. Теперь остановимся на основных информационных процессах. 1. Поиск Поиск информации ­ это извлечение хранимой информации. Методы поиска информации: непосредственное наблюдение; общение со специалистами по интересующему вас вопросу; чтение соответствующей литературы; просмотр видео, телепрограмм; прослушивание радиопередач, аудиокассет; работа в библиотеках и архивах; запрос к информационным системам, базам и банкам компьютерных данных; другие методы.         Понять,  что  искать,   столкнувшись   с   той   или   иной   жизненной   ситуацией,   осуществить процесс поиска ­ вот умения, которые становятся решающими на пороге третьего тысячелетия. 2. Сбор и хранение Сбор   информации   не   является   самоцелью.   Чтобы   полученная   информация   могла использоваться, причем многократно, необходимо ее хранить. Хранение   информации   ­  это   способ   распространения   информации   в   пространстве   и времени. Способ хранения информации зависит от ее носителя  (книга­ библиотека, картина­ музей, фотография­ альбом). ЭВМ   предназначен   для  компактного   хранения  информации   с   возможностью  быстрого доступа к ней. 3. Передача В процессе передачи информации обязательно участвуют источник и приемник информации: первый   передает   информацию,   второй   ее   получает.   Между   ними   действует   канал   передачи информации ­ канал связи. Канал связи ­ совокупность технических устройств, обеспечивающих передачу сигнала от источника к получателю. Кодирующее   устройство   ­  устройство,   предназначенное   для   преобразования   исходного сообщения источника к виду, удобному для передачи. Декодирующее устройство ­ устройство для преобразования кодированного сообщения в исходное. Деятельность людей всегда связана с передачей информации. В   процессе   передачи   информация   может   теряться   и   искажаться:   искажение   звука   в телефоне, атмосферные помехи в радио, искажение или затемнение изображения в телевидении, ошибки   при   передачи   в   телеграфе.   Эти   помехи,   или,   как   их   называют   специалисты,   шумы, искажают информацию. Наука, разрабатывающая способы защиты информации ­ криптология. Рисунок 1.1 Процесс передачи информации Каналы   передачи   сообщений   характеризуются  пропускной   способностью  и помехозащищенностью. Каналы передачи данных делятся на симплексные (с передачей информации только в одну сторону   (телевидение))   и  дуплексные  (по   которым   возможно   передавать   информацию   в   оба направления   (телефон,   телеграф)).   По   каналу   могут   одновременно   передаваться   несколько сообщений. Каждое из этих сообщений выделяется (отделяется от других) с помощью специальных фильтров. Например, возможна фильтрация по частоте передаваемых сообщений, как это делается в радиоканалах. Пропускная   способность   канала   определяется   максимальным   количеством   символов, передаваемых ему в отсутствии помех. Эта характеристика зависит от физических свойств канала. Для повышения помехозащищенности канала используются специальные методы передачи сообщений, уменьшающие влияние шумов. Например, вводят лишние символы. Эти символы не несут действительного содержания, но используются для контроля правильности сообщения при получении. С   точки   зрения   теории   информации   все   то,   что   делает   литературный   язык   красочным, гибким,   богатым   оттенками,   многоплановым,   многозначным,­   избыточность.   Например,   как избыточно с таких позиций письмо Татьяны к Онегину. Сколько в нем информационных излишеств для краткого и всем понятного сообщения «Я Вас люблю!» 4. Обработка Обработка   информации   ­  преобразование   информации   из   одного   вида   в   другой, осуществляемое по строгим формальным правилам. Примеры обработки информации Примеры Входная информация Таблица умножения Множители Выходная информация Произведение Правило Правила арифметики Таблица 1.1 Определение   времени полета   рейса   "Москва­ Ялта" Отгадывание   слова   в игре "Поле чудес" Получение   секретных сведений Постановка   диагноза болезни Время   вылета   из Москвы   и   время прилета в Ялту Количество   букв   в слове и тема Шифровка резидента Жалобы   пациента   + результаты анализов от   Диагноз Время в пути Отгаданное слово Дешифрованный текст Математическая формула не   Формально определено Свое конкретном случае   в   каждом Знание + опыт врача Обработка информации по  принципу «черного ящика» ­  процесс, в котором пользователю важна и необходима лишь входная и выходная информация, но правила, по которым происходит преобразование, его не интересуют и не принимаются во внимание. «Черный ящик» ­ это система, в которой внешнему наблюдателю доступны лишь информация на входе и на выходе этой системы, а строение и внутренние процессы неизвестны.  информации по принципу «черного ящика» 5. Использование Рисунок 1.2 Обработка Информация используется при принятии решений.  Достоверность,   полнота,   объективность   полученной   информации   обеспечат   вам возможность принять правильное решение.  Ваша   способность   ясно   и   доступно   излагать   информацию   пригодится   в   общении   с окружающими.  Умение общаться, то есть обмениваться информацией, становится одним главных умений человека в современном мире. Компьютерная грамотность предполагает: знание назначения и пользовательских характеристик основных устройств компьютера;   Знание   основных   видов   программного   обеспечения   и   типов   пользовательских интерфейсов;  умение   производить   поиск,   хранение,   обработку   текстовой,   графической,   числовой информации с помощью соответствующего программного обеспечения. знание основ компьютерной грамотности; Информационная культура пользователя включает в себя:  понимание закономерностей информационных процессов;   технические навыки взаимодействия с компьютером;  эффективное применение компьютера как инструмента;  привычку своевременно обращаться к компьютеру при решении задач из любой области, основанную на владении компьютерными технологиями;  применение полученной информации в практической деятельности. 6. Защита Защитой информации называется предотвращение:  доступа  к   информации   лицам,   не   имеющим   соответствующего   разрешения (несанкционированный, нелегальный доступ);  непредумышленного   или   недозволенного  использования,   изменения  или  разрушения информации. Более подробно о защите информации мы остановимся далее. Под защитой информации, в более широком смысле, понимают комплекс организационных, правовых   и   технических   мер   по   предотвращению   угроз   информационной   безопасности   и устранению их последствий. Контрольные вопросы 1. Поиск,   какой   информации   вы   осуществляете   при   работе   со   словарями: орфографическим, толковым, энциклопедическим? 2. Назовите, какие методы поиска информации использовал Шерлок Холмс в своей работе? 3. Является ли поиск решения конкретной математической или физической задачи поиском информации? 4. Опишите процедуру вашего поиска в виде последовательности действий. 5. Что такое эвристический метод поиска информации? 6. Как люди могут узнать о жизни своих предков, живших много лет назад? 7. Как хранится информация на фотопленке? В каком виде представлена эта информация? 8. Приведите примеры передачи информации в природе и обществе. 9. Приведите   примеры   из   истории   и   литературы,   когда   при   передачи   информация преднамеренно искажалась. К чему это привело? 10. На уроке информатики. Вовочка (думает Очень хочется пить!») говорит Вера Ивановна, можно выйти?» Вера Ивановна (думает Наверное, он не знает урока и надеется, что за оставшиеся 5 минут до конца урока я не успею его спросить».) говорит Вовочка к доске!» Определите в данном примере источник информации, кодирование и декодирование, канал связи, приемник информации, помехи и причину их возникновения. ТЕМА: БУЛЕВА АЛГЕБРА. ЛОГИЧЕСКИЕ ОПЕРАЦИИ Цель   занятия:   рассмотреть   основы   дискретной   математики   (функции,   отношения, множества, основы логики, графы и деревья) Задания: 1. Изучить функции, отношения, множества 2. Ознакомиться   с   основами   логики   (булевой   алгеброй),   логикой   высказываний, логическими связками, таблицей истинности 3. Произвести логические операции. Рассмотреть формулы и их преобразование 4. Составить отчет Теоретические сведения Используется аппарат алгебры логики. Основные положения алгебры логики разработал в XIX в. английский математик Джордж Буль. Алгебру логики называют также булевой алгеброй. В булевой алгебре различают двоичные переменные и переключательные функции. Двоичные   переменные   могут   принимать   два   значения:   0   и   1.   Они   называются   также логическими или булевыми переменными и обозначаются символами х1,x2,х3,... Переключательные   функции  (ПФ)   зависят   от   двоичных   переменных.   Они,   как   и аргументы, могут принимать лишь два значения: 0 или 1. ПФ называют также логическими или булевыми функциями. Будем обозначать ПФ в виде f(х1,x2,х3,...). указывая в скобках аргументы, либо   в  виде  y1,y2,y3,...  .   ПФ   в   свою  очередь   могут   служить   аргументами   еще   более   сложных логических функций. Следовательно, можно построить ПФ любой заранее заданной сложности, пользуясь ограниченным числом логических связей. ПФ   принято   задавать   таблицами   истинности,   в   которых   для   всех   наборов   переменных указываются соответствующие им значения ПФ. Формирование значений ПФ в таблице истинности выполняется в соответствии с логикой работы устройства (сумматора, сдвигателя, преобразователя кодов и т. д.). Набор   переменных  —   это   совокупность   значений   двоичных   переменных,   каждая   из которых может быть равна 0 или 1. Если число аргументов (независимых переменных) ПФ равно n (т.е. х1,x2,х3,...xn), то существует 2 различных сочетаний этих переменных, т. е. наборов. Таблица 2.1 представляет собой таблицу истинности для некоторых ПФ f1 и f2, зависящих от двоичных переменных х1,x2,х3. Так как n = 3 (три переменных), таблица 2.1 содержит 8 строк, соответствующих 23 = 8 наборам переменных х1,x2,х3. Для каждого набора в таблица 2.1 записаны значения   ПФ   f1   и  f2,   равные   0   или   1.   По   таблице   истинности   записывается   аналитическое выражение для ПФ. Таблица 2.1 х1 0 0 0 0 1 1 1 1 х2 0 0 1 1 0 0 1 1 х3 0 1 0 1 0 1 0 1 f1 0 1 0 1 0 1 0 0 f2 1 0 1 0 0 0 1 1 Произвольная ПФ может быть выражена в форме функции от двоичных переменных (либо от других ПФ) с помощью ограниченного числа элементарных логических функций. Рассмотрим эти функции. Логическое отрицание  (функция НЕ). Логическим отрицанием переменной х называется такая   ПФ   f1(x),   которая   имеет   значение   1,   когда  x  =   0   и   значение   0,   когда   х=   1.   ПФ   НЕ обозначается в виде  f 1 x  и читается f1 есть (эквивалентно) не х». Таблица 2.2 представляет собой таблицу истинности логической функции НЕ. Таблица 2.2 х 0 1 f1 1 0 Логическое   умножение   (конъюнкция).  Конъюнкция   двух   (или   любого   другого   числа) переменных х1 и х2 принимает значение 1 только на наборе, в котором все переменные имеют значения 1. На остальных наборах эта функция имеет значение 0. Таблица 2.3 x1 0 0 1 1 x2 0 1 0 1 f2 0 0 0 1 Таблица 2.3 представляет собой таблицу истинности конъюнкции двух переменных х1 и x2. ПФ конъюнкция обозначается в виде  f  2 xx 21  и читается f2 есть (эквивалентно) х1 и x2». Для   обозначения   конъюнкции   можно   использовать   символы      или   &.   Конъюнкция называется   также   функцией   И,   так   как   она   имеет   значение   1,   только   если   первый   и   второй аргументы имеют значения 1. Логическое   сложение   (дизъюнкция).  Дизъюнкция   двух   (или   любого   другого   числа) переменных х1 и х2 имеет значение 0 только на наборе, в котором все переменные имеют значение 0. Если хотя бы одна из переменных равна 1, функция будет иметь значение 1. Таблица   2.4   есть   таблица   истинности   для   дизъюнкции   двух   переменных   х1   и   х2.   ПФ  и читается f3 есть (эквивалентно) х1 или x2». Кроме  x 1 x дизъюнкция записывается в виде  символа + , для дизъюнкции употребляется символ V. 3 2 f Так как функция дизъюнкции имеет значение 1, если первый или второй аргументы имеют значение 1, операция дизъюнкции называется также операцией ИЛИ. Таблица 2.4 x1 0 0 1 1 x2 0 1 0 1 f3 0 1 1 1 Элементарные   логические   функции   НЕ,   И,   ИЛИ   являются   основными   логическими функциями. Имеется еще несколько логических функций, производных от основных функций (т.е. выражающихся   через   функции   НЕ,   И,   ИЛИ),   которые   реализуются   соответствующими электронными   элементами   и   так   часто   встречаются   в   схемотехнике   ЭВМ,   что   им   были   даны собственные названия. Рассмотрим эти функции. Отрицание конъюнкции (операция И — НЕ). Эта функция образуется путем отрицания результата,   получаемого   при   выполнении   операции   И.   Таблица   2.5   есть   таблица   истинности операции И — НЕ для двух переменных. Из сравнения таблиц 2.3 и 2.5 видно, что ПФ И — НЕ является отрицанием (операцией НЕ) конъюнкции. ПФ И — НЕ записывается в виде  f  4 xx 21 Таблица 2.5 x1 0 0 1 1 x2 0 1 0 1 f4 1 1 1 0 Отрицание   дизъюнкции   (операция   ИЛИ   —   НЕ).  Эта   операция   образуется   путем отрицания   результата,   полученного   при   выполнении   операции   ИЛИ.   Таблица   2.6   представляет собой таблицу истинности операции ИЛИ — НЕ для двух переменных. Из сравнения таблиц 2.4 и 2.6 видно, что ПФ ИЛИ — НЕ является отрицанием (операцией НЕ) дизъюнкции. ПФ ИЛИ — НЕ записывается в виде  f 5  x 1 x 2 Таблица 2.6 x1 0 0 1 1 x2 0 1 0 1 f5 1 1 1 0 ИСКЛЮЧАЮЩЕЕ ИЛИ (операция НЕРАВНОЗНАЧНОСТЬ или СЛОЖЕНИЕ ПО МОДУЛЮ ДВА). Данная функция имеет значение 1 на тех наборах переменных, в которых число единиц   нечетно.   Для   двух   переменных   операция  НЕРАВНОЗНАЧНОСТЬ  иллюстрируется таблицей   истинности   (таблица   2.7).   Эта   операция   записывается   для   двух   переменных   в   виде f  x 1 6 x 2 / Операция   НЕРАВНОЗНАЧНОСТЬ   выражается   через   операции   НЕ,   И,   ИЛИ   в   виде f 6  xx 1 2  xx 21 . x1 0 0 1 1 x2 0 1 0 1 Таблица 2.7 f6 0 1 1 0 Операция   ИСКЛЮЧАЮЩЕЕ   ИЛИ   —   НЕ   (РАВНОЗНАЧНОСТЬ).   Функция РАВНОЗНАЧНОСТЬ представляет собой отрицание операции ИСКЛЮЧАЮЩЕЕ ИЛИ. Данная операция имеет значение 1 на тех наборах переменных, которые содержат четное число   единиц.   Для   двух   переменных   операция   ИСКЛЮЧАЮЩЕЕ   ИЛИ   —   НЕ   представлена таблицей   истинности   (таблица   2.8).   Эта   операция   записывается   для   двух   переменных   в   виде f  x x 1 7 2 x1 0 0 1 1 x2 0 1 0 1 Таблица 2.8 f6 1 0 0 1 Операция ИСКЛЮЧАЮЩЕЕ ИЛИ — НЕ выражается через операции НЕ, И, ИЛИ в виде f 7  xx 1  xx 21 . 2 Задания для самостоятельного выполнения: Даны двоичных числа А и В (данные в таблице). Выполнить операции: - - - - - - - отрицание логическое сложение отрицание ИЛИ логическое умножение отрицание И исключающее ИЛИ отрицание исключающего ИЛИ Вариант 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. А 1111 1011 1010 1010 1101 0110 0001 1001 1010 1011 1001 1011 1001 0001 1101 ТЕМА: ГРАФЫ И ДЕРЕВЬЯ Цель занятия: изучить графы и деревья Задание: 1. Рассмотреть графы и деревья В 0101 0110 1011 1101 1011 0110 1001 0010 1100 1101 0111 0011 1111 1010 1110 2. Изучить неориентированные и ориентированные графы, стратегии обхода графов 3. Привести примеры графов и деревьев 4. Оформить отчет Теоретические сведения Граф  ­ это двойка  , где  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 Вес ребра (дуги) Стоимость получения визы Длина пересекающихся частей Существует   довольно   большое   число   разнообразных   способов   представления  графов. Однако мы изложим здесь только самые полезные с точки зрения программирования. Матрица   смежности  Sm  ­   это   квадратная   матрица   размером  NЧN  (N  ­   количество вершин в графе), заполненная единицами и нулями по следующему правилу: Если в графе имеется ребро e, соединяющее вершины u и v, то Sm[u,v] = 1, в противном случае Sm[u,v] = 0. Заметим, что данное определение подходит как ориентированным, так и неориентированным графам: матрица смежности для неориентированного графа будет симметричной относительно своей главной диагонали, а для орграфа ­ несимметричной. Задать взвешенный  граф  при помощи  матрицы смежности  тоже возможно. Необходимо лишь внести небольшое изменение в определение: Если в графе имеется ребро e, соединяющее вершины u и v, то Sm[u,v] = ves(e), в противном случае Sm[u,v] = 0. Небольшое затруднение возникнет в том случае, если в графе разрешаются ребра с весом 0. Тогда придется хранить два массива: один с нулями и единицами, которые служат показателем наличия ребер, а второй ­ с весами этих ребер. В качестве примера приведем  матрицы смежности  для трех  графов, изображенных на рисунке 3.5, рисунке 3.6 и рисунке 3.7. Примеры матриц смежности Таблица 3.4 Граф Эйлера (рисунок 3.5) Орграф (рисунок 3.6) Взвешенный граф (рисунок 3.7) a 0 1 1 0 0 b 1 0 1 1 0 c 1 1 0 1 1 d 0 1 1 0 1 f 0 0 1 1 0 1 0 0 1 0 0 2 1 0 1 0 0 3 0 0 0 1 0 4 1 0 0 0 0 5 0 0 1 0 0 1 2 3 4 5 a b c d f a 0 1 10 0 b 1 0 2 0 c 10 2 0 3 d 0 10 3 0 a b c d Удобство  матрицы   смежности  состоит   в   наглядности   и   прозрачности   алгоритмов, основанных на ее использовании. А неудобство ­ в несколько завышенном требовании к памяти: если  граф  далек от полного, то в массиве, хранящем  матрицу смежности, оказывается много «пустых мест» (нулей). Кроме того, для «общения» с пользователем этот способ представления графов не слишком удобен: его лучше применять только для внутреннего представления данных. Список ребер ­ этот способ задания графов наиболее удобен для внешнего представления входных данных. Пусть каждая строка входного файла содержит информацию об одном  ребре (дуге): <номер_начальной_вершины> <номер_конечной_вершины> [<вес_ребра>] В качестве примера приведем списки ребер (дуг), задающие те же три графа с рисунка 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. Построить ориентированный граф и вычислить длину пути от одной из вершин ко всем остальным. ТЕМА: АРХИТЕКТУРА КОМПЬЮТЕРА Цель   занятия:   изучить   представление   данных   в   компьютере,   логические   элементы компьютера. Задание: 1. Ознакомиться с историей архитектуры компьютеров 2. Рассмотреть логические элементы компьютера: вентили, триггеры, счетчики, регистры 3. Изучить представление данных в компьютере 4. Освоить   представления   числовых   и   нечисловых   данных,   знаковые   представления   и представления в дополнительном коде 5. Привести примеры представления данных 6. Составить отчет Теоретические сведения Архитектурой   компьютера  называется   его   описание   на   некотором   общем   уровне, включающее   описание   пользовательских   возможностей   программирования,   системы   команд, системы   адресации,   организации   памяти   и   т.д.   Архитектура   определяет   принципы   действия, информационные   связи   и   взаимное   соединение   основных   логических   узлов   компьютера: процессора,   оперативного  ЗУ,   внешних   ЗУ   и   периферийных   устройств.   Общность   архитектуры разных компьютеров обеспечивает их совместимость с точки зрения пользователя.