Рассмотрены вопросы алгоритмизации комбинаторно-оптимизационных задач структурного синтеза на графах. Большое внимание уделено формализации таких задач и методам их решения, основанным на идее отсечения, ветвей и границ, поиска в глубину, в ширину, двоичной свертки. Описаны основные этапы построения алгоритмов и подходы к оценке их точности и сложности; точные и приближенные алгоритмы решения таких задач, как построение минимального остовного дерева, замкнутого цикла минимальной длины, кратчайшего маршрута, разрезания гиперграфа схемы и др. Выполнена оценка вычислительной и емкостной сложности большинства алгоритмов. Содержание учебника соответствует курсу лекций, который автор читает в МГТУ им. Н.Э.Баумана. Для студентов вузов, обучающихся по специальностям, связанным с информатикой. Будет полезна инженерам, работающим в данной области.
Rassmotreny voprosy algoritmizatsii kombinatorno-optimizatsionnykh zadach strukturnogo sinteza na grafakh. Bolshoe vnimanie udeleno formalizatsii takikh zadach i metodam ikh reshenija, osnovannym na idee otsechenija, vetvej i granits, poiska v glubinu, v shirinu, dvoichnoj svertki. Opisany osnovnye etapy postroenija algoritmov i podkhody k otsenke ikh tochnosti i slozhnosti; tochnye i priblizhennye algoritmy reshenija takikh zadach, kak postroenie minimalnogo ostovnogo dereva, zamknutogo tsikla minimalnoj dliny, kratchajshego marshruta, razrezanija gipergrafa skhemy i dr. Vypolnena otsenka vychislitelnoj i emkostnoj slozhnosti bolshinstva algoritmov. Soderzhanie uchebnika sootvetstvuet kursu lektsij, kotoryj avtor chitaet v MGTU im. N.E.Baumana. Dlja studentov vuzov, obuchajuschikhsja po spetsialnostjam, svjazannym s informatikoj. Budet polezna inzheneram, rabotajuschim v dannoj oblasti.
