Тема: 6. Моделирование на графах

 

Тема 6. Моделирование на графах

 

Давайте рассмотрим, пожалуй, самую известную головоломку, придуманную аж в XVIII веке, и захватившую умы человечества на многие годы. Называется она задача о семи Кёнигсбергских мостах. В Кёнигсберге начиная с XIV было построено 7 мостов: Медовый мост, Лавочный мост, Зелёный мост, Рабочий мост, Кузнечный мост, Деревянный мост и Высокий мост, соединяющий остров и полуострова в единый город. Тогда и возникла головоломка: «Как пройти по всем мостам, не проходя ни по одному дважды?»

Десятилетиям жители города пытались решить эту задачу как практически (гуляя по городу), так и теоретически.

И только Леонард Эйлер, введя новое понятие — ГРАФ, смог решить ее раз и навсегда.

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

Графы делятся на:

— Неориентированные и ориентированные (когда движение по ребру возможно только в одну сторону).

— Взвешенными (когда у вершины или у ребра есть вес, отличающий его от другого) и невзвешенный.

— И другие более сложные графы (мультиграф, псевдограф, изоморфный граф и другие).

Эйлер установил, что:

1. Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа должно быть чётно или не может существовать граф, который имел бы нечётное число нечётных вершин.

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

3. Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.

ВЫВОД: пройти только один раз по каждому мосту невозможно.

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

Очень часто для решения задач требуется найти кратчайший путь между двумя вершинами.

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

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

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

Для примера возьмем следующий взвешенный ориентированный граф и попытаемся найти кратчайший путь от вершины A до F. Пошагово переберём все вершины графа, вычеркивая их, которые будут являются известным минимальным расстоянием от вершины «начала» до конкретной вершины.

Первым шагом: присвоим вершине А метку равную 0, потому как эта вершина — начало. Остальным вершинам присвоим метки равные бесконечности.

Вторым шагом: выберем не вычеркнутую вершину, вес которой является минимальным («источник»). Сейчас это вершина А. Вычисляем сумму веса вершины источника и веса ребра

То есть для:

B=0+2=2

C=0+5

D=0+7

F=0+10.

Если она окажется меньше веса вершины приемника, то изменим вес этой вершины.

Третьим шагом: вычеркнем вершину-«источник».

Повторим шаги 1, 2, 3 до тех пор, пока не будут вычеркнуты все вершины.

Еще один способом нахождения кратчайшего пути может служить «метод динамического программирования».

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

Составим таблицу, в которой каждая ячейка будет соответствовать определенной ячейке. Числа в ячейках будут равны минимальному числу пошлины, которое можно получить, пройдя от начала (A) до соответствующей клетки

Тема 5 : Информационные модели. Модели и моделирование.

 

Тема 5 : Информационные модели. Модели и моделирование.

Модель — это объект, который обладает существенными свойствами другого объекта, процесса или явления и используется вместо него.

Моделирование — это создание и исследование моделей с целью их изучения.

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

Информационные модели — это информация о свойствах оригиналах и его связях с внешним миром.

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

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

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

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

При моделировании всегда возникает вопрос: «Можно ли верить полученным результата?» Для этого проверяется свойство модели — АДЕКВАТНОСТЬ.

Адекватность — это совпадение существенных свойств модели и оригинала в рассматриваемой задаче. Доказать адекватность модели можно только в сравнении с оригиналом.

Для этого проверяется:

— не противоречит ли результат моделирования выводам теории,

— подтверждается ли результат моделирования результатами эксперимента.

Таким образом, любое моделирование должно соответствовать следующей схеме.

Такое моделирование позволяет:

1.   Существенно расширить круг исследуемых объектов.

2.   Исследовать процессы и явления, при необходимости ускорять или замедлять процесс.

3.   Находить оптимальное соотношение затрат.

4.   Проводить эксперименты без риска негативных последствий.

5.   Визуализировать полученные результаты.

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

Граф является многосвязной структурой, обладающей следующими свойствами:

— на каждый элемент может быть произвольное количество ссылок;

— каждый элемент может иметь связь с любым количеством элементов;

— каждая связка может иметь направление и вес.

Направленная (без стрелки) линия, соединяющая вершины графа, называется ребром.

Линия направленная (со стрелкой) называется дугой.

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

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

Граф называется взвешенным, если его вершины или ребра характеризуются некоторой дополнительной информацией — весами вершин или ребер.

