«ГАК информатика (ответы)»

Такие задачи имеют определенную специфику, которая заключается в следующем:

- нечеткой постановке или неполноте исходных данных задачи;

- отсутствии точного алгоритма решения задачи;

- огромного числа возможных исходов, подлежащих анализу;

- невозможности формализации задача (задача не может быть определена в числовой форме или цели задачи не могут быть выражены в терминах точно определенной целевой функции);

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

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

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

Цель замены эксперта мотивируется следующим образом:

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

Во-вторых, знания одного эксперта \"закрыты\" для других

В-третьих, эксперт не в состоянии быстро накапливать и усваивать

знания в силу физиологических ограничений.

В-четвертых, использование человека-эксперта невозможно в системах реального времени.

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

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

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

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

Характеристики экспертной системы

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

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

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

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

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

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

Например, для системы m уравнений с n неизвестными существует несколько способов решения: метод Гаусса, метод Крамера. Значит, для системы m линейных уравнений с n неизвестными проблема разрешения разрешима.

Если для серии М однотипных задач единый метод решения (алгоритм) существует, то говорят, что для этой серии М проблема разрешения решена и разрешима.

Если же доказано, что единого метода решения задач из серии М не существует, то говорят, что для данной серии задач проблема разрешения решена и неразрешима.

Если для серии М однотипных задач единый метод решения не найден, и не доказано, что такого метода не существует, то говорят, что для данной серии М задач проблема разрешения не решена (открыта).

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

Точное определение проблемы разрешения можно будет дать только после строгого математического определения понятия алгоритм. Такое определение существует, оно появилось в 30-ых годах XX-ого века.

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

Появление новой отрасли в математике - математической логики и теории алгоритмов сделало возможным решать такие задачи, т. е. доказывать, что они не разрешимы в рамках данной аксиоматической теории.

Проблема разрешения для алгебры высказываний.

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

В самом деле, если φ тождественно истинная формула, то φ тождественно ложная, т. е. невыполнима.

Если же φ не тождественно истинная формула, то φ - выполнима.

Известно, что проблема разрешения для алгебры высказываний разрешима. Существуют два способа ее разрешения:

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

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

Алгоритм проблемы выполнимости:

1) Берем формулу φ.

2) Приводим φ к К.Н.Ф. и узнаем, является ли φ тождественно истинной или нет.

3) Если формула φ тождественно истинна, то φ невыполнима, если же φ не тождественно истинна, то φ выполнима.

2. Высказывательные формы (предикаты). Способы их задания. Логические операции над предикатами.

Часто мы сталкиваемся с такими выражениями, которые имеют форму высказываний, но содержат предметные переменные некоторых множеств. Например, “x-простое число”. Такие выражения легко получить из любого высказывания, заменив в нём обозначения предметов, предметными переменными множеств. Если в таком выражении предметные переменные заменить каким-либо элементом (конкретным) множества, то снова получится высказывание.

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

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

Пример: Наполеон – француз. Пусть М - множество всех земных людей. x M. Слово Наполеон заменим предметной переменной x из М и получим “x-француз”. Это высказывание при одних элементах из М будет истинным, а при других – ложным. “Сократ – француз” – ложно. “Де Бальзак - француз” – истинно.

Другой пример: 2 – простое число. М – множество натуральных чисел. x M. “x – простое число”. В обоих этих случаях мы получим функции, определённые на некотором множестве М и со значениями И. или Л. Такие функции называются функциями-высказываниями или предикатами.

Определение 1

n- местным предикатом, определённым на некотором множестве М называется выражение, которое всякому упорядоченному набору элементов из М ставит в соответствие И или Л.

Обозначается: P (x1,…, xn),

А (x1,…, xn).

Если зафиксировать все переменные: x1=a1,…, xn=an, то предикат обращается в высказывание: P (а1,…, аn), А (а1,…, аn).

Пример:

1). Высказывание 3 < 2. Заменим 3 переменной х, получим x < 2, которое в области действительных чисел истинно тогда и только тогда, когда число меньше двух. Получим одноместный предикат x < 2. Заменим 2 переменной y:

x < y – двуместный предикат.

2). x2 + y2 = 2*x*y – истинно только при x = y

