15. Математические методы работы с данными. Профильный уровень

Кодирование. Двоичная запись

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

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

Какие-то способы продолжают оставаться аналоговыми. Например, чтобы описать, как выглядит дом, его можно достаточно точно нарисовать. А можно назвать его размеры и цвет с помощью чисел и специфических слов вроде «фасад», «перила» и прочее. Здесь мы сталкиваемся с таким понятием, как кодирование. И тут уже совсем недалеко до цифрового сигнала. Размеры — это числа, каждому названию тоже можно присвоить число — и вот описание дома можно представить как последовательность чисел (рис. 1). Конечно, тот, кто получит такое сообщение, должен уметь его раскодировать.

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

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

Мы стандартно пользуемся десятичной системой счисления. Так сложилось исторически из-за десяти пальцев на руках, таких естественных счётов (хотя в истории были и другие системы счисления, например 60-ричная или римская непозиционная). Компьютеры работают на электрических сигналах. Сигнал или есть, или его нет. Можно сказать, что у компьютера не десять пальцев, а два. Поэтому система счисления, с которой работают компьютеры, двоичная, основанная на двух цифрах: 0 и 1. Нет сигнала — 0, есть сигнал — 1. То, что калькулятор понимает расчёты и выдаёт результаты в десятичной системе, — только интерфейс. Все процессы внутри основаны на двоичном коде. Мы должны различать пользовательский режим и непосредственно работу «движка». Пользовательский режим рассчитан на то, чтобы любой человек (даже максимально далёкий от техники) смог разобраться в оборудовании и работать с ним.

Итак, если коротко:

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

2. Основной системой счисления для кодирования, передачи, хранения и обработки информации является двоичная система.

Двоичная система счисления устроена точно так же, как десятичная, но отличается основанием — оно не 10, а 2. Вспомним, что, к примеру, означает запись 5307.

Любое целое число можно записать в виде суммы различных степеней десятки. Для этого используется 10 цифр. Вместо 10 можно использовать любое другое основание, например 8. Тогда та же самая запись будет уже означать разложение по степеням восьмёрки и в десятичной записи соответствовать числу 2759.

Для записи числа в восьмеричной системе достаточно 8 цифр. Стандартно используют те же самые цифры от 0 до 7. Если использовать 16‑ричную систему, то нужны ещё 6 цифр, которых не было в десятичной. Обычно используют латинские буквы от до . Такая система счисления используется в программировании, в компьютерных моделях цвета.

Но нас интересует двоичная система счисления. Здесь используются только две цифры: 0 и 1, и каждое целое число представляет собой сумму степеней двойки. Например, число 11010012 семизначно. Значит, старшая степень — шестая. Это число раскладывается на сумму степеней двоек следующим образом:

Запись этой суммы мы осуществили уже в десятичной системе, и в десятичной системе это число равно 105:

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

2 — это 1-я степень двойки и ноль единиц, то есть 10:

Во всех системах счисления разрядное число будет записано как 1 и 0. Десятичная система не исключение. 3 записывается двумя единицами, что логично — следующее число после 10:

Нетрудно самим продолжить и записать 4, 5, и 6 в двоичном виде:

Теперь мы можем расписать исходное число в виде степеней основания (двойки).

Дробные числа в двоичной системе счисления записываются по такому же принципу, как в десятичной системе. Число 2,73 означает 2 единицы, 7 десятых, 3 сотых то есть:

Аналогично вот такое дробное число в двоичной системе можно расписать так:

В десятичной записи это соответствует 2,375:

Перевод из одной системы в другую несложен. Из двоичной в десятичную мы уже переводили:

Записываем сумму степеней двоек и считаем её уже в десятичном виде. Осуществим перевод в обратную сторону. Запишем число 327 в двоичном виде. Для этого распишем степени двойки от нулевой до девятой.

9-я степень равна 512 и уже больше нашего числа. Начинаем расписывать число 327 в виде суммы степеней двойки:

Распишем сумму всех степеней подряд, вставив недостающие слагаемые с коэффициентом ноль:

Мы получили нужные цифры двоичного разложения и теперь можем записать само число:

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

Следующую задачу вы можете предложить решить своим друзьям. Условие у неё не очень гуманное, но если от этого абстрагироваться, то процесс решения вполне может быть интересным.

Задача 1.

Доктор должен ввести пациенту лекарство не позднее чем через полтора часа, иначе пациент умрёт. Оказалось, что в партии из 32 ампул с лекарством одна ампула содержит яд, который по виду не отличается от лекарства. В какой именно ампуле яд — неизвестно. В лаборатории есть 5 мышей, на которых можно испытать содержимое ампул (от небольшой дозы лекарства с мышью ничего не случится, от капли яда мышь умрёт через час). Сможет ли врач спасти пациента?

На первый взгляд, пяти мышей никак не хватит для проверки 32 ампул за отведённое время. Но если вы занимаетесь кодированием и часто сталкивались с двоичной системой счисления, то вы обратите внимание на связь чисел 5 и 32. 32 — это . Пронумеруем все ампулы двоичной записью. У первой ампулы номер будет 0 (пять нулей в записи), у последней — пять единиц, в десятичной системе это соответствует числу 31, то есть всего 32 номера.

Мышей тоже пронумеруем числами от 1 до 5. Каждой мыши вводится вещество из той ампулы, где на её месте в номере стоит 1. Так, вещество из первой ампулы не вводится ни одной мыши (так как в номере ампулы только нули), вещество из второй ампулы вводится только 5-й мыши, из третьей — только 4-й мыши, из четвёртой — 4-й и 5-й мышам и так далее. Вещество из последней ампулы вводят всем мышам.

