Файл: Информация в материальном мире(Основные типы данных и их классификация).pdf

Связные списки

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

Рисунок 2 Связные списки

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

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

Стеки

Стек — это базовая структура данных, в которой вы можете только вставлять или удалять элементы в начале стека.^[7] Он напоминает стопку книг. Если вы хотите взглянуть на книгу в середине стека, вы сначала должны взять книги, лежащие сверху.

Стек считается LIFO (Last In First Out) — это означает, что последний элемент, который добавлен в стек, — это первый элемент, который из него выходит.

Рисунок 3 Стеки

Существует три основных операции, которые могут выполняться в стеках: вставка элемента в стек (называемый «push»), удаление элемента из стека (называемое «pop») и отображение содержимого стека (иногда называемого «pip»).

Очереди

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

Рисунок 4 Очереди

Если рассматривать очередь с точки доступа к данным, то она является FIFO (First In First Out). Это означает, что после добавления нового элемента все элементы, которые были добавлены до этого, должны быть удалены до того, как новый элемент будет удален.
В очереди есть только две основные операции: enqueue и dequeue. Enqueue означает вставить элемент в конец очереди, а dequeue означает удаление переднего элемента.

Рисунок 5 Множества

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

• Union (Объединение). Объединяет все элементы из двух разных множеств и возвращает результат, как новый набор (без дубликатов).
• Intersection (Пересечение). Если заданы два множества, эта функция вернет другое множество, содержащее элементы, которые имеются и в первом и во втором множестве.
• Difference  (Разница). Вернет список элементов, которые находятся в одном множестве, но НЕ повторяются в другом.
• Subset(Подмножество) — возвращает булево значение, показывающее, содержит ли одно множество все элементы другого множества.

Map

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

Map’ы позволяют сделать следующее:

• Добавление пары в коллекцию
• Удаление пары из коллекции
• Изменение существующей пары
• Поиск значения, связанного с определенным ключом

Рисунок 6 Хэш-таблицы

Хэш-таблица — это структура данных, реализующая интерфейс map, который позволяет хранить пары ключ / значение. Она использует хеш-функцию для вычисления индекса в массиве, по которым можно найти желаемое значение.

Хеш-функция обычно принимает строку и возвращает числовое значение. Хеш-функция всегда должна возвращать одинаковое число для одного и того же ввода. Когда два ввода хешируются с одним и тем же цифровым выходом, это коллизия. Суть в том, чтобы их было как можно меньше. Поэтому, когда вы вводите пару ключ / значение в хеш-таблице, ключ проходит через хеш-функцию и превращается в число.^[8]

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

Глава 2. Характеристика информации

2.1 Передача информации в компьютерных сетях

Протоколы, предназначенные для маршрутизации в мобильной беспроводной сети, подразделяются на три основные категории. Это проактивные, реактивные и гибридные протоколы маршрутизации. В каждой категории существуют несколько протоколов: Реактивные протоколы маршрутизации начинают создавать маршруты только по требованию. Протокол маршрутизации будет пытаться установить маршрут в том случае, когда какой-либо узел захочет установить связь с другим узлом к которому он не имеет маршрута. Этот тип протоколов обычно основывается на заполнении сети сообщениями типа Route Request (RREQ) и Route Reply (REPL).^[9]

При помощи со общений Route Request маршрут определяется от источника к необходимому узлу (цель), и как только необходимый узел получает RREQ сообщение, он отправляет REPL сообщения для подтверждения того, что маршрут установлен. Этот тип протоколов как правило эффективен в сетях с одинаковыми характеристиками и параметрами. Он обычно уменьшает количество прыжков выбранного маршрута.

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

Примеры реактивных протоколов маршрутизации: AODV (Ad hoc OnDemand Distance Vector Routing Protocol) DSR (Dynamic Source Routing Protocol) ACOR (Admission Control enabled On demand Routing Protocol) ABR (Associative Based Routing Protocol). Проактивные протоколы маршрутизации MANET также называют таблично-ориентированными протоколами, которые активно определяют уровень состояния сети.

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

