Контрольная работа по "Информационное общество"

                                                              Вариант 4.

         1.Возможно ли, чтобы бинарный ответ содержал меньше 1 бит информации?

Способов передачи информации существует множество: почта, телефон, радио, телевидение, компьютерные сети и пр. Однако в  них можно выделить общие элементы (рис. 3).

                   Рис. 3. Общая схема передачи информации

Источник информации порождает информацию и для передачи представляет ее в виде сообщения. Для представления информации он использует систему кодирования. Кодирующее устройство может являться подсистемой источника или внешним устройством по отношению к источнику информации.

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

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

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

Линия связи объединяет все элементы от источника до приемника информации. Характеристиками линии связи являются скорость передачи сообщения, а также степень искажения сообщения в процессе передачи.

                                                   Характеристики канала связи

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

Ширина полосы пропускания – интервал частот, используемый каналом связи для передачи сигналов.

В данном случае важна не сама ширина полосы пропускания, а максимальное значение частоты (n_m) из данной полосы, поскольку именно она определяет возможную скорость передачи информации по каналу.

Длительность элементарного импульса определяют исходя из следующих соображений. Если параметр сигнала меняется синусоидально, то за один период колебания Т сигнал будет иметь одно максимальное и одно минимальное значения. Если аппроксимировать синусоиду прямоугольными импульсами и сместить начало отсчета на уровень минимального значения (рис. 4), получится, что сигнал принимает всего два значения: максимальное – импульс (обозначим его 1) и минимальное – пауза (0).

 Рис. 4. Аппроксимация синусоидального параметра сигнала

Импульс и пауза – элементарные сигналы. При выбранной аппроксимации  длительности сигналов (t₀) одинаковы и равны:

Если же импульсы порождаются тактовым генератором, имеющим частоту n_m, то

Таким образом, n_m определяет длительность элементарного сигнала t₀, используемого для передачи сообщения.

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

Если I_imp выражено в битах, а t₀ – в секундах, то единицей измерения С будет бит/с. Величину I_imp можно установить следующим образом: если первичный алфавит содержит N знаков с вероятностями появления их в сообщении р_i, то по формуле Шеннона можно найти среднюю информацию на знак первичного алфавита I₁, для представления которого используется двоичный код длиной K⁽²⁾. Тогда

                                                                             .

Отсюда получаем формулу для  определения пропускной способности  канала:

Скорость передачи информации. Пусть по каналу связи за время t передано количество информации I. Можно ввести величину, характеризующую быстроту передачи информации – скорость передачи информации J:

                                                                                .

Размерностью J, как и С, является бит/с.

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

Влияние шумов на пропускную способность канала.

Отличие реального канала от идеального состоит в том, что шумы приводят к снижению пропускной способности  канала.В реальном канале из-за шумов при передаче может произойти искажение сигнала. Пусть его вероятность равна р. Тогда вероятность того, что исходный сигнал придет без искажений, равна 1–р. Следовательно, при распознавании конечного сигнала возникает неопределенность, которая может быть охарактеризована средней энтропией:

                                                             H = –p × log₂p – (1 – p) × log₂(1 – p).                    (5.1)

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

Поскольку длительность импульса t₀ определяется частотой n_m и не зависит от наличия шумов, пропускная способность реального канала C_R оказывается меньше, чем аналогичного идеального С:

                                          .

Обеспечение надежности передачи и хранения информации

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

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

Решение проблемы состоит в использовании  таких методов кодирования информации, которые позволили бы контролировать правильность передачи и при обнаружении  ошибки исправлять ее. При этом можно  рассмотреть две ситуации:

· кодирование обеспечивает только установление факта искажения информации, в этом случае исправление производится путем ее повторной передачи;

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

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

Избыточность сообщения (L) для реального канала определим следующим образом:

                                                               .

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

Для восстановления информационного  содержания сообщения следует дополнительно  передать количество информации не менее  величины ее потерь, т. е. вместо передачи каждого 1 бита информации следует передавать 1 + Н битов. В этом случае избыточность сообщения составит

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

                                                                    Код Хемминга

Идея состоит в добавлении к информационным битам нескольких битов четности, каждый из которых  контролирует определенные информационные биты. Если пронумеровать все передаваемые биты, начиная с первого слева  направо (информационные биты нумеруются с нулевого и справа налево), то контрольными оказываются биты, номера которых  равны степеням числа 2, а все остальные  являются информационными. Например, для  восьми битного информационного  кода (рис. 5) контрольными окажутся биты с номерами 1, 2, 4 и 8:                                     Рис. 5. Восьмибитный информационный код

                              Рис. 5. Восьмибитный информационный код

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

                                        Таблица 9. Номера контролируемых битов для проверочных

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

