{"id":111771,"date":"2018-03-11T10:38:27","date_gmt":"2018-03-11T10:38:27","guid":{"rendered":"https:\/\/www.deberes.net\/tesis\/sin-categoria\/aplicaciones-de-la-dimension-efectiva-a-la-complejidad-computacional-y-a-los-algoritmos-de-comprension-de-datos\/"},"modified":"2018-03-11T10:38:27","modified_gmt":"2018-03-11T10:38:27","slug":"aplicaciones-de-la-dimension-efectiva-a-la-complejidad-computacional-y-a-los-algoritmos-de-comprension-de-datos","status":"publish","type":"post","link":"https:\/\/www.deberes.net\/tesis\/matematicas\/aplicaciones-de-la-dimension-efectiva-a-la-complejidad-computacional-y-a-los-algoritmos-de-comprension-de-datos\/","title":{"rendered":"Aplicaciones de la dimensi\u00f3n efectiva a la complejidad computacional y a los algoritmos de comprensi\u00f3n de datos"},"content":{"rendered":"

Tesis doctoral de Mar\u00eda Lopez Valdes <\/strong><\/h2>\n

Durante las \u00faltimas d\u00e9cadas, la tecnolog\u00eda de las computadoras y el uso que de ellas se hace ha progresado de forma incre\u00edble. Dentro de este ritmo de desarrollo, importantes aplicaciones en inform\u00e1tica quedan obsoletas gracias a los nuevos recursos o a la aparici\u00f3n de soluciones m\u00e1s ingeniosas. ahora bien, si adem\u00e1s de generar resultados fu\u00e9ramos capaces de entender el fundamento de estos resultados, el desarrollo podr\u00eda ser mucho m\u00e1s estructurado y beneficioso. Este es el principal inter\u00e9s de la inform\u00e1tica te\u00f3rica: el sentar las bases formales de la inform\u00e1tica para facilitar as\u00ed un avance de conocimiento, proporcionar una visi\u00f3n global de los problemas y una intuici\u00f3n sobre futuras soluciones que puedan ser m\u00e1s adecuadas. dentro de la inform\u00e1tica te\u00f3rica existen numerosas \u00e1reas de estudio como por ejemplo: – la teor\u00eda de la computabilidad: estudia si un problema puede resolverse con un procedimiento autom\u00e1tico. – la teor\u00eda de la complejidad computacional: estudia si un problema se puede resolver de un modo eficiente. – la teor\u00eda de aprendizaje computacional: estudia la dificultad de que una m\u00e1quina sea capaz de aprender a encontrar las soluciones de un determinado problema. – la teor\u00eda de la informaci\u00f3n: estudia la complejidad intr\u00ednseca de las secuencias (por ejemplo, de las soluciones de un determinado problema) as\u00ed como lo que se pueden comprimir. en la b\u00fasqueda de nuevos conocimientos en cada una de estas \u00e1reas se han desarrollado numerosas herramientas formales. Por ejemplo, lutz introdujo en el a\u00f1o 2000 la dimensi\u00f3n efectiva orientada inicialmente a obtener resultados en el \u00e1rea de la complejidad computacional. Ahora bien, entre las diversas \u00e1reas existen fuertes conexiones y por lo tanto, parece l\u00f3gico que tambi\u00e9n existan conexiones entre las distintas herramientas formales que se utilizan. Encontrar estas conexiones permite trasladar resultados de unas \u00e1reas a otras y obtener un conocimiento mucho m\u00e1s profundo de los diversos problemas que pueden ser resueltos con un computador actual o incluso con un computador que pueda ser desarrollado en un futuro. en esta tesis se han estudiado las relaciones existentes entre la dimensi\u00f3n efectiva y la complejidad de kolmogorov, los ratios de compresi\u00f3n o el rendimiento en algoritmos de aprendizaje. Esto ha permitido trasladar resultados de complejidad computacional a aprendizaje computacional o teor\u00eda de la informaci\u00f3n y viceversa, estableciendo nuevas cotas superiores e inferiores de complejidad para problemas y clases de problemas cuya dimensi\u00f3n se conoce, as\u00ed como nuevos resultados sobre el tama\u00f1o de clases en funci\u00f3n de su complejidad. M\u00e1s concretamente: – dimensi\u00f3n y complejidad de kolmogorov: ryabko, staiger, cai y hartmanis fueron los primeros en estudiar la relaci\u00f3n entre dimensi\u00f3n cl\u00e1sica de hausdorff y complejidad de kolmogorov. Con el desarrollo de la versi\u00f3n constructiva de la dimensi\u00f3n de hausdorff, mayordomo y lutz demostraron que se consegu\u00eda una caracterizaci\u00f3n completa. en cuanto a los casos de dimensi\u00f3n calculable y dimensi\u00f3n en espacio polin\u00f3mico, hitchcock demostr\u00f3 que tambi\u00e9n es posible una caracterizaci\u00f3n completa. En este caso es necesario utilizar la versi\u00f3n de complejidad de kolmogorov con recursos de espacio acotados. en esta tesis se generalizan todos estos resultados para la dimensi\u00f3n con escala (un refinamiento de la dimensi\u00f3n efectiva). Para demostrar estos resultados se ha desarrollado la dimensi\u00f3n con escala para secuencias finitas, de inter\u00e9s independiente. Intuitivamente, estos resultados presentan una estrecha relaci\u00f3n entre el tama\u00f1o de una clase de problemas y la compresibilidad m\u00e1xima alcanzable para cada uno de estos problemas, a\u00fan en el caso de una medida de tama\u00f1o muy ajustada al tipo concreto de problemas (dimensi\u00f3n con escala). Adem\u00e1s, estos resultados se utilizan para estudiar el comportamiento de las reducciones p\/poly-turing en la clase espace. – dimensi\u00f3n y compresi\u00f3n: la relaci\u00f3n entre dimensi\u00f3n en tiempo polin\u00f3mico y complejidad de kolmogorov no parece ser clara, por ese motivo, en esta tesis se utiliza la noci\u00f3n usual de algoritmo de compresi\u00f3n para secuencias finitas para caracterizar la dimensi\u00f3n en tiempo polin\u00f3mico. Gracias a esta nueva caracterizaci\u00f3n, varios resultados conocidos para dimensi\u00f3n en tiempo polin\u00f3mico se pueden interpretar como resultados de compresi\u00f3n. Por ejemplo, los lenguajes de una clase de p-dimensi\u00f3n 1 no pueden comprimirse (i.O.) En m\u00e1s que una cantidad sublineal. As\u00ed se obtienen resultados sobre la compresibilidad de lenguajes completos y autoreducibles, dos de los tipos de problemas de m\u00e1s inter\u00e9s en complejidad computacional. – dimensi\u00f3n y aprendizaje: en esta tesis se estudian la relaci\u00f3n de la dimensi\u00f3n con distintos modelos de aprendizaje. En relaci\u00f3n con el aprendizaje on-line se obtiene una cota superior de la dimensi\u00f3n en tiempo polin\u00f3mico de clases de conceptos que pueden aprenderse con algoritmos on-line en tiempo exponencial y con alpha 2^n errores. Adem\u00e1s se demuestra que esta cota superior es \u00f3ptima. En relaci\u00f3n con el aprendizaje pac, se demuestra que la dimensi\u00f3n en espacio polin\u00f3mico de clases de conceptos que son pac-aprendibles es cero. Igualmente se demuestra que es cero para clases de conceptos que pueden aprenderse con un algoritmo basado en preguntas. Estos resultados han permitido obtener hip\u00f3tesis que implican el no aprendizaje o la complejidad de las representaciones necesarias para aprender un concepto.<\/p>\n

 <\/p>\n

Datos acad\u00e9micos de la tesis doctoral \u00abAplicaciones de la dimensi\u00f3n efectiva a la complejidad computacional y a los algoritmos de comprensi\u00f3n de datos<\/strong>\u00ab<\/h3>\n
    \n
  • T\u00edtulo de la tesis:<\/strong>\u00a0 Aplicaciones de la dimensi\u00f3n efectiva a la complejidad computacional y a los algoritmos de comprensi\u00f3n de datos <\/li>\n
  • Autor:<\/strong>\u00a0 Mar\u00eda Lopez Valdes <\/li>\n
  • Universidad:<\/strong>\u00a0 Zaragoza<\/li>\n
  • Fecha de lectura de la tesis:<\/strong>\u00a0 15\/11\/2011<\/li>\n<\/ul>\n

     <\/p>\n

    Direcci\u00f3n y tribunal<\/h3>\n
      \n
    • Director de la tesis<\/strong>\n
        \n
      • Elvira Mayordomo Camara<\/li>\n<\/ul>\n<\/li>\n
      • Tribunal<\/strong>\n
          \n
        • Presidente del tribunal: Alberto Carlos Elduque palomo <\/li>\n
        • ricard Gavald\u00ed\u00a0 mestre (vocal)<\/li>\n
        • Rafael Morales bueno (vocal)<\/li>\n
        • jack harold Lutz (vocal)<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n

           <\/p>\n","protected":false},"excerpt":{"rendered":"

          Tesis doctoral de Mar\u00eda Lopez Valdes Durante las \u00faltimas d\u00e9cadas, la tecnolog\u00eda de las computadoras y el uso que de […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""}},"footnotes":""},"categories":[13880,126,59170,16104,13610],"tags":[203365,15864,222605,222604,48297,148966],"class_list":["post-111771","post","type-post","status-publish","format-standard","hentry","category-informatica","category-matematicas","category-procesos-de-compresion","category-teoria-de-la-informacion","category-zaragoza","tag-alberto-carlos-elduque-palomo","tag-elvira-mayordomo-camara","tag-jack-harold-lutz","tag-maria-lopez-valdes","tag-rafael-morales-bueno","tag-ricard-gavaldi-mestre"],"_links":{"self":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/posts\/111771","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/comments?post=111771"}],"version-history":[{"count":0,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/posts\/111771\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/media?parent=111771"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/categories?post=111771"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/tags?post=111771"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}