Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000

УДК 519.45 Г 62 ББК 22.145 (075.8) Издание осащестелено яри содебстеии 000 гФирма вИэдательстео А СТе ОГЛАВЛЕНИЕ 5 7 10 13 13 18 22 29 36 Табл. 163, Ил. 313. Бибвиогр. 46 нева. 44 55 61 75 83 86 93 94 94 98 102 108 116 123 127 132 142 145 150 156 157 157 163 170 174 183 194 ТП-99-П 1БВН 5-02-015238-2 208 216 Г о р б а т о в В. А. Фундаментальные основы дискретной математики. Информационная мвтемнжию.

— Мл Наука. Физматлит, 2000.— 544 с.— 18В1ч 5-02-015238-2. В учебнике излагаются основы многасортных мноиеста, мвтематвческай ло. гиви, теория графов и могрвфоа, теории формальных грамматик и автоматов, прнкдаднай теории елгоритмоа и хвректерязепиовнога анакваа, которые в сова. купности образуют основы дискоетяай математики, предстввляюшне собой методически аавимасвязпый курс 'Компьютерна-июрармевиониая математика".

Для студентов технических университетов, академий и институтов, обучаю. шихся по специальности "Информатика и вычислительная техника", е такие научных работников и нниенеров, работающих в области ииформатяки и вычислительной техники. Редеввенты: квфеара "Информационные технологии" Московского гасударственного института электроники и математики; доктор фивнгиьметеьгатпческих науа, профессор В. Н. Рещео1нинае © В.А.Горбатов, 1999 © Наука.

Фпвматлит, оформление, 1999 К читателю Предисловие Введение Гл а в а 1. Основы миагасортных множеств 1.1. Множество, функция, операция. Способы задания.... 1.2. Понятие алгебры. Фундаментальные алгебры 1.3. Бинарные отношения, способы их задания и свойства . 1.4. Решетка 1.5, Модель. Алгебра отношений................. 1.6.

Аксиоматика теории множеств, минимизация представления множеств 1.7. Алгоритм — двусортное множество. Системы счисления 1.8. Компьютерные арифметики 1.9. Нечеткие подмножества 1.10. Метрические пространства.................. 1.11. Залечи и упражнения 1.12. Комментарии . Глава 2. Математическая апина 2.1. Логика высказываний............ 2.2.

Разложение Шеннона. Декомпозиция булевых функций 2.3. Минимизация булевых функций в классе ДНФ 2.4. Полнота. Построение сулерлозиций булевых функций 2.5. Дифференцирование булевых функций 2.6. Разложение булевой функции в заданной точке пространства . 3 2.7. Йсчисление высказываний.................. 2.8. Коиечнозначные логики 2.9. Исчисление предикатов 2.10. Теория трасс 2.11.

Задачи и упражнения . 2.12. Комментарии . Главе 3. Теория графов и маграфню 3.1. Взвешенный граф и его матричное задание 3.2. Связность и сильная связность графе 3.3. Цикломатикаи коцикломатика ............... 3.4. Дифференцирование графов и мографов 3.5. Устойчивость, покрытия, пвросочетания 3.6. Вложение' графов 3.7. Раскраска вершин и ребер графа. Характеризация реберности . 3 3.8. Квазиполные модели, их структура и свойства...... Оглавление 239 255 257 258 258 265 271 279 292 К ЧИТАТЕЛЮ 305 310 342 361 370 373 385 387 388 388 404 414 423 429 000 454 473 478 494 518 526 530 532 Список литературы Предметный указатель 533 536 3.9.

Характеризвцня частичного упорядочения мографа... 227 3.10. Логарифмические оценки хроматического числа. Решение проблемы четырех красок................ 3.11. Задачи и упражнения 3.12. Комментарии Г л а в а 4. Теория формалывых грамматик ж автоматов 4.1. Формальные грамматики .

4.2. Основные зтапы проектирования автоматов 4.3. Алгоритмический зтап проектирования........, 4.4. Абстрактное проектирование автоматов ......... 4.5. Кодирование внутренних состояний........... 3 4.6. Построение выходных функций н функций возбуждения памяти автомата 4.7.