Множество M назовём полем, и его элементы будем обозначать последними буквами латинского алфавита: x, y, z, … ,x1, y1 … . Эти символы неопределенных элементов и называются предметными переменными.

Начальные буквы латинского алфавита a, b, c, … , a1, b1… будут обозначать конкретные элементы из М и называется индивидуальными предметами.

A, B, C, … , U, V – обозначают элементарные высказывания. Выражения F(x), F(x, y), A(x, y , u), P (x1,…, xn) будут обозначать предикаты. Но F(a), F(a, b), A(a, a , b), P (a1,…, an) уже будут элементарными высказываниями. Они же иногда называются значением соответствующего предиката.

Определение 2

Два n- местных предиката P1 (x1,…, xn), P2 (x1,…, xn) называются равносильными, если их значения на данном поле М совпадают.

Пример: x > 2 и предикат x – 2 > 0 равносильны.

Определение 3

Предикат P1 (x1,…, xn) называется:

а) тождественно истинным, если его значение для любого набора из М истина;

б) тождественно ложным, если при любых наборах (x1,…, xn) из М она принимает значение ложь.

Пример: x2 + 2 < 0.

в) выполнимым, если существует по меньшей мере один набор (x10,…, xn0) из М, то Р(x10,…, xn0) = И.

Имеют место очевидные теоремы:

Теорема 1

Любые два n- местные тождественно истинные предикаты, определённые на одном и том же множестве, и любые два n- местные тождественно ложные предикаты, определённые на одном и том же множестве равносильны между собой.

Обратная теорема

Любой предикат равносильный тождественно истинному предикату будет тождественно истинным. Любой предикат равносильный тождественно ложному предикату - тождественно ложным.

Определение 4

Множеством истинности предиката P(x1,…, xn), определённого на некотором множестве М, называется совокупность из М, для которых значение Р есть истина и обозначается:

Ep ={(x1,…, xn) | P (x1,…, xn)}.

Например, пусть N – натуральные числа, тогда

{x | x < 10} = {1, 2, …, 9}

{ | x + y = 3} = {(0,3), (1,2),(2,1),(3,0)}.

Теорема 2

Множества истинности предикатов Р1(n) и Р2(n), определённых на множестве М, совпадают тогда и только тогда, когда Р1(n) Р2(n).

Р1(n) Р2(n) = Ep1 = Ep2

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

Операции над предикатами

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

Отрицанием n – местного предиката | P (x1,…, xn), определённого на М называется новый предикат, определенный на том же множестве М, который истинен тогда и только тогда, когда Р ложен.

Обозначается: (P(x1,…, xn)) или P(x1,…, xn).

Аналогично определяется конъюнкция и дизъюнкция

Теорема 3

а) Отрицание предиката Р тождественно истинно тогда и только тогда, когда предикат Р тождественно ложен.

б) Конъюнкция двух предикатов тождественно истинна тогда и только тогда, когда тождественно истинны оба предиката.

в) Дизъюнкция двух предикатов тождественно ложна тогда и только тогда, когда тождественно ложны оба предиката.

В логике предикатов имеются ещё две новые операции: операции квантификации.

1. Квантор общности.

Определение 5

Пусть А(х) одноместный предикат, определённый на М. Высказывание: “для всех х А(х) истинно” и обозначается через ( х)А(х) и считается полученным из предиката А(х) операцией связывания квантором общности.

( х)А(х) истинно тогда и только тогда, когда предикат А(х) истинен для всех элементов поля М, т. е. А(х) тождественно истинный предикат. В противном случае оно ложно.

( х)А(х) читается “для всех х А(х).”

Пример: пусть М – множество действительных чисел, х = х, то

( х)(х = х) есть истинное высказывание. Р1(х): x > 2, то ( х)(x > 2) – ложное высказывание.

Р2(х): “x – есть простое число”. ( х) Р2(х) - ложное высказывание, т. к. получили что любое действительное число есть простое.

Если М = {a1, …, an} – конечное множество, то ( х) Р(х) эквивалентно высказыванию: P(a1) P(a2) … P(an), т. е. в этом случае квантор общности является обобщением операции конъюнкции.

Для многоместных предикатов P (x1,…, xn) операция определяется также, но при P (x1,a1,…,an), т. е. при фиксированных х2, х3, …, хn.

Определение 6