Номер бита, содержащего ошибку, равен  сумме номеров контрольных битов, указавших на ее существование.

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

1. Произвести проверку всех битов четности.

2. Если все биты четности верны, то перейти к пункту 5.

3. Вычислить сумму номеров всех неправильных битов четности.

4. Инвертировать содержимое бита, номер которого равен сумме, найденной в пункте 3.

5. Исключить биты четности, передать правильный информационный код.

Избыточность кодов Хемминга для  различных длин передаваемых последовательностей  приведена в табл. 10.

Видно, что выгоднее передавать и  хранить более длинные последовательности битов. При этом избыточность не должна оказаться меньше L_min для выбранного канала связи.

                                                     Таблица 10. Избыточность кодов Хемминга

                        2.Чем обусловлена необходимость  структурирования данных?

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

• структура информации — схематичная форма представления сложных композиционных объектов и связей реальной предметной области, выделяемых как актуально необходимые для решения прикладных задач;

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

• структура записей — целесообразная (учитывающая особенности физической среды) реализация способов хранения данных и организации доступа к ним как на уровне отдельных записей, так и их элементов (с целью определения основных и вспомогательных функциональных массивов, а также совокупности унифицированных процедур манипулирования данными). Структура является общепринятым и удобным инструментом, одинаково эффективно используемым как на уровне сознания человека при работе с абстрактными понятиями, так и на уровне логики машинных алгоритмов. Структура позволяет простыми способами свести многомерность содержательного описания к линейной последовательности записей. Именно это позволяет формализовать на общей понятийной основе взаимосвязь представлений информации в разных средах: обеспечить контролируемое сведение бесконечного разнообразия объектов и видов взаимосвязей реального мира к жестко детерминированному описанию—совокупности двоичных данныхи машинно-ориентированных алгоритмов их обработки. Выделение трех видов структур, относящихся к представлению объектов предметной области, имеет, в некотором смысле, принципиальный характер. Структура информации — это неотъемлемое свойство информации (сведений, сигналов, воспринимаемых субъектом) о некоторой совокупности объектов предметной области в контексте практической задачи (решаемой субъектом), в общем случаебезучетатого,будутлидляеерешенияиспользованысредствапрограммированияивычислительныемашины.Структурированиеинформацииосуществляетсясистемныманалитикомисводится к выделениюоперационныхобъектов и определению их характеристических свойств и взаимосвязей. Структура данных — этоопределениеинформационныхмассивов(составаивзаимосвязейданныхналогическомуровне,соответствующих характеру информации и видам соответствующих преобразований). При определении структур данных необходимо не только установить состав массива, но и определить оптимальную их взаимосвязь (и, соответственно, определить критерии и методы оценки эффективности), например, выделение групп или агрегатов, имеющих иерархическую идентификацию. Эффективность в этом случае связывается с процессом построения программы («решателя» прикладной задачи) и, в каком – то смысле — с эффективностью работы программиста. Например, при функциональной обработке массива необходимо обращаться к отдельным элементам, в то время как в операциях присваивания или при записи массива в файл поэлементное обращение приведет к увеличению размера текста программы, а в ряде случаев—к увеличению времени выполнения. Структура записи — это определение структуры физической памяти: выделение, освобождение и защита областей физического носителя, способы адресации и пересылки. Эффективность в этом случае связывается с процессами обмена между устройствами оперативной и внешней памяти, искусственно вводимой для обеспечения функциональной эффективности отдельных операций (например, поиска по ключам) посредством избыточности данных. Рассмотрим разновидности и типологию «компьютерных» логических структур данных с точки зрения особенности их организации. Структура здесь в первую очередь определяет алгоритм выборки отдельных элементов данных, но в то же время необходимо отметить, что она отражает и особенности«технологии»организациииобработкиинформации,свойственныечеловекувегоповседневнойдеятельности.Физическипонятию структура соответствует записьданных. Записьэтоупорядоченнаявсоответствиисхарактеромвзаимосвязейсовокупность полей (элементов)данных,размещаемыхвпамятивсоответствиисих типом". Полепредставляетсобойминимальную адресуемую (идентифицируемую) часть памяти — единицу данных, на которую можно ссылаться при обращении к данным. Таким образом, структура данных — это способ отображениязначенийвпамяти:размеробластиипорядокеевыделения(которыйиопределитхарактерпроцедурыадресации/выборки).Зачастуюименноуспешностьструктурирования данных определяет сложность процедур их обработки.  Классификация структур данных должна проводиться с двух точек зрения.

