Комбинаторные задачи в логическом проектировании дискретных устройств
В монографии рассматриваются оптимизационные комбинаторные задачи дискретной математики, возникающие при логическом проектировании дискретных устройств и систем. Представлены методы решения таких задач, как поиск кратчайшего покрытия множества, раскраска графа и др. Описаны классические методы минимизации и декомпозиции булевых функций в терминах булевых и троичных векторов и матриц. Изложены методы проектирования дискретных устройств, использующие классические модели конечного автомата и параллельного автомата.Адресуется специалистам в области автоматизации проектирования дискретных устройств, а также студентам, магистрантам и аспирантам, специализирующимся в данном направлении.
Содержание
Содержание книги "Комбинаторные задачи в логическом проектировании дискретных устройств "
Отрывок из книги
19Примером задачи нахождения наиболь его независимого множества яв-ляется другая задача о ферзях, в которой надо расставить на ахматной доске наиболь ее число ферзей так, чтобы ни один из них не находился под ударом другого. Наиболь ее независимое множество графа, представляю его ах-матную доску, как определено вы е, покажет, на какие клетки надо поставить ферзей. Наиболь ее число ферзей, расставленных при указанном условии, которое в данном случае равно восьми, есть число независимости данного графа.Рассмотрим один из способов нахождения в графе всех максимальных не-зависимых множеств.Пусть G заданный граф с произвольно упорядоченным множе-ством вер ин V v1, v2, , vn. Рассмотрим последовательность подгра-фов G1, G2, , Gn, порожденных подмножествами V1, V2, , Vn, где Vi v1, v2, , vi i 1, 2, , n. Пусть 12 , , ,iiiiikSSSS совокупность всех максимальных независимых множеств графа Gi. Преобразуем Si следую им образом. ля каждого Sji j 1, 2, , ki получим множество 1 1 .сли в Si найдется такой элемент ,ilS что ,ilSS то ilS в Si заменяем на S. сли найдется такой элемент ilS в множестве i, что ,ilSS то Si не изменяем. В остальных случаях S добавляем в множество Si в качестве нового элемента.Нетрудно убедиться, что в результате таких преобразований множество Si превра ается в Si1 совокупность всех максимальных независимых мно-жеств графа Gi1. ействительно, все 12, ,...,iiiikSSS являются независимыми множествами для Gi1. Множество S является также независимым. Все по-гло аемые множества удаляются, так что остаются только максимальные. То, что Si1 содержит все максимальные независимые множества графа Gi1, легко доказывается от противного. Пусть S максимальное независимое множе-ство графа Gi1, не полученное в результате описанных преобразований. Но тогда S vi1 является максимальным независимым множеством графа Gi, которого нет в Si, что противоречит определению множеств...
Внимание!
При обнаружении неточностей или ошибок в описании книги "Комбинаторные задачи в логическом проектировании дискретных устройств (автор Юрий Поттосин)", просим Вас отправить сообщение на почту help@directmedia.ru. Благодарим!
и мы свяжемся с вами в течение 15 минут
за оставленную заявку