Registro completo de metadatos
| Campo DC | Valor | Lengua/Idioma |
|---|---|---|
| dc.provenance | Facultad de Ciencias Exactas y Naturales de la UBA | - |
| dc.contributor | Heintz, Joos | - |
| dc.contributor | Matera, Guillermo | - |
| dc.creator | Matera, Guillermo | - |
| dc.date.accessioned | 2018-05-04T22:07:43Z | - |
| dc.date.accessioned | 2018-05-28T16:34:44Z | - |
| dc.date.available | 2018-05-04T22:07:43Z | - |
| dc.date.available | 2018-05-28T16:34:44Z | - |
| dc.date.issued | 1997 | - |
| dc.identifier.uri | http://10.0.0.11:8080/jspui/handle/bnmm/73358 | - |
| dc.description | Se estudia la complejidad en espacio y tiempo de los procedimientos de eliminación geométrica tanto desde el punto de vista algorítmico como del de la complejidad computacional. Desde el punto de vista algorítmico, se desarrollan algoritmos determinísticos que resuelven algunos de los principales problemas de eliminación y requieren bajo recursos de espacio de memoria. Posteriormente se desarrolla una clase de algoritmos probabiísticos cuyo comportamiento en cuanto al tiempo es superior, que es capaz de distinguir sistemas bien condicionados de sistemas mal condicionados. Desde el punto de vista de la complejidad computacional, se demuestra una cota inferior para el tradeoff espacio-tiempo de los procedimientos de evaluación de polinomios y se exhiben varios casos naturales donde se alcanza esta cota. Finalmente se demuestra que todos los métodos generalistas existentes sobre el tema y todas sus posibles variantes requieren tiempo exponencial. | - |
| dc.description | The space-time complexity of geometric elimination procedures is studied from both the algorithmic and the computational complexity point of view. From the algorithmic point of view, deterministic algorithms are developed which solve some of the main elimination problems and require small space resources. Afterwards, a class of probabilistic algorithms is developed which has a better time performance and is able to distinguish well conditionated from ill-posed systems. From the computational complexity point of view, an optimal lower bound for the space-time tradeoff of polynomial evaluation procedures is shown and several natural cases where this bound is reached are exhibited. Finally, all the existent general purpose methods on the subject and all their posible variants are proved to require exponential time. | - |
| dc.description | Fil:Matera, Guillermo. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. | - |
| dc.format | application/pdf | - |
| dc.language | spa | - |
| dc.publisher | Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires | - |
| dc.rights | info:eu-repo/semantics/openAccess | - |
| dc.rights | http://creativecommons.org/licenses/by/2.5/ar | - |
| dc.source.uri | http://digital.bl.fcen.uba.ar/gsdl-282/cgi-bin/library.cgi?a=d&c=tesis&d=Tesis_2931_Matera | - |
| dc.subject | ELEMINATION | - |
| dc.subject | ALGORITHMS | - |
| dc.subject | COMPLEXITY | - |
| dc.subject | TRADEOFFS | - |
| dc.subject | CIRCUITS | - |
| dc.subject | ELIMINACION | - |
| dc.subject | ALGORITMOS | - |
| dc.subject | COMPLEJIDAD | - |
| dc.subject | TRADEOFFS | - |
| dc.subject | CIRCUITOS | - |
| dc.title | Sobre la complejidad en espacio y tiempo de la eliminación geométrica | - |
| dc.title | On the space-time complexity of geometric elimination | - |
| dc.type | info:eu-repo/semantics/doctoralThesis | - |
| dc.type | info:ar-repo/semantics/tesis doctoral | - |
| dc.type | info:eu-repo/semantics/publishedVersion | - |
| Aparece en las colecciones: | FCEN - Facultad de Ciencias Exactas y Naturales. UBA | |
Ficheros en este ítem:
No hay ficheros asociados a este ítem.