Логотип
Юнионпедия
Связь
Доступно в Google Play
Новый! Скачать Юнионпедия на вашем Android™ устройстве!
Установить
Более быстрый доступ, чем браузер!
 

Бинарная диаграмма решений

Индекс Бинарная диаграмма решений

Бинарная диаграмма решений (БДР) или программа с ветвлением является формой представления булевой функции f(x_1, x_2,..., x_n) от n переменных в виде направленного ациклического графа, состоящего из внутренних узлов решений (помеченных x_i), каждый из которых имеет по два потомка, и двух терминальных узлов (помеченных 0 и 1), каждый из которых соответствует одному из двух значений булевой функции.

15 отношения: Класс NP, Кнут, Дональд Эрвин, Путь (теория графов), Направленный ациклический граф, Система автоматизированного проектирования, Таблица истинности, Университет Карнеги — Меллона, Факторизация, Формальная верификация, Мультиплексор (электроника), Изоморфизм графов, Задача выполнимости булевых формул, Булева функция, Булева алгебра, Дерево (структура данных).

Класс NP

В теории алгоритмов классом NP (от non-deterministic polynomial) называют множество проблем разрешимости, решение которых возможно проверить на машине Тьюринга за время, не превосходящее полинома от размера входных данных, при наличии некоторых дополнительных сведений (так называемого сертификата решения).

Новый!!: Бинарная диаграмма решений и Класс NP · Узнать больше »

Кнут, Дональд Эрвин

Дональд Эрвин Кнут (Donald Ervin Knuth, МФА: /kəˈnuːθ/; род. 10 января 1938 года, Милуоки, штат Висконсин) — американский учёный в области информатики, эмерит-профессор Стэнфордского университета и нескольких других университетов в разных странах, в том числе Санкт-Петербургского, преподаватель и идеолог программирования, автор 19 монографий (в том числе ряда классических книг по программированию) и более 160 статей, разработчик нескольких известных программных технологий.

Новый!!: Бинарная диаграмма решений и Кнут, Дональд Эрвин · Узнать больше »

Путь (теория графов)

Граф-путь с 6 вершинами Путь в графе — последовательность вершин, в которой каждая вершина соединена со следующей ребром.

Новый!!: Бинарная диаграмма решений и Путь (теория графов) · Узнать больше »

Направленный ациклический граф

250px Направленный ациклический граф (ориентированный ациклический граф, DAG от directed acyclic graph) — орграф, в котором отсутствуют направленные циклы, но могут быть «параллельные» пути, выходящие из одного узла и разными путями приходящие в конечный узел.

Новый!!: Бинарная диаграмма решений и Направленный ациклический граф · Узнать больше »

Система автоматизированного проектирования

Система автоматизированного проектирования — автоматизированная система, реализующая информационную технологию выполнения функций проектирования, представляет собой организационно-техническую систему, предназначенную для автоматизации процесса проектирования, состоящую из персонала и комплекса технических, программных и других средств автоматизации его деятельности.

Новый!!: Бинарная диаграмма решений и Система автоматизированного проектирования · Узнать больше »

Таблица истинности

Таблица истинности — это таблица, описывающая логическую функцию.

Новый!!: Бинарная диаграмма решений и Таблица истинности · Узнать больше »

Университет Карнеги — Меллона

Университет Карнеги — Меллон (Carnegie Mellon University, CMU) — частный университет и исследовательский центр, расположенный в Питтсбурге, (штат Пенсильвания, США).

Новый!!: Бинарная диаграмма решений и Университет Карнеги — Меллона · Узнать больше »

Факторизация

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

Новый!!: Бинарная диаграмма решений и Факторизация · Узнать больше »

Формальная верификация

Формальная верификация или формальное доказательство — формальное доказательство соответствия или несоответствия формального предмета верификации его формальному описанию.

Новый!!: Бинарная диаграмма решений и Формальная верификация · Узнать больше »

Мультиплексор (электроника)

Схема мультиплексора 2-к-1. Mультипле́ксор — устройство, имеющее несколько сигнальных входов, один или более управляющих входов и один выход.

Новый!!: Бинарная диаграмма решений и Мультиплексор (электроника) · Узнать больше »

Изоморфизм графов

В теории графов изоморфизмом графов G.

Новый!!: Бинарная диаграмма решений и Изоморфизм графов · Узнать больше »

Задача выполнимости булевых формул

Зада́ча выполни́мости бу́левых фо́рмул (SAT или ВЫП) — важная для теории вычислительной сложности алгоритмическая задача.

Новый!!: Бинарная диаграмма решений и Задача выполнимости булевых формул · Узнать больше »

Булева функция

Бу́лева фу́нкция (или логи́ческая функция, или функция а́лгебры ло́гики) от n аргументов — в дискретной математике — отображение Bn → B, где B.

Новый!!: Бинарная диаграмма решений и Булева функция · Узнать больше »

Булева алгебра

Булевой алгеброй называется непустое множество A с двумя бинарными операциями \land (аналог конъюнкции), \lor (аналог дизъюнкции), одной унарной операцией \lnot (аналог отрицания) и двумя выделенными элементами: 0 (или Ложь) и 1 (или Истина) такими, что для любых a, b и c из множества A верны следующие аксиомы: \begin & a+(b+c).

Новый!!: Бинарная диаграмма решений и Булева алгебра · Узнать больше »

Дерево (структура данных)

Простой пример дерева Дерево — одна из наиболее широко распространённых структур данных в информатике, эмулирующая древовидную структуру в виде набора связанных узлов.

Новый!!: Бинарная диаграмма решений и Дерево (структура данных) · Узнать больше »

Перенаправления здесь:

Binary decision diagram, Branching program, Ordered binary decision diagram, Reduced ordered binary decision diagram, Сокращенная упорядоченная бинарная диаграмма решений, Упорядоченная бинарная диаграмма решений.

ИсходящиеВходящий
Привет! Мы на Facebook сейчас! »