1. По характеру взаимосвязи элементов  структуры (с точки зрения порядка  их размещения/выборки) виды структур  можно разделить на линейные и нелинейные.

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

                                                      3.5.1. Линейные структуры.

К линейным структурам относятся массивы  и последовательности таблицы. Порядок  следования (и, соответственно, выборки) элементов таких структур имеет  линейный характер и соответствует  порядку расположения элементов  в памяти: один за другим без каких-либо промежутков. Адрес элемента соответствует  его положению и определяется индексом — порядковым номером элемента в последовательности размещения. К  элементу имеется прямой доступ, если известен его индекс. Особенностью линейной структуры является то, что  при последовательной организации (размещении) она допускает возможность  прямого доступа к произвольному  элементу, поскольку условие однородности (однотипности) предполагает, что все  элементы занимают расположенные строго последовательно области одинакового  размера, что и позволяет достаточно просто вычислять значение физического  адреса элемента по значению его индекса. Массив представляет собой совокупность однотипных элементов, причем число элементов массива известно до его размещения, что позволяет строить гибкие многомерные системы адресации. Последовательность, так же, как и массив, представляет собой совокупность однотипных элементов. Однако число элементов до размещения неизвестно. И, хотя каждая конкретная последовательность имеет конечную длину, до начала обработки (и, соответственно, размещения) необходимо считать длину последовательности бесконечной. Принципиальность такого предположения выражается в том, что необходимо предусматривать специальную процедуру использования памяти (выделения/освобождения) и, возможно, алгоритм обработки последовательности по частям. Важность рассмотрения такого типа данных обусловлена тем, что именно он превалирует в операциях ввода/вывода с устройствами внешней памяти. Именно последовательный доступ позволяет организовать «потоковые» операции : однородность позволяет рассматривать пересылаемые данные как непрерывный поток. Поток не может быть прерван по контекстно определяемому условию, например, при пересылке текста — по значению кода «перевод строки», и это не заставляетпрограммуанализироватьзначениекаждогоочередногоэлемента.И,крометого,последовательныйдоступэтопростотауправленияпамятьюиустройствомвводавывода.Таблицаэтопоследовательности,обычнопредставляемыестроками— совокупностями разнотипных элементов. Или, иначе, таблица — это множество записей, каждаяизкоторыхпредставляетнаборпоименованныхполей.Однакосточкизренияразмещенияэлементовтаблицаможетбытьпредставленакакодномерныймассив(или,вслучаеВДпоследовательность)соднороднымикомпозиционнымиэлементами,каждыйизкоторыхпредставляетсобойсовокупность разнотипных элементов. Именно это позволяет свести ввод/вывод таких джипов структур к последовательным элементарным операциям. Кроме того, разнотипность элементов позволяет ввести отличную от перечислительной схему идентификации записей, определив одно из полей как ключ записи. Обычно ключ содержит значение, используемое в процедурах упорядочения и поиска записей. 

                                                      3.5.2. Нелинейные структуры.