Таким образом, в результате повышения мобильности, существует недостаток, выраженный в увеличении объема трафика, генерирующегося при построении ненужных маршрутов. Особенно это заметно при значительном увеличении размера сети. Часть общего трафика управления, который состоит из актуальных практических данных, уменьшается.^[10] Наконец, если узлы передают данные нечасто, то большая часть маршрутной информации рассматривается как избыточная.

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

Таким образом, проактивные протоколы маршрутизации лучше работают в сетях с низкой мобильностью или в сетях с часто генерируемым трафиком. Примеры проактивных протоколов маршрутизации: OLSR (Optimized Link State Routing Protocol) FSR (Fisheye State Routing Protocol) DSDV (Destination Sequenced Distance Vector Routing Protocol). CGSR (ClusterHead Gateway Switch Routing Protocol).

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

Примеры гибридных протоколов маршрутизации: TORA (Temporallyordered Routing Algorithm Protocol) HSR (Hierarchical State Routing Protocol) ARPAM (Adhoc Routing Protocol for Aeronautical Mobile AdHoc Networks) OORP (OrderOne Routing Protocol) качестве средства имитационного моделирования использовался сете вой симулятор OPNET (Optimized Network Engineering Tool) Modeler вер сии 14.0. Это наиболее широко используемый коммерческий симулятор, работающий под операционной системой Microsoft Windows и включающий в себя реализацию исследуемых нами протоколов маршрутизации.^[11]

Данный программный продукт не только поддерживает MANET маршрутизацию, но и также предоставляет параллельное ядро для поддержки увеличения стабильности и мобильности в сети. Функции интенсивного анализа OPNET обеспечивают лучшие условия для сравнения, вычисления и координации выходных данных. В рамках Opnet Modeler пользователи могут использовать графическую среду для того, чтобы создать, выполнить и проанализировать событийное моделирование сетей связи.

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

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

Генерацию случайного трафика можно автоматически сгенерировать из алгоритмов, которые указаны пользователями, а также импортировать на базе имеющихся в стандартной комплектации пакетов форматов реальных трафиков. Проведение анализа результатов моделирования можно осуществить, а генерацию графов и анимации трафика можно сделать автоматически.^[12] Среди возможных плюсов при формировании модели сети на основе программного обеспечения следует отметить то, что уровень гибкости, который обеспечивается с привлечением ядра моделирования, тот же, что и для моделирования, которое создано с нуля, но с использованием объектного построения среды.

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

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

В редакторах процессов пользователи могут определять модели процессов через комбинации алгоритмов работы конечных автоматов (finitestate machine FSM) и операторов языков программирования C/C++. Проведение вызова событий модели процессов при моделировании управляется на основе возбуждения прерывания, а каждое из прерываний соответствует событиям, которые должны быть обработаны в рамках модели процессов.

2.2 Взаимосвязь данных и информации

В 2017 г. не склонные к риску предприятия наконец освоили облака — а мы и не заметили, пишет на портале TechTarget старший аналитик и консультант Taneja Group Майк Мэтчетт. Незаметно произойдет и переход к новым технологиям хранения данных в 2018 г.

Порой большие изменения подкрадываются очень тихо. Особенно если речь идет о будущем технологий хранения данных. Мэтчетт предлагает обратить внимание на следующие тренды:

Контейнеры появились благодаря давнему желанию найти удачный способ упаковки приложений. В этом году управление контейнерами корпоративного класса достигнет уровня зрелости управления виртуальными машинами, не утратив тех преимуществ, которыми обладают контейнеры по сравнению с виртуальными машинами.^[13] Чисто программные (software-defined) ресурсы, такие как хранение, будут предоставляться главным образом в виде контейнеров.

В сочетании с динамическими операционными API-интерфейсами эти ресурсы составят очень гибкие программируемые инфраструктуры. Такой подход позволит производителям упаковывать приложения вместе с необходимой для них инфраструктурой в модули, которые можно развернуть где угодно, создавая даже такие облака, какие создают ЦОДы. Возможность развернуть ЦОД по запросу будет широко использоваться, например, при восстановлении после катастроф. Все говорят об искусственном интеллекте, а в действительности это машинное обучение постепенно проникает во все поры управления ИТ.