Если применить квантор всеобщности по переменной x1 к n – местному предикату P (x1,…, xn), то получится (n – 1) – местный предикат: Р1(x2,…, xn) = ( х1)P(x1,…, xn), который уже не зависит от x1, а зависит только от x2,…, xn. Причём, при фиксированных х20, …, хn0 P1(х20, …, хn0) истинен тогда и только тогда, когда истинен предикат Р при х20, …, хn0 и при всех x1 из М.

Примеры: М – множество действительных чисел.

1) x > y – двуместный предикат Р(x, y). ( х)(x > y) = Р1(y) – предикат, зависящий уже только от y. При любом у Р1(y) – ложно.

2) ( х)( у)[(x > y) (y > x)]. Предикат (x > y) (y > x) - двуместный.

Но после двукратного применения операции квантора общности, он стал высказыванием, причём тождественно ложным, т. к. может быть и x = y.

После n – раз применения операции квантора общности, n - местный предикат становится высказыванием.

Пример: ( z)(x2 + y2 = 0) - двуместный предикат, получен применением квантора к переменной z, от которого предикат (x2 + y2 = 0) не зависит.

2. Квантор существования.

Определение 7

Пусть А(х) одноместный определённый на М. Высказывание “существует х, что А(х) истинно” обозначается ( х) А(х) и считается полученным из А(х) операцией связывания квантором существования.

( х) А(х) истинно тогда и только тогда, когда существует по крайней мере один элемент из М х0, для которого А(х) истинен.

Если же для всех элементов из М предикат А(х) ложен, то и ( х) А(х) – ложное высказывание.

Пример:

М – множество действительных чисел, Р(x, y) - двуместный предикат,

(x > y). ( х)(x > y) – истинно; ( х)(x2 + y2 < 0) – одноместный предикат

Р1(y), который при любых значениях у принимает значение ложь.

Если М = {a1, …, an} – конечное множество, то выражение ( х) Р(х) равносильно следующему высказыванию: P(a1) P(a2) … P(an).

Определение 8

Если применить квантор существования ( ) по переменной x1 к n – местному (n > 1) предикату P (x1,…, xn), то получится (n – 1) – местный предикат: Р1(x2,…, xn) = ( х)P(x1,…, xn), который уже не зависит от переменной x1, а зависит только от x2,…, xn. Причём, при фиксированном наборе х20, …, хn0 высказывание P1(х20, …, хn0) истинно тогда и только тогда, когда одноместный предикат Р(x1, х20, …, хn0) истинен по крайней мере при одном х1 из М.

Уместно говорить о выполнимых формулах на М и на любом поле М.

Примеры:

1) ( х)(x2 + 1 = y2) одноместный предикат Р(y). Р(1) – истина, т. к. существует 0, что 0 + 1 = 1; Р(2) – ложь, т. к. при любом х x2 + 1 4, если х С.

2) ( х)( у)(x > y) – истинное высказывание во множестве действительных чисел, но если М – множество натуральные чисел, то

( х)( у)(x > y) - ложно

В этих примерах предикатные символы “=”, “<” истолкованы как

в арифметике.

Теорема 4

Предикат ( х1)P(x1,…, xn) = Р1(x2,…, xn),т. е. (n – 1) – местный предикат: Р1 полученный из Р применением квантора общности тождественно истинен тогда и только тогда, когда тождественно истинен предикат P(x1,…, xn).

Теорема 5

(n – 1) – местный предикат, полученный из n – местного предиката P(x1,…, xn) операцией связывания квантора существования тождественно ложен тогда и только тогда, когда тождественно ложен предикат P(x1,…, xn).

Теория графов может рассматриваться как раздел дискретной математики (точнее - теории множеств), и формальное определение графа таково: задано конечное множество X , состоящее из n элементов (X = {1, 2,., n}), называемых вершинами графа, и подмножество V декартова произведения X хХ, то есть VcX 2 , называемое множеством дуг, тогда ориентированным графом G называется совокупность ( X , V ) (неориентированным графом называется совокупность множества X и множества неупорядоченных пар элементов, каждый из которых принадлежит множеству X ). Дугу между вершинами i и j , i , j еХ, будем обозначать ( i , j ). Число дуг графа будем обозначать m ( V = ( v 1, v 2,., v m )).

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

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

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