В качестве примеров нелинейных структур рассмотрим списки, деревья и сети. Порядок следования (и, соответственно, выборки) элементов таких структур может не соответствовать порядку  расположения элементов в памяти. Списки представляют собой пример линейного  упорядочения, деревья — двумерного, сети — произвольного. Соответственно различаются методы и средства, обеспечивающие последовательность выборкиэлементовданных.Обычнодляобеспечениявозможностипрямогодоступакпроизвольномуэлементунеобходимоиспользоватьвспомогательныеструктурытипаинвертированныхсписков. Какимассив, список представляет собой совокупность однотипных элементов. Однако порядок выборки элементов может отличаться от порядка следования в памяти, определенного при размещении. Наиболее очевидный способ установления однонаправленного порядка выборки элементов — это сопоставить каждому элементу списка ссылку, указывающую на следующий элемент. Соответственно, для организации двунаправленного списка, допускающего также выборку в обратном порядке, каждый элемент должен иметь ссылку на предыдущий. Такая организация уже не допускает возможности прямого доступа, например, по номеру элемента. Кроме того, число элементов списка, как и в случае последовательностей, может быть неизвестно до размещения, и до начала обработки (и, соответственно, размещения) необходимо считать длину списка бесконечной, что ведет к необходимостипредусматриватьспециальнуюпроцедурувыделения/освобожденияпамяти.Такимобразом,сточкизренияфизическойреализацииэлементспискадолженбыть составным, включающимсобственноинформативные данные, несущие смысловое значение, и дополнительные данные (ссылки), определяющие порядок доступа к информативным элементам. Понятие списка достаточно универсально. В общем случае ссылки могут указывать ответвления к другим спискам — подспискам. В зависимости от способа построения списка и предполагаемых путей доступа к элементам различают следующие виды ссылок: перекрестные, боковые, иерархические, множественные, что позволяет изменять «естественный» последовательный порядок прохода по элементам списка. Дерево (рис. 3.7) представляет собой иерархию элементов, называемых узлами. На самомверхнемуровнеиерархииимеетсятолькоодинузелкорень.Каждыйузел,кромекорня,связансоднимузломнаболеевысокомуровне,называемым исходным узлом для данного узла. Каждый элементимееттолько один исходный. Каждый элемент может быть связан с одним или несколькими элементами на более низком уровне, которые называются порожденными. Элементы, расположенные в конце ветви, т. е. не имеющие порожденных, называются листьями. Существует несколько способов представления структуры дерева. Например, дерево может быть определено как иерархия узлов с по парными связями, в которой:1. Самый верхний уровень иерархии имеет один узел, называемый корнем. 2. Все узлы, кроме корня, связываются с одним и только одним узлом на более высоком уровне по отношению к ним самим. Такое определение в части организации связей совпадает со списком, и, в частности, список представляет вырожденный случай дерева, в котором каждаявершинаимеетнеболееодногоподдерева.Ещеразотметим,чтодеревьяздесьрассматриваютсякаксредствоидлялогического,идляфизическогопредставленияданных.Влогическомописанииданныхонииспользуютсядляопределениясвязеймеждуэлементамиструктуры,априопределениифизическойорганизацииданныхдляопределениянаборауказателей, реализующих связи между ними. Использование ссылок для организации доступа к отдельным элементам структурынепозволяетсократить процедуру поиска, в основу которой положен последовательныйперебор.Процедурапоискабудетэффективнее,еслибудетпредварительноустановленнекоторыйпорядокпереходак следующемуэлементудерева.Такойпорядокврядеслучаевопределяетсявотношении методаобхода и регулярности итераций,определяемойдлинойпутиикратностьюделениявершины.Выделяют[2]триметодаобхода: сверхувниз,слеванаправо,снизувверх.Регулярностьобходадереваможетбытьсвязанас упорядоченнымидеревьями, ккоторымотносятся сбалансированные (рис.3.8)и двоичныедеревья (рис.3.9).Сбалансированноедерво вкаждомузлеимеетодинаковое число ветвей,причемпроцессвключенияновыхветвейвузлыдереваидетсверхувниз,анакаждомуровнедереваслеванаправо.Длядеревасфиксированнымчисломветвейфизическаяорганизацияданныхбудетболеепростой.Однакобольшаячастьлогическихорганизацийданыхнеможетбытьзаданаввидесбалансированной древовидной структуры, и для их представления требуется переменное число ветвей в каждом узле. В то же время индексымогутбытьпостроеныввидесбалансированныхдреввидныхструктур.Двоичныедеревьяэтоособаякатегориясбалансированных древовидных структур, в которой допускается не более двух ветвей для одного узла. На рис. 3.9 показано несбалансированное двоичное дерево. Любые связи в дереве можно представить в виде двоичных древовидных структур. Рис. 3.10 иллюстрирует представление дерева в виде двоичного дерева. При таком представлении каждый элемент может иметь указатели как на порожденные, так и на подобные элементы. Различные виды двоичных деревьев, для которых характерно наличие жесткой схемы управления их ростом, достаточно эффективно используются для построения больших поисковых индексов, размещаемых обычно на устройствах внешней памяти. Кроме того, для таких деревьев можно организовать специальное «страничное» хранение под деревьев, что сократит число физических обращений к устройству. Заметим, что деревья по исковых индексов являются однородными структурами: каждый узел представлен элементами одного типа. Однако большинство баз должно поддерживать организацию данных, имеющих различную природу. В этом случае при работе с неоднородными структурами разной глубины, гарантировать регулярность, обеспечивающую эффективность процедур доступа, становится затруднительно.

                                                         3.5.3.Сетевые структуры.

