Содержание
49 отношения: BWA (выравнивание биологических последовательностей), Кубический граф, Классификация экономической литературы JEL, Кликовая ширина, Компромисс времени и памяти, Псевдоузел, Путевая ширина, Предсказание вторичной структуры РНК, Параллелизм на уровне команд, Полный перебор, Перекрытие (значения), Обратная индукция, Оптимальное управление, Алгоритм Смита — Ватермана, Алгоритм Флойда — Уоршелла, Алгоритм Беллмана — Форда, Алгоритм Витерби, Алгоритм Ли, Незацепленное вложение графа, Некорневое двоичное дерево, Расписание, Разделяй и властвуй (информатика), Роботы BEAM, Техника Бренды Бейкер, Теорема о планарном разбиении, Частичное k-дерево, Эффективность алгоритма, Математическая экономика, Марковский момент, Мемоизация, Задача раскроя, Задача разбиения множества чисел, Задача о сумме подмножеств, Задача о ранце, Задача о джипе, Задача о порядке перемножения матриц, Берцекас, Димитрис, Выравнивание последовательностей, Временная сложность алгоритма, Внешнепланарный граф, Граф Халина, Глубина дерева (теория графов), Древесная ширина (теория графов), Древесная декомпозиция, ДП, Дистанционно-наследуемый граф, Доминирующее множество, Декомпозиция графа на ветви, 1-планарный граф.
BWA (выравнивание биологических последовательностей)
BWA (Burrows-Wheeler Aligner) — программный пакет для картирования коротких прочтений на большие референсные геномы (такие как, например, геном человека), написанный китайским биоинформатиком Хенг Ли и англичанином Ричардом Дурбиным.
Посмотреть Динамическое программирование и BWA (выравнивание биологических последовательностей)
Кубический граф
Граф Петерсена является кубическим. Полный двудольный граф K_3,3 является примером бикубического графа Кубический граф — граф, в котором все вершины имеют степень три.
Посмотреть Динамическое программирование и Кубический граф
Классификация экономической литературы JEL
Научные статьи в области экономики принято категоризировать в соответствии с классификацией Американской экономической ассоциации, также называемой классификацией JEL по аббревиатуре издаваемого ассоциацией журнала.
Посмотреть Динамическое программирование и Классификация экономической литературы JEL
Кликовая ширина
дистанционно-наследуемуего графа кликовой ширины 3 путём несвязного объединения, переименования вершин и объединения меток. Метки вершин показаны цветом. В теории графов кликовая ширина графа G — это параметр, который описывает структурную сложность графа.
Посмотреть Динамическое программирование и Кликовая ширина
Компромисс времени и памяти
Компромисс времени и памяти (Space-time trade-off, «выбор оптимального соотношения „место-время“» (space-time trade-off), или, иначе, «выбор оптимального соотношения „время-память“» (time-memory trade-off)) — компромиссный подход к решению ряда задач в информатике, при котором используется обратное соотношение требуемого объёма памяти и скорости выполнения программы: время вычислений может быть увеличено за счёт уменьшения используемой памяти или, наоборот, снижено за счёт увеличения объёма используемой памяти.
Посмотреть Динамическое программирование и Компромисс времени и памяти
Псевдоузел
Псевдоу́зел — элемент вторичной структуры нуклеиновых кислот (в основном РНК), состоящий из двух шпилек, в которых половина стебля одной шпильки располагается между двумя половинами стебля другой шпильки.
Посмотреть Динамическое программирование и Псевдоузел
Путевая ширина
В теории графов путевая декомпозиция графа G — это, неформально, представление графа G в виде «утолщённого» пути, а путевая ширина графа G — это число, измеряющее, насколько граф G был утолщён.
Посмотреть Динамическое программирование и Путевая ширина
Предсказание вторичной структуры РНК
Предсказа́ние втори́чной структу́ры РНК — метод определения вторичной структуры нуклеиновой кислоты по последовательности её нуклеотидов.
Посмотреть Динамическое программирование и Предсказание вторичной структуры РНК
Параллелизм на уровне команд
Параллелизм на уровне команд (Instruction-level parallelism — ILP) — является мерой того, какое множество операций в компьютерной программе может выполняться одновременно.
Посмотреть Динамическое программирование и Параллелизм на уровне команд
Полный перебор
Полный перебор (или метод «грубой силы», brute force) — метод решения математических задач.
Посмотреть Динамическое программирование и Полный перебор
Перекрытие (значения)
Перекры́тие.
Посмотреть Динамическое программирование и Перекрытие (значения)
Обратная индукция
Равновесие, совершенное по подыграм Обратная индукция — метод нахождения оптимальной последовательности действий.
Посмотреть Динамическое программирование и Обратная индукция
Оптимальное управление
Оптимальное управление — это задача проектирования системы, обеспечивающей для заданного объекта управления или процесса закон управления или управляющую последовательность воздействий, обеспечивающих максимум или минимум заданной совокупности критериев качества системы Самойленко В.
Посмотреть Динамическое программирование и Оптимальное управление
Алгоритм Смита — Ватермана
Алгоритм Смита — Ватермана предназначен для получения локального выравнивания последовательностей, то есть для выявления сходных участков двух нуклеотидных или белковых последовательностей.
Посмотреть Динамическое программирование и Алгоритм Смита — Ватермана
Алгоритм Флойда — Уоршелла
Алгоритм Флойда — Уоршелла — динамический алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного ориентированного графа.
Посмотреть Динамическое программирование и Алгоритм Флойда — Уоршелла
Алгоритм Беллмана — Форда
Алгоритм Беллмана — Форда — алгоритм поиска кратчайшего пути во взвешенном графе.
Посмотреть Динамическое программирование и Алгоритм Беллмана — Форда
Алгоритм Витерби
Алгоритм Витерби — алгоритм поиска наиболее подходящего списка состояний (называемого путём Витерби), который в контексте цепей Маркова получает наиболее вероятную последовательность произошедших событий.
Посмотреть Динамическое программирование и Алгоритм Витерби
Алгоритм Ли
Алгори́тм волново́й трассиро́вки (волновой алгоритм, алгоритм Ли) — алгоритм поиска пути, алгоритм поиска кратчайшего пути на планарном графе.
Посмотреть Динамическое программирование и Алгоритм Ли
Незацепленное вложение графа
Незацепленное вложение графа — вложение неориентированного графа в евклидово пространство, при котором никакие два цикла графа не имеют ненулевой коэффициент зацепления.
Посмотреть Динамическое программирование и Незацепленное вложение графа
Некорневое двоичное дерево
актинобактерий. Некорневое двоичное дерево — это некорневое дерево, в котором каждая вершина имеет либо одного, либо трёх соседей.
Посмотреть Динамическое программирование и Некорневое двоичное дерево
Расписание
Расписа́ние — вид календаря (то есть, упорядоченность по времени), для которого указана информация о предстоящих (планируемых или потом произошедших) событиях.
Посмотреть Динамическое программирование и Расписание
Разделяй и властвуй (информатика)
Разделяй и властвуй (divide and conquer) в информатике — важная парадигма разработки алгоритмов, заключающаяся в рекурсивном разбиении решаемой задачи на две или более подзадачи того же типа, но меньшего размера, и комбинировании их решений для получения ответа к исходной задаче; разбиения выполняются до тех пор, пока все подзадачи не окажутся элементарными.
Посмотреть Динамическое программирование и Разделяй и властвуй (информатика)
Роботы BEAM
Роботы BEAM — Слово BEAM является аббревиатурой от Biology, Electronics, Aesthetics, Mechanics.Это термин, обозначающий принцип построения роботов, использующий простые аналоговые цепи (например, компараторы) вместо микропроцессоров с целью достичь необычно простого (в сравнении с традиционными передвижными роботами) дизайна, который жертвует гибкостью ради надёжности и эффективности выполнения определённого задания.
Посмотреть Динамическое программирование и Роботы BEAM
Техника Бренды Бейкер
Техника Бренды Бейкер — это метод построения приближенных схем полиномиального времени (ПСПВ, PTAS) для задач на планарных графах.
Посмотреть Динамическое программирование и Техника Бренды Бейкер
Теорема о планарном разбиении
Теорема о планарном разбиении — это форма изопериметрического неравенства для планарных графов, которое утверждает, что любой планарный граф может быть разбит на более мелкие части путём удаления небольшого числа вершин.
Посмотреть Динамическое программирование и Теорема о планарном разбиении
Частичное k-дерево
Частичное k-дерево — это вид графа, либо подграф, либо граф с древесной шириной, не превосходящей k. Много комбинаторных NP-трудных задач на графах решаются за полиномиальное время, если ограничиться частичными k-деревьями c некоторым ограниченным значением k.
Посмотреть Динамическое программирование и Частичное k-дерево
Эффективность алгоритма
Эффективность алгоритма — это свойство алгоритма, которое связано с вычислительными ресурсами, используемыми алгоритмом.
Посмотреть Динамическое программирование и Эффективность алгоритма
Математическая экономика
accessdate.
Посмотреть Динамическое программирование и Математическая экономика
Марковский момент
В математике теория момента остановки или марковский момент времени связана с проблемой выбора времени, чтобы принять определённое действие, для того чтобы максимизировать ожидаемое вознаграждение или минимизировать ожидаемые затраты.
Посмотреть Динамическое программирование и Марковский момент
Мемоизация
Мемоизация (запоминание, от англ. memoization в программировании) — сохранение результатов выполнения функций для предотвращения повторных вычислений.
Посмотреть Динамическое программирование и Мемоизация
Задача раскроя
Задача раскроя — это NP-полная задача оптимизации, по существу, сводимая к задаче о ранце.
Посмотреть Динамическое программирование и Задача раскроя
Задача разбиения множества чисел
Задача разбиения множества чисел — это задача определения, можно ли данное мультимножество S положительных целых чисел разбить на два подмножества S1 и S2, таких, что сумма чисел из S1 равна сумме чисел из S2.
Посмотреть Динамическое программирование и Задача разбиения множества чисел
Задача о сумме подмножеств
Задача о сумме подмножеств — это важная задача в теории сложности алгоритмов и криптографии.
Посмотреть Динамическое программирование и Задача о сумме подмножеств
Задача о ранце
Пример задачи о ранце: необходимо уложить коробки в ранец вместимостью 15 кг так, чтобы стоимость уложенных коробок была максимальной Задача о ранце (или задача о рюкзаке) — NP-полная задача комбинаторной оптимизации.
Посмотреть Динамическое программирование и Задача о ранце
Задача о джипе
Задача о джипе (Jeep problem, desert crossing problem, exploration problem) — математическая задача, целью которой является максимизация пути, который можно преодолеть на джипе с полным баком топлива в труднопреодолимых условиях, к примеру, в пустыне.
Посмотреть Динамическое программирование и Задача о джипе
Задача о порядке перемножения матриц
Задача о порядке перемножения матриц — классическая задача динамического программирования, в которой дана последовательность матриц A_1, A_2, \dots, A_n и требуется минимизировать количество скалярных операций для вычисления их произведения.
Посмотреть Динамическое программирование и Задача о порядке перемножения матриц
Берцекас, Димитрис
Дими́трис Пантели́с Берцека́с (Δημήτρης Παντελής Μπερτσεκάς, Dimitri Panteli Bertsekas; род. 1942, Афины, Аттика, Греция) — греческий и американский учёный в области прикладной математики и информатики, профессор кафедры электротехники и информатики факультета инженерного дела Массачусетского технологического института (MIT).
Посмотреть Динамическое программирование и Берцекас, Димитрис
Выравнивание последовательностей
Выравнивание последовательностей — биоинформатический метод, основанный на размещении двух или более последовательностей мономеров ДНК, РНК или белков друг под другом таким образом, чтобы легко увидеть сходные участки в этих последовательностях.
Посмотреть Динамическое программирование и Выравнивание последовательностей
Временная сложность алгоритма
В информатике временна́я сложность алгоритма определяет время работы, используемое алгоритмом, как функции от длины строки, представляющей входные данные.
Посмотреть Динамическое программирование и Временная сложность алгоритма
Внешнепланарный граф
Максимальный внешнепланарный граф и его 3-раскраска. Полный граф K4 является наименьшим планарным графом, не являющимся внешнепланарным. В теории графов outerplanar graph — это граф, допускающий планарную диаграмму, в которой все вершины принадлежат внешней грани.
Посмотреть Динамическое программирование и Внешнепланарный граф
Граф Халина
Граф Халина. В теории графов графом Халина называется некоторый вид планарного графа, который строится из дерева, имеющего по меньшей мере 4 вершины, ни одна из которых не имеет в точности двух соседей.
Посмотреть Динамическое программирование и Граф Халина
Глубина дерева (теория графов)
В теории графов глубина дерева связного неориентированного графа G — это числовой инвариант G, минимальная высота дерева Тремо для суперграфа графа G. Этот инвариант и близкие понятия встречаются под различными именами в литературе, включая число ранжирования вершин, упорядоченное хроматическое число и минимальная высота исключения дерева.
Посмотреть Динамическое программирование и Глубина дерева (теория графов)
Древесная ширина (теория графов)
В теории графов древесная ширина неориентированного графа — это число, ассоциированное с графом.
Посмотреть Динамическое программирование и Древесная ширина (теория графов)
Древесная декомпозиция
Граф с восемью вершинами и его древесная декомпозиция в дерево с шестью узлами. Каждое ребро графа соединяет две вершины, перечисленные вместе в некотором узле дерева, и каждая вершина графа указана в узлах непрерывных поддеревьев дерева.
Посмотреть Динамическое программирование и Древесная декомпозиция
ДП
ДП, DP — аббревиатура.
Посмотреть Динамическое программирование и ДП
Дистанционно-наследуемый граф
В теории графов дистанционно-наследуемый граф (или вполне сепарабельный граф) — это граф, в котором расстояния в любом связном порождённом подграфе те же самые, что и в исходном графе.
Посмотреть Динамическое программирование и Дистанционно-наследуемый граф
Доминирующее множество
Доминирующее множество (красные вершины). В теории графов доминирующее множество для графа G.
Посмотреть Динамическое программирование и Доминирующее множество
Декомпозиция графа на ветви
решётки. Показано e-разделение. Разделение, декомпозиция, и сам граф имеют ширину три. В теории графов декомпозиция на ветви неориентированного графа G — это иерархическая кластеризация рёбер графа G, представленная некорневым бинарным деревом T с рёбрами из G в качестве листьев.
Посмотреть Динамическое программирование и Декомпозиция графа на ветви
1-планарный граф
графа Хивуда — шесть рёбер имеют единичные пересечения, а остальные 15 рёбер не пересекаются. В топологической теории графов 1-планарный граф — это граф, который может быть нарисован в евклидовой плоскости таким образом, что каждое ребро имеет максимум одно пересечение с единственным другим ребром.
Посмотреть Динамическое программирование и 1-планарный граф