Путем называется последовательность дуг (в ориентированном графе), такая, что конец одной дуги является началом другой дуги. Простой путь - путь, в котором ни одна дуга не встречается дважды. Элементарный путь - путь, в котором ни одна вершина не встречается дважды. Контур - путь, у которого конечная вер шина совпадает с начальной вершиной. Длиной пути (контура) называется число дуг пути (или сумма длин его дуг, если последние заданы).

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

симметрическим. Если из следует, что то соответствующий граф называется антисимметрическим.

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

Если любые две вершины графа можно соединить цепью, то граф называется связным. Если граф не является связным, то его можно разбить на связные подграфы, называемые компонентами. Связностью графа называется минимальное число ребер, после удаления которых граф становится несвязным. Для ориентированных графов, если любые две вершины графа можно соединить путем, то граф называется сильно связным. Известно [7], что: связность графа не может быть больше, чем [2m /n], где [x] - целая часть числа x; существуют графы с n вершинами и m ребрами, имеющие связность [2m /n]; в сильно связном графе через любые две вершины проходит контур.

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

В неориентированном графе степенью вершины i называется число di инцидентных ей ребер. Очевидно, dj < n - l , i eX . Граф, степени всех вершин которого равны n - 1, называется полным. Граф, все степени вершин которого равны, называется однородным.

Вершина, для которой не существует инцидентных ей ребер ( di = 0) называется изолированной. Вершина, для которой существует только одно инцидентное ей ребро (di = 1) называется вися чей.

Связный граф является эйлеровым тогда и только тогда, когда степени всех его вершин четны (теорема Эйлера). Обозначим щ — число вершин, имеющих степень k, k = 0, 1, 2,. . Известно [7, 15],

что:

Для ориентированных графов для каждой вершины можно ввести два числа - полустепень исхода [число выходящих из нее вершин) и полустепень захода d [ (число входящих в нее

для эйлерова графа имеет место: d * = d i ,

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

Определим матрицу смежности графа как квадратную матрицу n х п, элемент a i j которой равен единице, если и нулю, если Для неориентированного графа матрица смежности всегда симметрическая.

Определим матрицу инциденций для ребер графа как прямо угольную матрицу n х m, элемент Гц которой равен единице, если

вершина i инцидентна ребру j , и нулю в противном случае,

Аналогично определяется матрица инциденций для дуг графа - как прямоугольная матрицу m хп, элемент Гц которой равен плюс единице, если дуга Uj исходит из вершины i , минус единице, если дуга Ц заходит в вершину i , и нулю в остальных

случаях,

Деревом называется связный граф без простых циклов, имеющий не менее двух вершин. Для дерева m = n -1, а число висячих

вершин равно . Легко показать, что в дереве

любые две вершины связаны единственной цепью.

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

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

Пример 1 (изоморфизм). Покажем, что следующие два графа изоморфны.

Действительно, отображение a ® e, b ® f, c ® g, d ® h, являющееся изоморфизмом легко представить как модификацию первого графа, передвигающую вершину d в центр рисунка.

Представление графов на ЭВМ.

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

По определению, элементы извлекаются из стека в порядке, обратном их добавлению в эту структуру, т.Е. Действует принцип \"последний пришёл — первый ушёл\".

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

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

Выделим типовые операции над стеком и его элементами:

добавление элемента в стек;

удаление элемента из стека;

проверка, пуст ли стек;

просмотр элемента в вершине стека без удаления;

очистка стека.

Очередь — это информационная структура, в которой для добавления элементов доступен только один конец, называемый хвостом, а для удаления — другой, называемый головой. В англоязычной литературе для обозначения очередей довольно часто используется аббревиатура FIFO (first-in-first-out — первый вошёл — первым вышел).

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

Выделим типовые операции над очередями:

• добавление элемента в очередь (помещение в хвост);

• удаление элемента из очереди (удаление из головы);

• проверка, пуста ли очередь;

• очистка очереди.

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

В двоичном (бинарном) дереве каждый узел может быть связан не более чем двумя другими узлами. Рекурсивно двоичное дерево определяется так: двоичное дерево бывает либо пустым (не содержит ни одного узла), либо содержит узел, называемый корнем, а также два независимых поддерева — левое поддерево и правое поддерево.

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