| dbo:abstract
|
- In der theoretischen Informatik bezeichnet der Problemkern (engl. problemkernel) den algorithmisch „schwierig“ entscheidbaren Teil einer Instanz eines NP-Schweren Problems. Viele Instanzen NP-schwerer Probleme enthalten Teilprobleme, die leicht entscheidbar sind. Zum Beispiel in vielen Instanzen von Problemen, bei denen eine Teilmenge S von einer Menge M gewählt werden soll, haben Elemente x von M gewisse Eigenschaften, durch die man effizient entscheiden kann, dass x in S sein muss oder nicht in S sein kann. Die Methode, solche Elemente zu suchen und aus der Instanz zu entfernen, bezeichnet man als Problemkern-Reduktion (engl. kernelization). Die Elemente, die solche Eigenschaften nicht haben und nach Problemkern-Reduktionen übrig sind, bilden den Problemkern der Instanz. (de)
- In computer science, a kernelization is a technique for designing efficient algorithms that achieve their efficiency by a preprocessing stage in which inputs to the algorithm are replaced by a smaller input, called a "kernel". The result of solving the problem on the kernel should either be the same as on the original input, or it should be easy to transform the output on the kernel to the desired output for the original problem. Kernelization is often achieved by applying a set of reduction rules that cut away parts of the instance that are easy to handle. In parameterized complexity theory, it is often possible to prove that a kernel with guaranteed bounds on the size of a kernel (as a function of some parameter associated to the problem) can be found in polynomial time. When this is possible, it results in a fixed-parameter tractable algorithm whose running time is the sum of the (polynomial time) kernelization step and the (non-polynomial but bounded by the parameter) time to solve the kernel. Indeed, every problem that can be solved by a fixed-parameter tractable algorithm can be solved by a kernelization algorithm of this type. (en)
- En informatique théorique, et notamment en théorie de la complexité, la kernelisation ou réduction au noyau est une formalisation d'un prétraitement efficace d'une instance d'un problème NP-difficile qui consiste à l'alléger et à le simplifier. La réduction se place dans le cadre de la complexité paramétrée. La réduction est possible quand une instance d'un problème possède des parties qui sont facilement décidables et détectables, et que l'on peut enlever sans modifier le problème de départ. Les données qui subsistent après ces réductions forment le noyau de l'instance. (fr)
- Параметрическая редукция — это техника для разработки эффективных алгоритмов, которые достигают своей эффективности путём препроцессорного шага, в котором вход алгоритма заменяется на меньший вход, называемый «ядром». Результат решения задачи на ядре должен быть либо тем же самым, что и при исходных данных, либо выход решения для ядра должен легко преобразовываться в желаемый выход исходной задачи. Параметрическая редукция часто достигается путём применения набора правил редукции, которые отсекают часть конкретной задачи, с которой легко справиться. В часто можно доказать, что ядро с гарантированными границами, зависящими от размера ядра (как функции некоторых параметров, связанных с задачей), могут быть найдены за полиномиальное время. Если это возможно, результатом будет алгоритм, время работы которого является суммой шага (полиномиального времени) параметрической редукции и (неполиномиального, но ограниченного параметром) времени для решения ядра. Более того, любая задача, которую можно решить фиксированно-параметрически разрешимым алгоритмом, может быть решена алгоритмом параметрической редукции этого типа. (ru)
|
| rdfs:comment
|
- En informatique théorique, et notamment en théorie de la complexité, la kernelisation ou réduction au noyau est une formalisation d'un prétraitement efficace d'une instance d'un problème NP-difficile qui consiste à l'alléger et à le simplifier. La réduction se place dans le cadre de la complexité paramétrée. La réduction est possible quand une instance d'un problème possède des parties qui sont facilement décidables et détectables, et que l'on peut enlever sans modifier le problème de départ. Les données qui subsistent après ces réductions forment le noyau de l'instance. (fr)
- In der theoretischen Informatik bezeichnet der Problemkern (engl. problemkernel) den algorithmisch „schwierig“ entscheidbaren Teil einer Instanz eines NP-Schweren Problems. Viele Instanzen NP-schwerer Probleme enthalten Teilprobleme, die leicht entscheidbar sind. Zum Beispiel in vielen Instanzen von Problemen, bei denen eine Teilmenge S von einer Menge M gewählt werden soll, haben Elemente x von M gewisse Eigenschaften, durch die man effizient entscheiden kann, dass x in S sein muss oder nicht in S sein kann. (de)
- In computer science, a kernelization is a technique for designing efficient algorithms that achieve their efficiency by a preprocessing stage in which inputs to the algorithm are replaced by a smaller input, called a "kernel". The result of solving the problem on the kernel should either be the same as on the original input, or it should be easy to transform the output on the kernel to the desired output for the original problem. (en)
- Параметрическая редукция — это техника для разработки эффективных алгоритмов, которые достигают своей эффективности путём препроцессорного шага, в котором вход алгоритма заменяется на меньший вход, называемый «ядром». Результат решения задачи на ядре должен быть либо тем же самым, что и при исходных данных, либо выход решения для ядра должен легко преобразовываться в желаемый выход исходной задачи. (ru)
|
