Что такое информационная модель
Представьте, что вы работаете в библиотеке, где хранится несколько тысяч книг. Каждый день к вам приходят читатели с просьбами найти определённую книгу: кому-то нужен детектив Агаты Кристи, кто-то ищет учебник по физике за 10 класс, а кто-то хочет почитать что-нибудь о космических путешествиях. Если все книги просто стоят на полках в случайном порядке, вы потратите часы на поиски нужного произведения. Придётся просматривать каждую полку, каждый корешок, надеясь наткнуться на то, что нужно.
А теперь рассмотрим другую ситуацию. Все книги организованы по разделам: художественная литература разделена по жанрам, школьные учебники определены в свой отдел, а под научпоп отведена целая секция.
Внутри каждого раздела книги расположены по алфавиту. Есть каталог, в котором можно быстро найти нужную книгу по названию или автору. Теперь на поиск книги уходят считанные минуты вместо часов!
В чём разница между этими двумя ситуациями? В первом случае информация о книгах существует, но она не структурирована и бесполезна для быстрого поиска. Во втором случае та же самая информация организована с помощью определённой системы, которая делает работу простой и эффективной.
Именно для решения подобных задач в информатике существуют информационные модели. Это специальные способы представления данных, которые помогают нам структурировать информацию, делать её наглядной и удобной для анализа. Информационная модель — это упрощённое представление реального объекта, процесса или явления, которое отражает его существенные свойства и отбрасывает несущественные детали.
Существует множество видов информационных моделей: словесные описания, математические формулы, схемы, чертежи, таблицы, графы и многие другие. Каждый вид модели используется для решения определённого типа задач. В этой статье мы подробно рассмотрим два наиболее важных и часто используемых вида информационных моделей: таблицы и графы. Эти модели помогут вам эффективно работать с данными и решать сложные практические задачи. Ну а кроме всего прочего, именно с этими моделями мы будем работать при решении заданий 1 ЕГЭ по информатике.
Таблица
Давайте рассмотрим ситуацию, которая вам хорошо знакома. Представьте, что классный руководитель получил задание проанализировать успеваемость своего 11 «А» класса по информатике за первое полугодие. Завуч передал ему список учеников со всеми оценками, который выглядит примерно так:
«Иванов Пётр получил за первую четверть 4, за вторую четверть 5. Смирнова Анна получила за первую четверть 5, за вторую четверть 5. Кузнецов Дмитрий получил за первую четверть 3, за вторую четверть 3. Петрова Мария получила за первую четверть 5, за вторую четверть 4. Сидоров Алексей получил за первую четверть 3, за вторую четверть 4.»
Не очень-то удобно анализировать, не так ли? Приходится по несколько раз перечитывать текст, запоминать цифры, сравнивать их в уме. Здесь на помощь приходит структурирование данных в виде таблицы.
Таблица — это информационная модель, которая представляет данные в виде строк и столбцов. Она позволяет упорядочить информацию так, что поиск и анализ данных становятся максимально простыми и наглядными.
Любая таблица состоит из нескольких элементов. Заголовки столбцов описывают, какая информация содержится в каждом столбце. Строки содержат информацию об одном объекте, в нашем случае — об одном ученике. Ячейки находятся на пересечении строк и столбцов и содержат конкретные значения.
Давайте преобразуем наше текстовое описание оценок учеников в таблицу:
Посмотрите, как изменилась ситуация! Теперь вся та же самая информация стала наглядной и понятной. За несколько секунд можно увидеть, что у Смирновой Анны стабильные пятёрки, у Иванова Петра и Сидорова Алексея оценки улучшились, а вот Петровой Марии стоит уделить внимание, так как её успеваемость снизилась. Кузнецову Дмитрию определённо нужна дополнительная помощь.
Более того, если эта таблица не «рукописная», а электронная, то можно автоматически подсчитывать средний балл по классу, количество отличников, хорошистов и так далее. В таком формате работать становится гораздо проще и эффективней.
Таблицы незаменимы, когда нужно систематизировать однородные данные, например, информацию о группе учеников, товарах в магазине, спортивных результатах. С помощью таблиц удобно сравнивать объекты по различным параметрам: можно сразу увидеть, кто учится лучше, а кому нужны дополнительные занятия.
Современные программы для работы с таблицами, такие как Excel или Calc, позволяют автоматически производить вычисления: находить суммы, средние значения, максимумы и минимумы, строить графики и диаграммы. Например, наш классный руководитель может одним щелчком мыши построить диаграмму успеваемости класса и приложить её к отчёту.
Таблицы также можно легко сортировать. Хотите увидеть учеников по убыванию среднего балла? Нет проблем — один клик, и таблица перестроится так, что отличники окажутся вверху списка. Хотите найти всех учеников с динамикой «Улучшение»? Используйте фильтр, и таблица покажет только нужные строки.
Однако таблицы не всегда удобны. Попробуйте представить в виде таблицы отношения между людьми в социальной сети или схему метрополитена. Получится громоздко и неудобно. Для таких задач существуют другие информационные модели, и одна из самых мощных среди них — это граф.
Граф
Граф — это информационная модель, состоящая из вершин (узлов) и рёбер (связей между вершинами). Графы идеально подходят для представления систем, где важны не столько сами объекты, как связи между ними.
Давайте рассмотрим практическую задачу, чтобы понять, как работают графы. Предположим, что живём мы в прекрасном посёлке с названием «Колыбелька». По соседству от нас не менее прекрасные Петрово, Жогино и Васюки.
Как-нибудь абстрактно отметим их на импровизированной карте:
Также на карту нанесём дороги, которые соединяют эти населённые пункты друг с другом. Нам известно, что есть следующие дороги:
- Между Колыбелькой и Петрово
- Между Колыбелькой и Жогино
- Между Петрово и Васюками
- Между Жогино и Васюками
Отметим эти дороги зелёными линиями.
Что же, таким нехитрым способом мы получили граф! К практической задаче мы вернёмся немного позже. Давайте сначала познакомимся поближе с этой информационной моделью и дадим определение основным терминам.
Начнём с вершин, которые также называют узлами. Вершины — это объекты, которые мы моделируем. В нашем примере это населённые пункты (Колыбелька, Петрово и прочие). Вершины обычно обозначают точками или кружками и подписывают названиями или номерами.
Рёбра, которые иногда называют дугами или связями — это линии, соединяющие вершины. Они показывают, что между объектами существует какая-то связь. В нашем случае рёбра — это дороги между населёнными пунктами.
Когда каждому ребру присвоен числовой параметр, граф называют взвешенным. Этот параметр называется весом ребра. Вес может обозначать расстояние, стоимость, время или любую другую величину, которая важна для решаемой задачи. Чуть позже мы сделаем из нашего графа взвешенный, но всему своё время.
Ещё важно различать направленные и ненаправленные графы. В ненаправленном графе рёбра не имеют направления: если можно пройти от вершины А к вершине Б, то можно и обратно. Это похоже на двустороннюю дорогу, по которой можно ехать в обе стороны.
В направленном графе, который ещё называют орграфом (ориентированным графом), рёбра имеют направление, обозначаемое стрелкой. Это может соответствовать односторонней дороге или отношениям, которые не симметричны. Например, в генеалогическом дереве связь родитель-ребёнок направлена только в одну сторону.
Графы можно представлять не только визуально в виде рисунка, но и в виде таблиц. Да, мы снова возвращаемся к таблицам! Оказывается, эти два типа информационных моделей прекрасно дополняют друг друга. Существует два основных способа табличного представления графов.
Первый способ называется матрицей смежности. Это таблица, которая показывает, какие вершины соединены рёбрами. Строки и столбцы этой таблицы соответствуют вершинам графа, а в ячейках ставится единица, если между вершинами есть связь, и ноль, если связи нет. Но могут быть и другие обозначения, например, при наличии связей между вершинами в соответствующей ячейке может стоять знак «*».
В нашем же примере матрица смежности будет отражать наличие дороги между двумя населёнными пунктами. Изобразить её можно следующим образом:
По этой матрице смежности, даже не видя граф, мы можем понять, что вершина «Колыбелька» соединена с «Петрово» и «Жогино», «Петрово» — с «Колыбелька» и «Васюки», в свою очередь вершина «Жогино» соединена с «Колыбелька» и «Васюки», а «Васюки» с «Петрово» и «Жогино».
Кстати, обратите внимание, что наш граф неориентированный — у дорог нет направления, ведь можно проехать как с Колыбельки в Петрово, так и обратно — с Петрово в Колыбельку. Если бы обратной дороги не существовало бы, то во второй строке на пересечении со столбцом «Колыбелька» знак «*» отсутствовал бы.
По матрице смежности можно построить граф и, наоборот, по графу можно составить матрицу смежности. Эти две модели взаимозаменяемы и применяется каждая в своей ситуации: например, для большей наглядности можно воспользоваться графом, а для поиска конкретной дороги для нужного населённого пункта проще будет взглянуть на таблицу, чем искать этот пункт на графе, особенно большом и запутанном.
Но есть и второй способ табличного представления графов — весовая матрица. И, как уже говорилось ранее, нам нужно добавить «веса» нашему графу.
Что же, вернёмся к формулировке задачи. Итак, есть у нас 4 посёлка, между ними проложены дороги. А нам нужно добраться из родной Колыбельки в Васюки, да причем так, чтобы потратить как можно меньше времени и сил. То есть наша задача — найти кратчайший путь от пункта А в пункт Б.
Здесь нам не обойтись без знания протяжённости дорог. Выпишем длину каждой из проложенных дорог:
- Дорога Колыбелька-Петрово: 20 км
- Дорога Колыбелька-Жогино: 8 км
- Дорога Петрово-Васюки: 10 км
- Дорога Жогино-Васюки: 25 км
Не будем повторять мысль о том, что в таком виде воспринимать протяжённость дорог довольно сложно. А определить оптимальный путь еще сложнее. Но не зря же мы изучаем информационные модели, так давайте отметим длину каждой дороге на нашем графе!
Вот так гораздо наглядней. Сразу видно, что у нас есть два варианта пути: через Петрово и через Жогино. Отсюда можем найти протяжённость обоих маршрутов: 30 км для первого и 33 км для второго. Тут всё очевидно: Петрово — наш выбор!
Но вернёмся к матрицам. Весовая матрица, как несложно догадаться, похожа на матрицу смежности. Отличия их состоит лишь в одном: вместо «звёздочек», обозначающие просто существование какого-то ребра, у нас будут конкретные числа — веса эти рёбер или же протяжённости дорог в нашем случае. Заполним весовую матрицу значениями:
Мы познакомились почти со всеми нужными терминами. Остался лишь один — степень вершины. Степенью вершины называется количество рёбер, которые выходят из данной вершины. Так, на рассматриваемом графе у каждой вершины степень 2.
Но давайте теперь представим, что между Жогино и Васюками построили новый населённый пункт — Озерки. Также из него проложили дорогу в Петрово, а дороги между Васюками и Жогино больше не существует. Получим такой граф:
Теперь у нас есть 3 вершины со степенью 3 (Петрово и Озерки) и 3 вершины со степенью 2 (Колыбелька, Васюки и Жогино).
Итоги
В данной статье рассмотрели две важнейшие информационные модели: таблицы и графы. Таблицы помогают структурировать однородные данные и упрощают их анализ, делая поиск информации быстрым и удобным. Как мы видели на примере с успеваемостью класса, преобразование бесструктурного текста в таблицу превращает хаос в порядок и позволяет мгновенно находить нужную информацию, сравнивать данные и делать выводы.
Графы незаменимы, когда нужно моделировать связи между объектами и находить оптимальные решения в сложных системах, где важна структура отношений. Задача о поиске кратчайшего пути между населёнными пунктами показала, как граф превращает запутанную информацию о дорогах в наглядную схему, с которой легко работать.
Эти модели не конкурируют между собой, а дополняют друг друга. Более того, как мы видели, графы сами можно представить в табличном виде через матрицы смежности и весовые матрицы! Владение обеими моделями делает вас более эффективными в решении самых разных задач — от анализа школьной успеваемости до планирования путешествий.
Теперь с новыми знаниями мы можем уверенно приступать к разбору алгоритма решения задания 1 ЕГЭ по информатике, в котором нам как раз предстоит работать как с графами, так и с матрицами смежности или весовыми матрицами. Но об этом — в следующей статье.