Оформляют таблица в соответствии с ГОСТ 2.105-95 «ЕСКД».

Таблицы могут быть следующими типами:

«Объект — свойство», содержащими информацию о свойствах отдельных объектов, принадлежащих одному классу.

«Объект — объект», содержащими информацию о некотором одном свойстве пар объектов, принадлежащих одному или разным классам

 

Тема 4: Вредоносное программное обеспечение и способы борьбы с ним.

 

Тема 4: Вредоносное программное обеспечение и способы борьбы с ним.

1.      Информационная среда, виды информационных угроз и методы защиты информации

2.      Средства защиты информации. Вирусы и вирусные атаки

 

1.      Информационная среда, виды информационных угроз и методы защиты информации

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

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

Информационная безопасность— совокупность мер по защите информационной среды общества и человека.

Основными целями обеспечения информационной безопасности общества являются:

• защита национальных интересов;

• обеспечение человека и общества достоверной и полной информацией;

• защита человека и общества при получении, распространении и использовании информации.

Виды информационных угроз

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

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

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

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

Угрозы нарушения целостности информации. К ним относится любое злонамеренное искажение информации, обрабатываемой с использованием автоматизированных систем.

Угрозы нарушения доступности информации. Такие угрозы возникают, когда доступ к некоторому ресурсу для легальных пользователей блокируется.

Информационные угрозы безопасности информации можно также разделить на также разделить на преднамеренные и случайные

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

• хищение информации— несанкционированный доступ к документам и файлам (просмотр и копирование данных), хищение компьютеров или носителей информации, уничтожение информации;

• распространение компьютерных вирусов;

• физическое воздействие на аппаратуру— внесение в неё изменений, подключение к каналам связи, порча или уничтожение носителей, преднамеренное воздействие магнитным полем.

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

• ошибки пользователя компьютера;

• ошибки профессиональных разработчиков информационных систем;

• отказы и сбои аппаратуры, в том числе помехи и искажения сигналов на линиях связи;

• форс-мажорные обстоятельства (авария, пожар, наводнение и другие воздействия непреодолимой силы)

 

Методы защиты информации

К традиционным методам защиты от преднамеренных информационных угроз относятся следующие.

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

2.Управление — влияние на элементы защищаемой системы.

3.Маскировка — действия с защищаемой системой или информацией, приводящие к такому виду системы или информации, который делает её недоступной для злоумышленника (криптографические методы защиты и др.). Шифрование информации заключается в преобразовании (кодировании) слов, букв, слогов, цифр с помощью специальных алгоритмов.

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

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

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

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

 

 

2.      Средства защиты информации. Вирусы и вирусные атаки

Средства защиты информации

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

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

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

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

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

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

Наиболее эффективным средством защиты информации в каналах связи является применение специальных протоколов и криптографии (шифрования).

 

Вирусы и вирусные атаки

 

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

Компьютерный вирус — любая программа, созданная и используемая для реализации компьютерных угроз.

Часто такие программы называют вредоносными программами. К вредоносным программам относятся: вирусы, черви, троянцы, клавиатурные шпионы, программы для кражи паролей, макровирусы, вирусы сектора загрузки, скриптовые вирусы, мошенническое ПО, шпионские и рекламные программы. К сожалению, составить полный список вредоносных программ невозможно. Каждый год их «армия» пополняется всё новыми и новыми видами. Далее все вредоносные программы мы будем называть общим словом — вирусы.

Рассмотрим более подробно некоторые из вирусов.

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

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

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

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

 

Признаки заражения компьютера.

 Определить наличие вируса на компьютере можно, зная ранние признаки его заражения:

• уменьшение объёма свободной оперативной памяти;

• сильное замедление загрузки и работы компьютера;

• непонятные изменения в файлах, а также изменение размеров и даты их последнего изменения;

• ошибки при загрузке операционной системы и во время её работы;

• отсутствие возможности сохранять файлы в определённых папках;

• непонятные системные сообщения, музыкальные и визуальные эффекты.

 

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

• не устанавливать на компьютер нелегально распространяемое ПО;

• не скачивать файлы с неизвестных сайтов в сети Интернет;

• не открывать электронные письма от неизвестных или сомнительных адресатов;

•не подключать к своему компьютеру чужие накопители данных без предварительной проверки на наличие вирусов;

• установить на компьютер антивирусное программное обеспечение.

Для защиты от вирусов следует использовать антивирусное программное обеспечение