Vliv uspořádání proměnných na algoritmické učení pomocí OBDD

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985807%3A_____%2F05%3A00405663" target="_blank" >RIV/67985807:_____/05:00405663 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

On the Influence of the Variable Ordering for Algorithmic Learning using OBDDs

Popis výsledku v původním jazyce

OBDDs with a fixed variable ordering are used successfully as data structure in experiments with learning heuristics based on examples. In this paper, it is shown that, for some functions, it is necessary to develop an algorithm to learn also a good OBDDvariable ordering. There are functions with the following properties. They have OBDDs of linear size for optimal variable orderings. But for all but a small fraction of all variable orderings one needs large size to represent a list of randomly chosen examples. These properties are shown for simple functions like the multiplexer and the inner product.

Název v anglickém jazyce

On the Influence of the Variable Ordering for Algorithmic Learning using OBDDs

Popis výsledku anglicky

OBDDs with a fixed variable ordering are used successfully as data structure in experiments with learning heuristics based on examples. In this paper, it is shown that, for some functions, it is necessary to develop an algorithm to learn also a good OBDDvariable ordering. There are functions with the following properties. They have OBDDs of linear size for optimal variable orderings. But for all but a small fraction of all variable orderings one needs large size to represent a list of randomly chosen examples. These properties are shown for simple functions like the multiplexer and the inner product.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

<a href="/cs/project/GA201%2F98%2F0717" target="_blank" >GA201/98/0717: Výpočetní modely a složitost výpočtů</a><br>

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2005

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Information and Computation and Information and Control

ISSN

0890-5401

e-ISSN

—

Svazek periodika

201

Číslo periodika v rámci svazku

-

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

18

Strana od-do

160-177

Kód UT WoS článku

—

EID výsledku v databázi Scopus

—