В.Б. Алексеев, С.А. Ложкин - Элементы теории графов, схем и автоматов (DJVU) (1055625)
Текст из файла
Московский государственный университет имени М. В. Ломоносова Факультет вычислительной математики и кибернетики В. Б. Алексеев, С. А. Ложкин ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ, СХЕМ И АВТОМАТОВ Учебное пособие но курсам "Введение в дискретную математику" и 'Основы кибернетики' Москва 2000 УДК 519.95 ББК 22.176 А 47 Алексеев В.Б., Ложкин С.А. "Элементы теории графов, схем и автоматов" (учебное пособие для студентов) М.: Издательский отдел ф-та ВМиК МГУ (лицензия ЛР Х 040777 от 23.07.1996), 2000 г. 58 с.
В программу курсов "Введение в дискретную магемагику" (1 курс) и "Основы кибернетики" (3--4 курс), которые являются обязательными для студентов, обучанпцихся по специальности 01.02 ----- прикладная математика, входят различные вопросы теории графов, схем и автоматов. В основных учебных пособиях по данным курсам некоторые из этих вопросов отсутствуют. Методическая разработка призвана восполнить указанный пробел. В ее первой части рассматриваются некоторые свойства деревьев и планарных графов. Во второй части разработки описываются различные типы схем и усганавливаются связи между ними„изучается сложность реализации этими схемами некоторых функций.
В третьей части рассматриваются автоматы и их реализация схемами, а также эксперименты с автомагами. Рецензенты: Лупанов О.Б., чл.-корр.РАН, профессор Сапоженко А.А., д.ф.-м.н., профессор Печатается по решению Ученого Совета факультета вычислительной матемагики и кибернетики МГУ им.М.В.Ломоносова. 18 В 1~ 5-89407-087-2 © Издагельский отдел факуль вета вычислительной магематики и кибернетики МГУ им.М.В.Ломоносова,2000 Введение ОГЛАВЛКНИК Часть 1. Графы Ц1 Основные понятия теории графов ~2 Деревья ~3 Планарные графы 'Часть 2.
Схемы ~4 Формулы и схемы из функциональных элементов. Задача синтеза и простейшие способы ее решения ~5 Реализация некоторых 'управляющих" систем функций алгебры логики в классе СФЭ ~6 Реализация некоторых "арифметических" систем ФАЛ в классе СФЭ ~7 Метод Шеннона для синтеза СФЭ. Верхняя и нижняя оценки функции Шеннона и сложности некоторых ФАЛ Часть 3. Автоматы ~8 Автомагные функции. Их реализация схемами из функциональных элементов и элементов задержки ~9 Эксперименты с автомагами.
Теорема Мура ввкдкник При изучении дискретных систем, в частности, систем преобра.- зования информации, требуется строить математические модели, описывающие структуру или функционирование таких систем. В учебном пособии рассматриваются некоторые из таких моделей. Одним из наиболее важных понятий, относящихся к структуре дискретных систем, является понятие графа.
Это понятие, описывающее структуру связей между отдельными частями системы, в силу своей общности используется во многих магемагических моделях. 1 1)афы Очень часто использую'1'ся в п1)илОжениях. Поскольку они возникают как модель при изучении многих обьектов. Например, структура молекулы является графом. в котором вершинами служ п атомы, а ребрами --- валентные связи. Блок-схема алгоритма представляет собой орграф, в котором вершинами являются отдельные операгоры, а дуги указывают переходы между ними. Другие примеры графов: узлы и соединения в электрической цепи, схема дорог, множество предприятий с указанием двухсторонних связей между ними, группа людей с указанием их психологической совместимости, структура управления с указанием об ьектов и их подчиненности друг ,1ц)угу и т.д.
Тематика исследований, связанных с графами, очень широка. Это и исследование структуры и свойств графов, изучение специальных классов графов„построение быстрых алгоритмов для решения различных задач на графах и т. д. Здесь мы рассмотрим только некоторые простые вопросы, относящиеся к свойствам произвольных графов, а также рассмотрим два важных класса графов --- деревья и планарные графы, ---- и изучим их свойства.
В настоящее время получили широкое распространение сложные преооразователи информации, которые составлены из простейших преобразователей (элементов) и в которых движутся сигналы нескольких типов, преобразуемые или передаваемые отдельными элементами в соответствии с определенными законами. В теории управляющих систем рассматриваются различные теоретико-графовые модели таких преобразователей, называемые схемами. Еаждая схема характеризуется структурой графом определенного вида и функционированием законом преобразования входных наборов или их последовательностей в выходные наборы или их последовательности. Функционирование схемы однозначно определяется ее структурой и функционированием элементов базиса набора простейших преобра- зователей, из которых построена схема. При изучении схем решаются две основные задачи: задача анализа и задача синтеза.
Задача анализа состоит в нахождении функционирования данной схемы, а задача синтеза в построении схемы, имеющей (реализующей) заданное функционирование. Каждая из этих задач может рассматриваться либо как индивидуальная задача, и тогда ее решением является конкретное функционирование (схема), либо как массовая задача, и тогда ее решением должен быть алгоритм нахождения функционирования (схемы). Задача синтеза имеет, как правило, множество решений, из которых выбирают решение, оптимальное по какому-либо критерию. Чаще всего в качестве такого критерия выступает сложность схемы, понимаемая как сумма сложностей составляющих ее элементов.
В Я4 — 7 мы мы рассмотрим, как решается задача синтеза для схем из функциональных элементов -- для преобразователей без памяти, реализующих некоторые системы булевых функций. В Я8--9 рассматриваются автоматы-преобразователи с памятью, работающие по тактам в дискретном времени. Кроме задач анализа и синтеза авгоматов, которые рассматриваются в ~8, изучаются также эксперименты с автоматами Я9), что тесно связано с тестированием вычислительных устройсгв. Часть 1.
Графы ~ 1. Основные понятия теории графов Определение. Графом с(' «в широком понимании) называется любая пара (1', Е), где 1г = (! )„(2,...~ — множа(тно элементов любой природы, а Е = (е),е~,...) — семейство пар элементов нз Г. причем допускаются пары вида.(с;.(:,;) и одинаковые пары. Если нары В !' рассма!'рина)от('я как н(уиОрядОченнь(е, тО ! "ра(1) назынаетс(! нео1)не)()г)((1)анании. если как у(ю1)ядОч('нные„')О г1гаф называе)ся о1)()ент:щ)оаанным (оргрс)фон). Эг(((мен"!'ы множес !'Ва 1' назывгнО'гся с(е1)нхиналш гре)фа, и пары из Š— его ребрами; н орграфе онн нж)ывакптя ор)(ентиронаннык(и ребрами или дугами.
Говорят. что ребро е = (((,(:) н неориентиронанном графе соединяет нершины и и с, а н ориентированном графе дуга е = (((„()) идет из вер)нины а н вершину г. Графы можно условно изобража!'ь следуюв(им образом. Вершины будем изображагь точками, а каждое ребро «дугу) (((, с1) б Е— линией, соединяюц(ей точки„соотнетствукяцие (; и в . Если «!';.
( )— ду(а, то на эгой Линии будем указЫна(Ь с)1геЛку О! с! к «р На рис. 1.1 приведены неор((енгирован)п)й и Ориенгированный графы 6 = «1',Е), где 1 = (1,2„3„4),„Е = (е(,е2,(:в,с4.с;,,св„е() и е! —— «1.2), е2 — — (-,3), в = (3,4), е4 = (4,2), ен — — (1,4), .б — — (4,2), с'; = (1, 1).
Рис. 1.1. Пара вида «(„,()!) называется г)етлс(и, н вершин(. (ч. Если и ра (в;, !);) вс)ре-)ае)ся н Е Оолее ~Д~~~~ раза, .)О говорят ~((о «с- е ) краг))нос ребро. В графах на рис. 1.1 «4, 2) — кр)тгное ребро, е-, — петля. Замечание. Часто в литературе под графом понимается граф без петель и кратных ребер. В этом случае граф с кратными ребрами называют мультиграфом, граф с кратными ребрами и петлями исевдографом. Графы очень часто используются в приложениях, поскольку они возникают как модель при изучении многих об:ьектов. Наи1эимер, струкгура молекулы является графом, в котором вершинами являются атомы, а ребра,ми — — валентные связи. Блок-схема алгоритма представляет собой орграф, в кото1эом ве1эшинами являются отдельные операгоры, а дуги указывают переходы между ними.
Другие примеры графов: элементы и соединения в электрллческой цепи, схема перекрестков и дорог, множество предприятий с указанием двухсторонних связей между ними. группа людей с указанием их психологической совместимости, структура управления с указанием обьектов и их подчиненности друг другу и т. д. Определение. Говорят. что вершины и; и и смежны в графе С = (1;Е), есллл в Е входит пара (в;,и.) элли (с|э,и;). Говорят, что ребро (дуга) (х;, о ) инллидентно вершинам и; и в . Определение. Степенью вершины в неориентированном графе называется число ребер, инцидентных данной вершине, при этом петли учитываются дважды. Вершины степени О называют изоллэрованными,.
Характеристики
Тип файла DJVU
Этот формат был создан для хранения отсканированных страниц книг в большом количестве. DJVU отлично справился с поставленной задачей, но увеличение места на всех устройствах позволили использовать вместо этого формата всё тот же PDF, хоть PDF занимает заметно больше места.
Даже здесь на студизбе мы конвертируем все файлы DJVU в PDF, чтобы Вам не пришлось думать о том, какой программой открыть ту или иную книгу.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
