МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ПО ВЫПОЛНЕНИЮ ПРАКТИЧЕСКИХ РАБОТ ПО ДИСЦИПЛИНЕ ИНФОРМАТИКА ДЛЯ ОБУЧАЮЩИХСЯ 2017 год

ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ПРОФЕССИОНАЛЬНОЕ  ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ИРКУТСКОЙ ОБЛАСТИ «УЛЬКАНСКИЙ МЕЖОТРАСЛЕВОЙ ТЕХНИКУМ» Утверждено на заседании МК протокол № ______ «__»_____________201___ г.  Руководитель  МК Общеобразовательного цикла ______________________ Л.Г. Кузнецова МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ПО ВЫПОЛНЕНИЮ ПРАКТИЧЕСКИХ РАБОТ   ПО ДИСЦИПЛИНЕ ИНФОРМАТИКА  ДЛЯ ОБУЧАЮЩИХСЯ  1 Улькан, 2016 2 СОДЕРЖАНИЕ Тема 1. Информация и информационные процессы                                                                                ...............................................................................3 Тема 2. Булева алгебра. Логические операции.......................................................................................6 Тема 3. Графы и деревья.........................................................................................................................10 Тема 4. Архитектура компьютера..........................................................................................................16 Тема 5. Системы счисления....................................................................................................................22 Тема 6. Организация машины. Хранение информации.........................................................................29 Тема 7. Алгоритмы. Основы разработки алгоритмов...........................................................................33 Тема 8. Структуры данных. Блок­схемы...............................................................................................38 Тема 9. Языки программирования..........................................................................................................42 Тема 10. Парадигмы программирования................................................................................................45 Тема 11. Основные элементы языка программирования Visual Basic for Application (VBA) ..........48 Тема 12. Операторы, выражения, операции...........................................................................................49 Тема 13. Операторы управления............................................................................................................51 Тема 14. Программирование циклов......................................................................................................54 Тема 15. Основные элементы операционных систем............................................................................56 Тема 16. Утилиты .............................................................................................................................54 Тема 17. Текстовый редактор Word.......................................................................................................56 Тема 18 Табличный процессор Exсel. Работа с таблицами..................................................................63 Тема 19 Функции в Exсel.........................................................................................................................66 Тема 20. Работа со списками данных в Exсel........................................................................................68 Тема 21. СУБД Access. Создание таблиц в Access...............................................................................67 Тема 22. Разработка запросов в Access..................................................................................................72 Тема 23. Разработка форм и отчетов в Access......................................................................................73 Тема 24. Работа с пакетом PowerPoint...................................................................................................75 Тема 25. Локально­вычислительные сети..............................................................................................78 Тема 26. Глобальная сеть Internet...........................................................................................................80 Тема 27. Графические системы..............................................................................................................83 Тема 28. Работа с графическими приложениями..................................................................................85 Тема 29. Работа в среде графической программы................................................................................88 Тема 30. Основы защиты информации...................................................................................................91 2 ТЕМА: ИНФОРМАЦИЯ И ИНФОРМАЦИОННЫЕ ПРОЦЕССЫ Цель   занятия:  Изучить   структуру   информатики,   виды   и   свойства   информации, информационные процессы Задание: 1. Рассмотреть   информатику   как   единство   науки   и   технологии   и   изучить   структуру информатики. 2. Ознакомиться с видами и свойствами информации. Привести структуру информации 3. Измерить объем информации 4. Дать характеристику информационным процессам. Произвести операции с данными 5. Изучить носители данных 6. Составить отчет Теоретические сведения Процессы,   связанные   с   поиском,   хранением,   передачей,   обработкой   и   использованием информации, называются информационными процессами. Теперь остановимся на основных информационных процессах. 1. Поиск Поиск информации ­ это извлечение хранимой информации. Методы поиска информации:         Понять,  что  искать,   столкнувшись   с   той   или   иной   жизненной   ситуацией,   осуществить непосредственное наблюдение; общение со специалистами по интересующему вас вопросу; чтение соответствующей литературы; просмотр видео, телепрограмм; прослушивание радиопередач, аудиокассет; работа в библиотеках и архивах; запрос к информационным системам, базам и банкам компьютерных данных; другие методы. процесс поиска ­ вот умения, которые становятся решающими на пороге третьего тысячелетия. 2. Сбор и хранение Сбор   информации   не   является   самоцелью.   Чтобы   полученная   информация   могла использоваться, причем многократно, необходимо ее хранить. Хранение   информации   ­  это   способ   распространения   информации   в   пространстве   и времени. Способ хранения информации зависит от ее носителя  (книга­ библиотека, картина­ музей, фотография­ альбом). ЭВМ   предназначен   для  компактного   хранения  информации   с   возможностью  быстрого доступа к ней. 3. Передача 2 В процессе передачи информации обязательно участвуют источник и приемник информации: первый   передает   информацию,   второй   ее   получает.   Между   ними   действует   канал   передачи информации ­ канал связи. Канал связи ­ совокупность технических устройств, обеспечивающих передачу сигнала от источника к получателю. Кодирующее   устройство   ­  устройство,   предназначенное   для   преобразования   исходного сообщения источника к виду, удобному для передачи. Декодирующее устройство ­ устройство для преобразования кодированного сообщения в исходное. Деятельность людей всегда связана с передачей информации. В   процессе   передачи   информация   может   теряться   и   искажаться:   искажение   звука   в телефоне, атмосферные помехи в радио, искажение или затемнение изображения в телевидении, ошибки   при   передачи   в   телеграфе.   Эти   помехи,   или,   как   их   называют   специалисты,   шумы, искажают информацию. Наука, разрабатывающая способы защиты информации ­ криптология. Рисунок 1.1 Процесс передачи информации Каналы   передачи   сообщений   характеризуются  пропускной   способностью  и помехозащищенностью. Каналы передачи данных делятся на симплексные (с передачей информации только в одну сторону   (телевидение))   и  дуплексные  (по   которым   возможно   передавать   информацию   в   оба направления   (телефон,   телеграф)).   По   каналу   могут   одновременно   передаваться   несколько сообщений. Каждое из этих сообщений выделяется (отделяется от других) с помощью специальных фильтров. Например, возможна фильтрация по частоте передаваемых сообщений, как это делается в радиоканалах. Пропускная   способность   канала   определяется   максимальным   количеством   символов, передаваемых ему в отсутствии помех. Эта характеристика зависит от физических свойств канала. Для повышения помехозащищенности канала используются специальные методы передачи сообщений, уменьшающие влияние шумов. Например, вводят лишние символы. Эти символы не несут действительного содержания, но используются для контроля правильности сообщения при получении. С   точки   зрения   теории   информации   все   то,   что   делает   литературный   язык   красочным, гибким,   богатым   оттенками,   многоплановым,   многозначным,­   избыточность.   Например,   как избыточно с таких позиций письмо Татьяны к Онегину. Сколько в нем информационных излишеств для краткого и всем понятного сообщения «Я Вас люблю!» 2 4. Обработка Обработка   информации   ­  преобразование   информации   из   одного   вида   в   другой, осуществляемое по строгим формальным правилам. Примеры обработки информации Входная Примеры Таблица умножения Определение   времени полета рейса "Москва­ Ялта" Отгадывание   слова   в игре "Поле чудес" Получение   секретных сведений Постановка   диагноза болезни информация Множители Время   вылета   из Москвы   и   время прилета в Ялту Количество   букв   в слове и тема Шифровка резидента Жалобы   пациента   + результаты анализов от   Выходная информация Произведение Время в пути Отгаданное слово Дешифрованный текст Таблица 1.1 Правило Правила арифметики Математическая формула   не Формально определено Свое   в   каждом конкретном случае Диагноз Знание + опыт врача Обработка информации по  принципу «черного ящика» ­  процесс, в котором пользователю важна и необходима лишь входная и выходная информация, но правила, по которым происходит преобразование, его не интересуют и не принимаются во внимание. «Черный ящик» ­ это система, в которой внешнему наблюдателю доступны лишь информация на входе и на выходе этой системы, а строение и внутренние процессы неизвестны.   информации по принципу «черного ящика» 5. Использование Рисунок 1.2 Обработка Информация используется при принятии решений.  Достоверность,   полнота,   объективность   полученной   информации   обеспечат   вам возможность принять правильное решение.  Ваша   способность   ясно   и   доступно   излагать   информацию   пригодится   в   общении   с окружающими.  Умение общаться, то есть обмениваться информацией, становится одним главных умений человека в современном мире. Компьютерная грамотность предполагает:  знание назначения и пользовательских характеристик основных устройств компьютера;  Знание   основных   видов   программного   обеспечения   и   типов   пользовательских интерфейсов;  умение   производить   поиск,   хранение,   обработку   текстовой,   графической,   числовой информации с помощью соответствующего программного обеспечения. Информационная культура пользователя включает в себя: 2  понимание закономерностей информационных процессов;  знание основ компьютерной грамотности;  технические навыки взаимодействия с компьютером;  эффективное применение компьютера как инструмента;  привычку своевременно обращаться к компьютеру при решении задач из любой области, основанную на владении компьютерными технологиями;  применение полученной информации в практической деятельности. 6. Защита Защитой информации называется предотвращение:  доступа  к   информации   лицам,   не   имеющим   соответствующего   разрешения (несанкционированный, нелегальный доступ);  непредумышленного   или   недозволенного  использования,   изменения  или  разрушения информации. Более подробно о защите информации мы остановимся далее. Под защитой информации, в более широком смысле, понимают комплекс организационных, правовых   и   технических   мер   по   предотвращению   угроз   информационной   безопасности   и устранению их последствий. Контрольные вопросы 1. Поиск,   какой   информации   вы   осуществляете   при   работе   со   словарями: орфографическим, толковым, энциклопедическим? 2. Назовите, какие методы поиска информации использовал Шерлок Холмс в своей работе? 3. Является ли поиск решения конкретной математической или физической задачи поиском информации? 4. Опишите процедуру вашего поиска в виде последовательности действий. 5. Что такое эвристический метод поиска информации? 6. Как люди могут узнать о жизни своих предков, живших много лет назад? 7. Как хранится информация на фотопленке? В каком виде представлена эта информация? 8. Приведите примеры передачи информации в природе и обществе. 9. Приведите   примеры   из   истории   и   литературы,   когда   при   передачи   информация преднамеренно искажалась. К чему это привело? 10. На уроке информатики. Вовочка (думает Очень хочется пить!») говорит Вера Ивановна, можно выйти?» Вера Ивановна (думает Наверное, он не знает урока и надеется, что за оставшиеся 5 минут до конца урока я не успею его спросить».) говорит Вовочка к доске!» Определите в данном примере источник информации, кодирование и декодирование, канал связи, приемник информации, помехи и причину их возникновения. ТЕМА: БУЛЕВА АЛГЕБРА. ЛОГИЧЕСКИЕ ОПЕРАЦИИ Цель   занятия:   рассмотреть   основы   дискретной   математики   (функции,   отношения, 2 множества, основы логики, графы и деревья) Задания: 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 2 х2 0 0 1 1 0 0 1 х3 0 1 0 1 0 1 0 f1 0 1 0 1 0 1 0 f2 1 0 1 0 0 0 1 1 1 1 0 1 Произвольная ПФ может быть выражена в форме функции от двоичных переменных (либо от других ПФ) с помощью ограниченного числа элементарных логических функций. Рассмотрим эти функции. Логическое отрицание  (функция НЕ). Логическим отрицанием переменной х называется такая ПФ f1(x), которая имеет значение 1, когда x = 0 и значение 0, когда х= 1. ПФ НЕ обозначается в виде  x  и читается f1 есть (эквивалентно) не х». f 1 Таблица 2.2 представляет собой таблицу истинности логической функции НЕ. х 0 1 Таблица 2.2 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. 2 3 f Так как функция дизъюнкции имеет значение 1, если первый или второй аргументы имеют значение 1, операция дизъюнкции называется также операцией ИЛИ. x1 0 2 x2 0 f3 0 Таблица 2.4 0 1 1 1 0 1 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 . 2 x1 0 0 1 1 x2 0 1 0 1 Таблица 2.7 f6 0 1 1 0 Операция   ИСКЛЮЧАЮЩЕЕ   ИЛИ   —   НЕ   (РАВНОЗНАЧНОСТЬ).   Функция РАВНОЗНАЧНОСТЬ представляет собой отрицание операции ИСКЛЮЧАЮЩЕЕ ИЛИ. Данная операция имеет значение 1 на тех наборах переменных, которые содержат четное число   единиц.   Для   двух   переменных   операция   ИСКЛЮЧАЮЩЕЕ   ИЛИ   —   НЕ   представлена таблицей   истинности   (таблица   2.8).   Эта   операция   записывается   для   двух   переменных   в   виде f  x 1 x 2 7 x1 0 0 1 1 x2 0 1 0 1 Таблица 2.8 f6 1 0 0 1 Операция ИСКЛЮЧАЮЩЕЕ ИЛИ — НЕ выражается через операции НЕ, И, ИЛИ в виде xx 1  xx 21 . 2 Задания для самостоятельного выполнения: Даны двоичных числа А и В (данные в таблице). Выполнить операции: - - - - - - - отрицание логическое сложение отрицание ИЛИ логическое умножение отрицание И исключающее ИЛИ отрицание исключающего ИЛИ Вариант 1. 2. 3. 4. 5. 6. 7. 8. 9. А 1111 1011 1010 1010 1101 0110 0001 1001 1010 В 0101 0110 1011 1101 1011 0110 1001 0010 1100 f 7  2 10. 11. 12. 13. 14. 15. 1011 1001 1011 1001 0001 1101 1101 0111 0011 1111 1010 1110 ТЕМА: ГРАФЫ И ДЕРЕВЬЯ Цель занятия: изучить графы и деревья Задание: 1. Рассмотреть графы и деревья 2. Изучить неориентированные и ориентированные графы, стратегии обхода графов 3. Привести примеры графов и деревьев 4. Оформить отчет Теоретические сведения Граф  ­ это двойка  , где  V  ­ непустое множество  вершин, а  Е  ­ множество  ребер, соединяющих эти вершины попарно. Две вершины, связанные между собой ребром, равноправны, и именно   поэтому   такие  графы  называются  неориентированными:   нет   никакой   разницы   между 2 «началом» и «концом» ребра. Примеры неориентированных графов Таблица 3.1 Граф Семья Город Домино Вершины Люди Перекрестки Костяшки Ребра Родственные связи Улицы Возможность Говоря   простым   языком,  граф  ­   это   множество   точек   (для   удобства   изображения   ­   на плоскости) и попарно соединяющих их линий (не обязательно прямых). В графе важен только факт наличия связи между двумя вершинами. От способа изображения этой связи структура графа не зависит. Например, три графа на рисунке 3.1 совпадают, а два графа на рисунке 3.2 ­ различны. Из   приведенного   выше   определения   вытекает,   что   в  графах  не   бывает  петель  ­   ребер, соединяющих некоторую вершину саму с собой (рисунок 3.3). Кроме того, в классическом графе не бывает двух различных ребер, соединяющих одну и ту же пару вершин. Рисунок 3.1 Три способа изображения одного графа Ребро  е  и  вершина  v  называются  инцидентными  друг другу, если  вершина  v является одним из концов ребра е. Рисунок 3.2 Пример двух разных графов Рисунок 3.3 Псевдограф Любому  ребру  инцидентно  ровно  две  вершины,  а  вот вершине  может  быть  инцидентно произвольное количество ребер, это количество и определяет  степень вершины. Изолированная вершина вообще не имеет инцидентных ей ребер (ее степень равна 0). Две вершины  называются  смежными, если они являются разными концами одного ребра (иными   словами,   эти   вершины   инцидентны   одному   ребру).   Аналогично,   два   ребра   называются смежными, если они инцидентны одной вершине. 2 Путь  в   графе   ­   это   последовательность   вершин   (без   повторений),   в   которой   любые   две соседние вершины смежны. Например, в графе, изображенном на рисунке 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 Граф Эйлера Гамильтонов граф ­ это граф, в котором существует  цикл (без повторений), содержащий 2 все вершины графа (рисунок 3.5; искомый цикл: abdfca). Ориентированный   граф  (орграф)  ­   это  граф,   все  ребра  которого   имеют   направление. Такие   направленные  ребра  называются  дугами.   На   рисунках  дуги  изображаются   стрелочками (рисунок 3.6). Рисунок 3.6 Орграф В отличие от ребер, дуги соединяют две неравноправные вершины: одна из них называется началом дуги (дуга из нее исходит), вторая ­ концом дуги (дуга в нее входит). Можно сказать, что любое ребро ­ это пара дуг, направленных навстречу друг другу. Если в графе присутствуют и ребра, и дуги, то его называют смешанным. Все   основные   понятия,   определенные   для   неориентированных  графов  (инцидентность, смежность,  достижимость,  длина   пути  и   т.п.),   остаются   в   силе   и   для  орграфов  ­   нужно   лишь заменить   слово   «ребро»  словом   «дуга».   А   немногие   исключения   связаны   с   различиями   между ребрами и дугами. Степень   вершины  в  орграфе  ­   это   не   одно   число,   а   пара   чисел:   первое   характеризует количество исходящих из вершины дуг, а второе ­ количество входящих дуг. Путь в орграфе ­ это последовательность  вершин  (без повторений), в которой любые две соседние вершины смежны, причем каждая вершина является одновременно концом одной дуги и началом следующей дуги. Например, в орграфе на рисунке 3.6 нет пути, ведущего из вершины 2 в вершину 5. «Двигаться» по орграфу можно только в направлениях, заданных стрелками. Таблица 3.2 Примеры ориентированных графов Граф Чайнвор д Стройка Вершины Слова Работы Дуги Совпадение   последней   и   первой   букв   (возможность   связать   два   слова   в цепочку) Необходимое предшествование (например, стены нужно построить раньше, чем крышу, т. п.) Взвешенный  (другое   название:  размеченный)  граф  (или  орграф)   ­   это  граф  (орграф), некоторым элементам которого (вершинам, ребрам или дугам) сопоставлены числа. Наиболее часто встречаются графы с помеченными ребрами. Числа­пометки носят различные названия: вес, длина, стоимость. Замечание: Обычный (не взвешенный)  граф  можно интерпретировать как взвешенный, все ребра которого имеют одинаковый вес 1. Длина   пути  во   взвешенном  (связном)  графе  ­   это   сумма   длин   (весов)   тех   ребер,   из которых состоит  путь.  Расстояние  между  вершинами  ­ это, как и прежде,  длина  кратчайшего пути. Например,  расстояние  от  вершины  a  до  вершины  d  во взвешенном  графе, изображенном на 2 рисунке 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.5) Орграф (рисунок 3.6) a 0 1 b 1 0 c 1 1 d 0 1 f 0 0 1 0 0 2 1 0 3 0 0 4 1 0 5 0 0 1 2 a b a b 2 Таблица 3.4 Взвешенный граф (рисунок 3.7) a 0 1 c 10 2 b 1 0 d 0 10 c d f 1 0 0 1 1 0 0 1 1 1 0 1 1 1 0 3 4 5 1 0 0 1 0 0 0 1 0 0 0 0 1 0 0 c d 10 0 2 0 0 3 3 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. Собственно,   этот   способ   представления  графов  является   всего   лишь   внутренней 2 реализацией списка смежности: в одном линейном списке содержатся номера «начальных вершин», а в остальных ­ номера смежных вершин или указатели на эти вершины. Таблица 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. дуг; дуге. Традиционно в математике и в родственных ей науках (в том числе и в теоретическом программировании) деревья «растут» вниз головой: это делается просто для удобства наращивания листьев  в случае необходимости. Таким образом, на рисунках  корень  дерева  оказывается самой 2 верхней вершиной, а листья ­ самыми нижними. Предок  вершины  v  ­   это  вершина,   из   которой   исходит  дуга,   заходящая   в  вершину  v. Потомок  вершины  v  ­ это  вершина, в которую заходит  дуга, исходящая из  вершины  v. В этих терминах можно дать другие определения понятиям корень и лист: у корня нет предков, у листа нет потомков. Бинарное дерево  ­ это  корневое дерево, каждая  вершина  которого имеет не более двух потомков.   В   таком   случае   иногда   говорят   о  левом  потомке  и  правом  потомке  для   текущей вершины. Высота корневого дерева ­ это максимальное количество дуг, отделяющих листья от корня. Если дерево не взвешенное, то его высота ­ это просто расстояние от корня до самого удаленного листа. Поскольку   любое  дерево  является  графом,   то   его   можно   задавать   любым   из   способов, перечисленных выше. Задания для самостоятельного выполнения: 1. Построить неориентированный граф и вычислить длину пути от одной из вершин ко всем остальным. 2. Построить ориентированный граф и вычислить длину пути от одной из вершин ко всем остальным. 2 ТЕМА: АРХИТЕКТУРА КОМПЬЮТЕРА Цель   занятия:   изучить   представление   данных   в   компьютере,   логические   элементы компьютера. Задание: 1. Ознакомиться с историей архитектуры компьютеров 2. Рассмотреть логические элементы компьютера: вентили, триггеры, счетчики, регистры 3. Изучить представление данных в компьютере 4. Освоить   представления   числовых   и   нечисловых   данных,   знаковые   представления   и представления в дополнительном коде 5. Привести примеры представления данных 6. Составить отчет Теоретические сведения Архитектурой   компьютера  называется   его   описание   на   некотором   общем   уровне, включающее   описание   пользовательских   возможностей   программирования,   системы   команд, системы   адресации,   организации   памяти   и   т.д.   Архитектура   определяет   принципы   действия, информационные   связи   и   взаимное   соединение   основных   логических   узлов   компьютера: процессора,   оперативного  ЗУ,   внешних   ЗУ   и   периферийных   устройств.   Общность   архитектуры разных компьютеров обеспечивает их совместимость с точки зрения пользователя. Структура   компьютера  —   это   совокупность   его   функциональных   элементов   и   связей между ними. Элементами могут быть самые различные устройства — от основных логических узлов компьютера до простейших схем. Структура компьютера графически представляется в виде структурных   схем,   с   помощью   которых   можно   дать   описание   компьютера   на   любом   уровне детализации. История   вычислительной   техники   началась   едва   ли   не   раньше,   чем   окончательно сформировалась понятие числа. Неспроста в некоторых языках слово  "цифра"  происходит от слова  "палец"  ­   поначалу   счет   был   неотделим   от   загибания   пальцев.   Пальцы   стали   первой вычислительной   техникой.   Великий   переворот   в   вычислительной   технике   произошел   с изобретением  абака.   Даже   если   вы   не   слышали   этого   слова,   вы   встречали,   и   не   раз,   русскую разновидность этого прибора ­ счеты. Абак долгое время играл особую роль в арифметике (как в геометрии   ­   циркуль   и   линейка):   задача   считалось   решенной,   только   если   было   указано,   как необходимые вычисления выполнить на абаке. Существовала целая наука о счете на этой машине; особенно большой вклад в ее развитие внес французский ученый  Герберт  (950­1003), под конец жизни ставший папой римским Сильвестром II. Но вычисления  с развитием торговли, банковского дела, техники становились все более трудоемкими, и мысль поручить счет машине оставалось привлекательной. Многие умы занимались этой проблемой. Около 1632 году немецкий ученый Вильгельм Шиккард, профессор математики и восточных языков в Тюбингене, сконструировал первый в истории счетный механизм. Вскоре, в 2 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 были изобретены интегральные микросхемы (чипы), в которых все электронные компоненты вместе с проводниками помещались внутри кремниевой пластинки. Применение чипов в компьютерах позволяет сократить пути прохождения тока при 2 переключениях, и скорость вычислений повышается в десятки раз. Существенно уменьшаются и габариты машин. Появление чипа знаменовало собой рождение третьего поколения компьютеров. В   середине   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­разрядной ячейке может храниться 2k различных значений целых чисел. Чтобы получить внутреннее представление целого положительного числа N, хранящегося в k­разрядном машинном слове, необходимо: 1) перевести число N в двоичную систему счисления; 2) полученный результат дополнить слева незначащими нулями до k разрядов. Например, получим внутреннее представление целого числа 1607 в 2­х байтовой ячейке. Переведем число в двоичную систему: 160710 = 110010001112. Внутреннее представление этого числа в ячейке будет следующим: 0000 0110 0100 0111. Для записи внутреннего представления целого отрицательного числа (­N) необходимо: 2