Иерархические структуры характерны для многих областей, однако во многих случаях отдельная запись требует  более одного представления или  связана с несколькими другими. В результате получаются обычно более  сложные структуры по сравнению  с древовидными. Например, генеалогическое дерево может быть представлено в виде древовидной структуры, только если для каждого элемента (личности) будет показан только один исходный элемент (родитель). Если бы были показаны оба родителя, то это была бы более сложная структура. В сетевой структуре любой элемент может быть связан с любым другим элементом. Примеры сетевых структур приведены на рис. 3.11.Так же, как и в случае древовидных структур, сетевую структуру можно описать с помощью исходных и порожденных элементов. Удобно представлять ее так, чтобы порожденные элементы располагались ниже исходных. При рассмотрении некоторых сетевых структур естественно говорить об уровнях, так же как и в случае древовидных структур. Во многих сетевых структурах, задающих связи между элементами, представление отношений между исходными и порожденными элементами аналогично представлению отношений в случае дерева: отношение исходный — порожденный является сложным (указывается сдвоенными стрелками), а отношение порожденный — исходный — простым (указывается одинарными стрелками). На рис. 3.12 показана неоднородная сетевая структура с пятью типами  элементов. Ни одна из их соединяющих линий не имеет сдвоенных стрелок в обоих направлениях. Каждое отношение может рассматриваться как отношение « исходный — порожденный». Запись ЗАКАЗ-НА-ЗАКУПКУ является порожденной по отношению к записи ИЗДЕЛИЕ и исходной по отношению к записи ПАРТИЯ-ТОВАРА. на закупку Желательно отличать структуры, в которых представление отношений « порожденный - исходный» является  простым  или не используется,отструктур,вкоторыхпредставлениеотношениймеждукакимитодвумятипамиданных  является сложным в обоих направлениях.

Для структур второго типа на одной  из линий схемы будут сдвоенные  стрелки, указывающие в разные стороны. Этот тип схемы назовем сложной сетевой структурой, а схему, в которой ни на одной из линий нет сдвоенных стрелок в обоих направлениях, — простой сетевой структурой. На рис. 3.12 показана простая сетевая структура. Она станет сложной, если ввести отношение ЗАКАЗ-НА-ЗАКУПКУ — ИЗДЕЛИЕ, когда один заказ может быть сделан сразу на несколько изделий. Для образования сложной сетевой структуры достаточно двух типов элементов. Например, ПОСТАВЩИК может иметь несколько порожденных записей, потому что может поставляться более одного вида изделий. С другой стороны, элемент ИЗДЕЛИЕ может иметьболееодногоисходногоэлемента,посколькуэтоизделиеможетпоставлятьсяразличнымипоставщиками.Внекоторыхслучаяходинэлементданныхможетбытьсвязансцелой совокупностью других элементов данных. Например, одно изделие может поставляться несколькими поставщиками, каждый из которых установил свою ценунаэтоизделие.ЭлементданныхЦЕНАнеможетбытьассоциировантолькосэлементомИЗДЕЛИЕилитолькосэлементомПОСТАВЩИК,адолженбытьсвязанодновременносдвумя.Информациятакогорода,т.е.данные,ассоциированныессовокупностьюэлементов,называютиногда даннымипересечения.  Некоторыеструктурысодержатциклы. Циклом считается ситуация, в которой предшественник узла является в то же время его последователем. Отношения «исходный — порожденный» образуют при этом замкнутый контур. Например, завод выпускает различную продукцию. Некоторые изделия производятся на других заводах-субподрядчиках. С одним контрактомможетбытьсвязанопроизводствонесколькихизделий.Представлениеэтихотношенийиобразуетцикл. Иногдаэлементысвязанысдругимиэлементамитогожетипа.Такаяситуацияназывается петлей. Нарис.3.13 приведены две достаточно распространенные ситуации, где могут использоваться петли. В массиве служащих специфицированы связи, существующие между некоторыми служащими. В базу данных списка материалов введено дополнительное усложнение: некоторые узлы сами состоят из узлов. Разделение сетевых структур на простые и  ,что сложные структуры требуют более сложных методов  физического  представления. Это не всегда является недостатком, поскольку сложную сетевую структуру можно (а в большинстве случаев и следует) преобразовать к простому виду.