Open Classic Hard Problems — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| Строка 2: | Строка 2: | ||
showtotal=yes | showtotal=yes | ||
namespace=Main | namespace=Main | ||
| − | limit= | + | limit=5 |
order=creation desc | order=creation desc | ||
output=template | output=template | ||
Версия 22:13, 5 апреля 2023
Всего страниц найдено: 5.
Задача «Minimum Local Register Allocation»©
- Набор инструкций, формирующих некий блок без переходов,
- N доступных регистров,
- стоимость чтения и записи в регистр i.
- Порядок резервирования регистров для этой последовательности инструкций.
- Минимизировать полную стоимость чтения-записи в регистры.
Задача в лаб22 (рид-онли просмотр)
Задача «Minimum Register Sufficiency»©
- Направленный ациклический граф G=(V,A)
- Найти вычисление на G, которое использует k регистров, т.е.
- порядок v1, …, vn на вершинах V
- последовательность S0, …, Sn подмножеств V, удовлетворяющих
- S0 — пустое
- Sn — содержит все вершины с нулевой входящей степенью в G
- 1 ≤ i ≤ n, , , и содержит все вершины u, для которых
- Минимизировать число регистров,т.е. k.
Задача в лаб22 (рид-онли просмотр)
- Задача в базе NP-полных задач Вигго Кана
- Код задачи в книге «ГД» → «PO1»
Задача «Minimum Permutation Group Base»©
- Группа G перестановок из n символов.
- Найти базу для G, т.е. последовательность точек b1, …, bk, такой, что единственный элемент в G фиксирующий все эти bi это идентичное преобразование.
- Минимизировать размер базы, т.е. k.
Задача в лаб22 (рид-онли просмотр)
Задача «Minimum Locally Testable Automaton Order»©
- Локально тестируемый язык L, т.е. некий язык L, такой, что положительное целое j, такое что входит или нет строка x в этот язык зависит от …
- префикса и суффикса x длины j-1,
- набора подстрок x длины j.
- Найти порядок j, т.е. положительное целое j, «свидетель» локальной тестируемости L.
- Минимизировать значение порядка, т.е. j.
Задача в лаб22 (рид-онли просмотр)
Задача «Shortest Computation»©
- Недетерминированная машина Тьюринга M, двоичная входная строка x.
- Найти недерминированную строку-догадку c, произведенную машиной M на входе x.
- Минимизировать длину кратчайшей из этих строк,т.е. .
Задача в лаб22 (рид-онли просмотр)