Самый лучший исход — все мыши через час будут живы, значит, яд находится в первой ампуле. Если умерли 4-я и 5-я мыши, значит, яд был в четвёртой ампуле, и так далее. Задача решена.

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

Теория графов

Чтобы создать вычислительную машину, необходим двоичный код.

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

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

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

Итак, о самой задаче.

Задача 2.

На реке Преголе, протекающей через Кёнигсберг, есть два острова, соединённых мостами (рис. 3).

Вопрос: можно ли найти такой маршрут по городу, чтобы пройти по каждому мосту, но только один раз?

Для упрощения задачи Эйлер построил модель: территории суши, разделённые водой, обозначаются точками — стягиваются до точек (два острова и два берега — всего 4 точки); мосты превращаются в линии, соединяющие точки (рис. 4).

Тип полученной картинки называют графом (однокоренные слова «графика», «график») — от греческого слова «чертить».

Точки называют вершинами графа, линии — рёбрами графа.

Вершина, в которую сходится чётное количество рёбер, называется чётной. Соответственно, нечётной называется вершина, в которую сходится нечётное количество рёбер.

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

Понятно, что если вершина не является началом или концом графа, то она должна быть чётной — сколько раз в неё вошли, столько раз должны выйти. Если начало и конец — одна и та же точка, то это тоже чётная вершина, если это разные точки, то это нечётные вершины. Значит, необходимым условием безотрывного построения графа будет следующее: или все вершины чётные, или имеются ровно две нечётные. На полученном Эйлером графе все 4 вершины нечётные. Вывод ясен: решения нет. Нельзя пройти по всем мостам Кёнигсберга за один раз, не проходя ни по какому дважды.

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

Посмотрим на граф друзей в социальной сети.

Если Маша дружит с Витей, то и Витя дружит с Машей. Такой граф называется неориентированным — его рёбра не имеют выбранного направления. При этом от Маши к Лене нет пути по графу — такой граф называется несвязным (рис. 5).

Подружим Лену с Борей. Теперь от каждой вершины есть путь до любой другой — такой граф называется связным. Он, конечно, остался неориентированным (рис. 6).

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

Чтобы указать взаимных подписчиков, нужно два ребра между двумя точками. Перед нами пример ориентированного несвязного графа (рис. 7). Если Света подпишется на Петю, то мы получим связный ориентированный граф (рис. 8).

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

А во втором их даже два.

Путь Маша → Боря → Лена → Галя.

И путь Маша → Витя → Боря → Лена → Галя.

Если путь замкнут, то его называют циклом. Путь Маша → Витя → Боря → Маша является циклом.

Вспомним задачу с мостами и дадим следующие определения.

Эйлеровым путём называется путь, проходящий через все рёбра графа по одному разу (рис. 12).

Если он ещё и цикл, то так и называется — эйлеров цикл. Граф, содержащий эйлеров цикл, называется эйлеровым графом (рис. 13).

Формулируя решение Эйлера в этих определениях, получаем, что связный граф содержит эйлеров путь тогда и только тогда, когда у него ноль или две вершины нечётные, а остальные — чётные.

Если нечётных вершин ноль, то эйлеров путь является эйлеровым циклом.

Другое важное имя в теории графов — это великий ирландский математик XIX века Уильям Гамильтон.

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

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

Гамильтон исследовал задачу о кругосветном путешествии, в котором нужно посетить все большие города по одному разу.

Задача была представлена Гамильтоном в виде игры, которая представляла собой гамильтонов граф, где игрок должен последовательно соединить города, проложив гамильтонов путь (рис. 17).

Важную роль в обработке информации имеют особенные виды графов — деревья (рис. 18, слева — неориентированное дерево, справа — ориентированное).

Деревом называется связный граф, не имеющий циклов.

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

Для их описания, кроме степени вершины (количества рёбер, соединённых в вершине), говорят о степени захода и степени исхода каждой вершины.

Степень захода — количество входящих в вершину рёбер.

Степень исхода — количество исходящих.

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

Вершина с нулевой степенью захода называется корнем дерева.

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

Все узлы, кроме концевых, называются узлами ветвления.

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

Уровнем узла называется длина пути от корневого узла до него. Высотой дерева называют путь от вершины до самого далёкого листа.

Важными являются бинарные деревья (рис. 22).

Попробуйте самостоятельно дать ему определение.

Итак, бинарным называется дерево, у которого степень исхода всех вершин не превышает 2. То есть это либо узлы ветвления с одним или двумя исходящими рёбрами (их называют дугами), либо листы (без исходящих дуг).

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

Список литературы

1. Березина, Л. Ю. Графы и их применение. Популярная книга для школьников и преподавателей / Л. Ю. Березина. — М.: URSS, 2018. — 150 с. — (Науку — всем! Шедевры научно-популярной литературы (математика), № 83).

2. Мельников, О. И. Теория графов в занимательных задачах / О. И. Мельников. — Изд. 3-е, испр. и доп. — М.: Книжный дом «ЛИБРОКОМ», 2009. — 232 с.

Домашнее задание

1. Переведите число 11010,0112 в десятичную систему счисления.

2. Переведите число 49110 в двоичную систему счисления.

3. Определите степень вершины а2 в графе.

4. Ника планирует отправится в путешествие по столицам крупнейших стран мира: Оттава, Пекин, Вашингтон, Бразилиа и Канберра. Она нашла все возможные варианты авиарейсов: Оттава — Пекин, Оттава — Вашингтон, Оттава — Канберра, Пекин — Бразилиа, Вашингтон — Бразилиа, Вашингтон — Канберра (каждый перелёт в обе стороны). Можно ли попасть из Оттавы в Бразилиа прямым рейсом, с одной пересадкой, с двумя пересадками? Если да, то укажите количество способов, с помощью которых можно осуществить перелёт.