Комбинаторные задачи в логическом проектировании дискретных устройств
Место издания: Минск
ISBN: 978-985-08-2725-8
Страниц: 177
Артикул: 93758
Краткая аннотация книги "Комбинаторные задачи в логическом проектировании дискретных устройств"
В монографии рассматриваются оптимизационные комбинаторные задачи дискретной математики, возникающие при логическом проектировании дискретных устройств и систем. Представлены методы решения таких задач, как поиск кратчайшего покрытия множества, раскраска графа и др. Описаны классические методы минимизации и декомпозиции булевых функций в терминах булевых и троичных векторов и матриц. Изложены методы проектирования дискретных устройств, использующие классические модели конечного автомата и параллельного автомата. Адресуется специалистам в области автоматизации проектирования дискретных устройств, а также студентам, магистрантам и аспирантам, специализирующимся в данном направлении.
Содержание книги "Комбинаторные задачи в логическом проектировании дискретных устройств"
Предисловие
Глава 1. Комбинаторные задачи и методы комбинаторного поиска
1.1. Особенности комбинаторных задач
1.2. Задача о кратчайшем покрытии
1.3. Основные понятия теории графов
1.4. Доминирующие множества графа
1.5. Независимые множества графа
1.6. Раскраска графа
1.7. Разрез графа
1.8. Полные двудольные подграфы
Глава 2. Булевы функции
2.1. Способы задания булевой функции
2.2. Элементарные булевы функции и алгебраические формы
2.3. Интерпретации булевой алгебры
2.4. Выполнение операций над булевыми функциями с помощью характеристических множеств
2.5. Нормальные формы
2.6. Троичные векторы и матрицы
2.7. Ортогонализация дизъюнктивной нормальной формы
2.8. Графическое представление булева пространства. Карта Карно
2.9. Функциональная полнота
2.10. Минимизация дизъюнктивной нормальной формы
2.11. Минимизация не полностью определенных булевых функций
Глава 3. Системы булевых функций
3.1. Представления системы булевых функций
3.2. Минимизация системы ДНФ
Глава 4. Декомпозиция булевых функций
4.1. Двухблочная разделительная декомпозиция
4.2. Неразделительная декомпозиция
4.3. Декомпозиция систем булевых функций
4.4. Многоблочная параллельная декомпозиция системы не полностью определенных булевых функций
Глава 5. Конечные автоматы
5.1. Типы автоматов
5.2. Минимизация полных автоматов
5.3. Минимизация частичных автоматов
Глава 6. Кодирование состояний синхронного автомата
6.1. Задача кодирования состояний
6.2. Метод «желательных соседств»
6.3. Итеративный метод
6.4. Энергосберегающее кодирование состояний
Глава 7. Кодирование состояний асинхронного автомата
7.1. Явление состязаний элементов памяти
7.2. Условие отсутствия опасных состязаний
7.3. Минимизация длины кода
7.4. Энергосберегающее кодирование состояний
Глава 8. Параллельные автоматы
8.1. Описание модели
8.2. Установление параллельности частичных состояний
8.3. Кодирование частичных состояний
Заключение
Список использованных источников
Предметный указатель
Все отзывы о книге Комбинаторные задачи в логическом проектировании дискретных устройств
Отрывок из книги Комбинаторные задачи в логическом проектировании дискретных устройств
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, что противоречит определению множеств...
С книгой "Комбинаторные задачи в логическом проектировании дискретных устройств" читают
Посмотреть
Посмотреть
Посмотреть
Посмотреть
Посмотреть
Посмотреть
Посмотреть
Посмотреть
Бестселлеры нон-фикшн
Посмотреть
Посмотреть
Посмотреть
Посмотреть
Посмотреть
Посмотреть
Посмотреть
Посмотреть
Посмотреть
Посмотреть
Посмотреть
Посмотреть
Посмотреть
Новинки книги нон-фикшн
Посмотреть
Посмотреть
Посмотреть
Посмотреть
Посмотреть
Посмотреть
Посмотреть
Посмотреть
Посмотреть
Посмотреть
Посмотреть
Посмотреть
Посмотреть
и мы свяжемся с вами в течение 15 минут
за оставленную заявку