Sobre la complejidad en espacio y tiempo de la eliminación geométrica
Se estudia la complejidad en espacio y tiempo de los procedimientos deeliminación geométrica tanto desde el punto de vista algorítmico como delde la complejidad computacional. Desde el punto de vista algorítmico, se desarrollan algoritmos determinísticosque resuelven algunos de los principales problemas de eliminacióny requieren bajo recursos de espacio de memoria. Posteriormente se desarrollauna clase de algoritmos probabiísticos cuyo comportamiento en cuantoal tiempo es superior, que es capaz de distinguir sistemas bien condicionadosde sistemas mal condicionados. Desde el punto de vista de la complejidad computacional, se demuestrauna cota inferior para el tradeoff espacio-tiempo de los procedimientosde evaluación de polinomios y se exhiben varios casos naturales donde sealcanza esta cota. Finalmente se demuestra que todos los métodos generalistasexistentes sobre el tema y todas sus posibles variantes requieren tiempoexponencial.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | info:eu-repo/semantics/doctoralThesis biblioteca |
| Language: | spa |
| Published: |
Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
|
| Subjects: | ELIMINACION, ALGORITMOS, COMPLEJIDAD, TRADEOFFS, CIRCUITOS, ELEMINATION, ALGORITHMS, COMPLEXITY, CIRCUITS, |
| Online Access: | https://hdl.handle.net/20.500.12110/tesis_n2931_Matera http://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=tesis_n2931_Matera_oai |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | Se estudia la complejidad en espacio y tiempo de los procedimientos deeliminación geométrica tanto desde el punto de vista algorítmico como delde la complejidad computacional. Desde el punto de vista algorítmico, se desarrollan algoritmos determinísticosque resuelven algunos de los principales problemas de eliminacióny requieren bajo recursos de espacio de memoria. Posteriormente se desarrollauna clase de algoritmos probabiísticos cuyo comportamiento en cuantoal tiempo es superior, que es capaz de distinguir sistemas bien condicionadosde sistemas mal condicionados. Desde el punto de vista de la complejidad computacional, se demuestrauna cota inferior para el tradeoff espacio-tiempo de los procedimientosde evaluación de polinomios y se exhiben varios casos naturales donde sealcanza esta cota. Finalmente se demuestra que todos los métodos generalistasexistentes sobre el tema y todas sus posibles variantes requieren tiempoexponencial. |
|---|