Синтез логических структур в топологических базисах 4.8. Синтез логических структур в несвязных базисах 4.9. Синтез логических структур в связных базисах.... 4.10. Синтез нейронных структур,............... 4.11. Моделирование автоматных систем сетями Петри... 4.12. Задачи и упражнения . з 4.13. Комментарии Г л а в а 5. Прикладная теория алгоритмов з 5.1. Принципы характеризационного анализа. Построение комбинвторных алгоритмов З5.2. Характеризация и методы оптимального размещения данных в памяти ЭВМ 3 5.3. Характеризвция выходной связности логических структур 5.4. Теоретико-структурная минимизация булевых функций 5.5. Харвктеризация разложения графа переходов в частичное декартово произведение З 5.6. Семантическое ослабление функциональной связности памяти автомата 15.7.

Решение проблемы повторной функциональной декомпозиции в булевой логике .. 3 5.8. Синтез функциональной декомпозиции в 5-значной логике ., 3 5.9, Синтез функциональной декомпозиции заданной размерности 5.10. Семантическое проектирование нейронных сетей.... 5.11. Оценка динамики логических структур 5.12. Семантическое проектирование скоростной транспортной сети большого города з 5.13. Техническая диагностика сильносвязных объектов...

5.14. Задачи и упражнения . 5.15. Комментарии . Г б В сл в Афанасьевич академик многих академий, ор атов яче а 1 м числе Международной академии информатизации 1 втом ч РАЕН, Российской академии медика-технических наук, р п офессар, доктор физико-математических наук, доктор технических ивук, родился 19 апрелн 1939 года в Москве. С отличием закончил Московский энергетический институт, в тридцать три года защитил до р кторскую диссертацию, женат, имеет дочь и сына. Много лет возглавляет кафедру "Вычислительные машины Москов гасударственного горного университета.

В.А. Горбатов нвляется авторам научного открытия — теории характеризвционнаго анализа. Это открытие, сделанное в середине 60-х годов, явилось основой научной школы В.А. Горбатова по информационной математике, идеи которой палучилн развитие как у нас в стране, так и за рубежом. В рамках этого науч- К читателю Аквдемик МАИ, РАЕН, профессор МГУ, доктор физико-мвтемвтическик нвук С.Я.

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

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

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

Горбатова отмечены рядом международных и российских премий и медалей, в том числе Международной премией фон Неймана, медалью Лауреата Нобелевской премии П.Л. Капицы эа научное открытие, медалью Петра 1 "За заслуги в деле возрождения науки и экономики России", Георгиевским Крестом 1 степени "За заслуги в деле развития науки и экономики России", именной медалью ООН, Международной премией н Золотой медалью ООН за большой вклад в области информатизации мирового сообщества, медалью вЛауреат премии имени Александра Чижевского". В.А. Горбатов уделяет большое внимание научным кадрам: им подготовлено свыше ста кандидатов и докторов наук в области информатики, вычислительной техники и экономики.

Основные научные результаты профессора В.А. Горбатова опубликованы более чем в 400 научных трудах. В.А. Горбатав— автор 35 книг, в том числе 18 монографий по дискретной математике, информатике и вычислительной технике, ряд которых переведен на английский, испанский, немецкий, китайский, болгарский, польский языки. ПРЕДИСЛОВИЕ Общество лл века— лл1 — общество информационное (постиндув кото ом одно нз й главных проблем является пров и П и оды.

Составляющей этой гармоблема гармонии Человека и рироды. о кт ра общества.' нии является мошна р ная инфо мационная инфраструктура язи с наличием у него Вопрос об ис ключительности Человека в связ с Д был поставлен в конце 50-х разума после р Капе ника и эрвина следование "искусственгодов нашего столет ия когда началось нс ешения задач переменого интел еллектае когда центр тяжести решен р й ( ислительной) математики к стился от зад ач канечнамерной вычис . Е адачи конечномерной иск етных структурах. сли з ы с и облемой создания ракетно.ядерного математики были связаны с пр лема с иск етной математики — с пр лемами у правлешита, то задачи дискретно ах.

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

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

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