«ГАК информатика (ответы)» - Шпаргалка

Содержание

Дискретная математика

1. Основные комбинаторные объекты и числа.

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

3. Рекуррентные соотношения. Способы решения рекуррентных соотношений. Числа Фибоначчи.

4. Основные понятия теории графов. Изоморфизм графов. Связные графы. Деревья. Представление графа на ЭВМ (динамические структуры данных, стеки, очереди, двоичные деревья)

Архитектура компьютера

5. Архитектура ЭВМ. Классическая архитектура ЭВМ и принцип Фон Неймана.

6. Язык программирования Ассемблер. Базовые элементы. Основные операции над регистрами.

7. Аппаратные и программные прерывания. Адресное пространство и смещение.

8. Аппаратные и программные средства обработки информации.

Информационные технологии в математике

9. Информационная технология. Этапы развития и перспективы информационных технологий.

10. Информационная емкость. Формула информационной емкости.

11. Перспективы развития информационных технологий.

12. Математический пакет Maple — среда для решения математических задач. Основы работы, команды. Построение графиков функций. Решение дифференциальных уравнений.

Исслед операций

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

14. Условный экстремум: Функция Лагранжа, метод множителей Лагранжа.

15. Симплекс-метод. Преобразование симплекс  таблиц на языке Pascal.

16. Двойственные задачи: симметричные и несимметричные. Двойственность в линейном программировании.

Компьютерное моделирование

17. Моделирование как метод познания. Понятие «модель». Виды моделирования в естественных и технических науках. Компьютерная модель. Информационные модели. Объекты и их связи. Основные структуры в информационном моделировании. Примеры информационных моделей. Поля, методы и свойства. Абстрактные, виртуальные, динамические и перегружаемые методы.

18. Графическое моделирование. Основы трехмерной графики. Преобразования координат. Перенос и повороты в трехмерном пространстве.

19. Понятие математического моделирования. Этапы и цели математического моделирования. Различные подходы к классификации математических моделей. Модели с сосредоточенными и распределенными параметрами. Дескриптивные, оптимизационные, многокритериальные, игровые модели.

20. Имитационные модели и системы. Этапы построения имитационной модели. Анализ и оценка адекватности имитационной модели. Примеры имитационных моделей.

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

Компьютерные сети

22. Понятие о компьютерных сетях. Типы сетей. Топология. Классификация.

23. Архитектура компьютерных сетей. Семиуровневая модель OSI. Модель TCP/IP.

24. Адресация в сети Internet. Понятие сокета, как способ программного доступа к сетевым функциям.

25. Технология «Клиент-Сервер». Одноранговые и распределенные сети.

26. Протоколы и службы Internet.

Математическая логика, теория алгоритмов, теоретические основы информатики

27. Алгебра высказываний как модель алгебры Буля, ее аксиоматическое задание. Принцип двойственности и теорема двойственности.

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

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

30. Неформальное понятие алгоритма. Общие свойства алгоритмов. Графические средства для описания алгоритмов.

31. Формальное определение понятия алгоритма в виде машин Тьюринга. Вычисления на машинах Тьюринга. Тезис Тьюринга - Черча. Проблема самоприменимости.

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

33. Система счисления с произвольным основанием. Перевод из одной системы счисления в другую. Операции над числами в системах счисления с произвольным основанием.

34. Основные понятия теории кодирования. Оптимальный код Шеннона-Фано.

Основы искусственного интеллекта.

35. Основы теории экспертных систем. Общая характеристика ЭС. Виды ЭС и типы решаемых задач. Структура и режимы использования ЭС. Перспективы развития экспертных систем.

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

37. Основы нейросетевых технологий. Нейроклетка - разработка формальной модели. Классы нейронных сетей. Методы обучения.

38. Базовые конструкции языка программирования Pascal.

39. Основные типы данных языка программирования Pascal и их производные.

40. Описание процедур и функции языка программирования Pascal.

41. Delphi – cреда разработки приложений для ОС Windows. Компонентная разработка приложений в среде Delphi.

42. Разработка мультимедийных приложений в среде Delphi.

Численные методы

43. Метод простой итерации при решении уравнения с одной переменной.

44. Метод простой итерации для СЛАУ.

45. Интерполяционный многочлен Лагранжа. Вывод, оценка погрешности.

46. Метод трапеций для численного нахождения определенного интеграла: вывод формулы, оценка погрешности, геометрический смысл.

47. Методы численного интегрирования дифференциальных уравнений.

48. Метод наименьших квадратов.

Элементы абстрактной и компьютерной алгебры.

49. Теория множеств: множества и операции над множествами, основные проблемы.

50. Алгебра и алгебраические системы.

51. Группы (подгруппы), поля и кольца.

Введение

1. Основы теории экспертных систем. Общая характеристика ЭС. Виды ЭС и типы решаемых задач. Структура и режимы использования ЭС. Перспективы развития экспертных систем.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Выдержка из текста работы

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

Проблема разрешения

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

Например, для системы 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).

Заключение

4. Основные понятия теории графов. Изоморфизм графов. Связные графы. Деревья. Представление графа на ЭВМ (динамические структуры данных, стеки, очереди, двоичные деревья)

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

Теория графов может рассматриваться как раздел дискретной математики (точнее - теории множеств), и формальное определение графа таково: задано конечное множество 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 — первый вошёл — первым вышел).

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

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

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

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

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

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

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

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

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

Примечания

Есть приложения