UNA INTRODUCCIÓ A LA COMPLEXITAT PARAMETRITZADA
UNA INTRODUCCIÓ A LA COMPLEXITAT PARAMETRITZADA
h. 10.00-13.00
Cal inscripció.
UPC
La complexitat parametritzada va ser introduïda als anys 90 per Downey i Fellows i va proposar una anàlisi més refinada dels problemes computacionals. La idea clau és estudiar les diferents maneres en què els paràmetres secundaris clau es poden intercalar amb la mida d'entrada en la complexitat computacional dels algorismes.
Aquest estudi va revelar oportunitats per dissenyar algorismes que encara es poden considerar eficients sota un concepte d'eficiència més fluix, però encara legítim. Això va induir l'estudi de problemes computacionals com a “entitats bivariades” on, a part de la mida de l'entrada, la segona variable és un paràmetre que mesura certes particularitats estructurals, especialment les que són habituals en aplicacions reals.
La teoria de la complexitat parametritzada és ara un camp madur de la informàtica teòrica i ha desenvolupat una gran quantitat de tècniques per dissenyar algorismes parametritzats (és a dir, límits superiors), però també per demostrar que aquests algorismes probablement no existeixen (és a dir, límits inferiors). Per demostrar els límits inferiors, Downey i Fellows van introduir una jerarquia de classes de complexitat parametritzades i adequades
conceptes de reductibilitat de problemes que van permetre la classificació sistemàtica de nombrosos problemes computacionals segons la seva complexitat parametritzada.
Aquest curs cobreix els conceptes fonamentals d'aquesta teoria des del punt de vista dels límits inferiors. El curs cobreix el concepte de parametrització del problema, explica "per què i com" això va induir la definició de la jerarquia de complexitat parametritzada i proporciona alguns enllaços d'aquesta teoria amb la teoria clàssica de la complexitat.
h. 10.00-13.00
Cal inscripció.
UPC
La complexitat parametritzada va ser introduïda als anys 90 per Downey i Fellows i va proposar una anàlisi més refinada dels problemes computacionals. La idea clau és estudiar les diferents maneres en què els paràmetres secundaris clau es poden intercalar amb la mida d'entrada en la complexitat computacional dels algorismes.
Aquest estudi va revelar oportunitats per dissenyar algorismes que encara es poden considerar eficients sota un concepte d'eficiència més fluix, però encara legítim. Això va induir l'estudi de problemes computacionals com a “entitats bivariades” on, a part de la mida de l'entrada, la segona variable és un paràmetre que mesura certes particularitats estructurals, especialment les que són habituals en aplicacions reals.
La teoria de la complexitat parametritzada és ara un camp madur de la informàtica teòrica i ha desenvolupat una gran quantitat de tècniques per dissenyar algorismes parametritzats (és a dir, límits superiors), però també per demostrar que aquests algorismes probablement no existeixen (és a dir, límits inferiors). Per demostrar els límits inferiors, Downey i Fellows van introduir una jerarquia de classes de complexitat parametritzades i adequades
conceptes de reductibilitat de problemes que van permetre la classificació sistemàtica de nombrosos problemes computacionals segons la seva complexitat parametritzada.
Aquest curs cobreix els conceptes fonamentals d'aquesta teoria des del punt de vista dels límits inferiors. El curs cobreix el concepte de parametrització del problema, explica "per què i com" això va induir la definició de la jerarquia de complexitat parametritzada i proporciona alguns enllaços d'aquesta teoria amb la teoria clàssica de la complexitat.
contingut
- La idea de la parametrització
- La classe FPT
- Exemples d'algorismes FPT
- Reduccions de FPT
- Les classes para-NP, XP
- Les classes W[P] i W[SAT]
- La jerarquia W, definicions alternatives
- Duresa per a la jerarquia W
- Hipòtesi del temps exponencial
- Lema d'esparsificació
Breu biografia del professor
El Prof. Dimítrios M. Thilikós Touloupas es va doctorar al Departament d'Enginyeria Informàtica i Informàtica de la Universitat de Patras l'any 1996. Actualment (2018) és investigador del CNRS al LIRMM i professor del Departament de Matemàtiques de NKUA. També actualment està visitant el departament de CS de la UPC com a ajudant de recerca. La seva recerca inclou contribucions en diversos camps de la informàtica teòrica i la matemàtica discreta amb contribucions en computació parametritzada i teoria de gràfics. En particular, els seus resultats estan relacionats amb la teoria de gràfics estructurals, les descomposicions de gràfics, els algorismes d'aproximació, els mètodes probabilistes, els jocs de cerca de gràfics i els homomorfismes de gràfics. També té contribucions a àrees aplicades com la computació distribuïda, la bioinformàtica i la mineria de dades. Ha publicat 146 articles, entre els quals el 40% durant els últims 5 anys.
La seva docència s'ha centrat en els fonaments matemàtics de la informàtica. Va impartir nombrosos cursos de grau i grau a universitats o centres de recerca al Canadà, a Espanya, França, Bèlgica, Grècia i Noruega. Va impartir cursos sobre teoria de la complexitat, teoria de la recursivitat, teoria d'autòmats, algorismes, combinatòria, teoria de gràfics i programació. També ha dissenyat i impartit diversos mini-cursos sobre àrees temàtiques de la seva especialitat, incloent 4 tutories a escoles de temporada al marge de conferències i tallers internacionals. Ha impartit 61 ponències seminaris en diversos centres de recerca i universitats. Ha dirigit 5 tesis doctorals i 18 tesis de màster.
Ha estat 11 vegades el principal organitzador de conferències/workshops. Ha estat 32 vegades membre de PC de conferències/workshops i n'ha estat encarregant-ne 2. En total, ha impartit 10 xerrades convidades en conferències/workshops. Finalment, ha estat l'editor o LNCS dels volums 6410 i 7535, del DAM volum 199 i dels TCS dels volums 399, 412 i 655.
El 2015 va rebre el premi Nerode EATCS per la seva contribució a la computació parametritzada.