Groupe de Lecture et de Travail de l'équipe AMACC
SFT 1d : a graphical approach
| Proposé par : | Pascal |
| Résumé : | Vous êtes allergiques aux degrés Turing, à la hiérarchie arithmetique, ou à des distinctions plus fines que décidable/indécidable, mais vous avez quand même envie d'entendre parler de sous-shifts, alors ce GLT est fait pour vous. Les SFTs 1d sont essentiellement des ensembles de chemins dans des graphes, nous parlerons de plusieurs notions de dynamique, ce qu'elles veulent dire sur les graphes et nous finirons par parler du problème de la conjugaison : LA notion d'isomorphisme pour les sous-shifts (mais on l'appelle pas comme ça parce qu'on est snobs), ce problème est décidable si l'on considère les SFTs sur N mais on ne sait pas pour les SFTs sur Z (et bien entendu c'est indécidable sur N^d, Z^d pour d>1). |
| Objectifs : | faire plaisir à Paul et parler de graphes, faire plaisir à Pascal et parler de sous-shifts |
| Prérequis : | Nada |
| Intéressés : |
Gaétan (4), Martin (2), Matthieu (5), Pascal (5), Paul (5)
|
Parameterized complexity
| Proposé par : | Paul |
| Résumé : | Les problèmes FPT sont les problèmes où la partie exponentielle peut se restreindre à un paramètre k. Est-alors FPT tout problème qui admet un algo en O(f(k)n^(O(1)). Les problèmes ayant un algo en O(n^f(k)) sont eux dans la classe XP. Une hierarchie W existe entre FPT et XP, avec les problèmes de clique max dans W(1), de dominant min dans W(2), etc... |
| Objectifs : | Le but est de consolider la connaissance de FPT/XP et de comprendre un peu une intuition de cette classification W. |
| Prérequis : | Trouver qqn qui s'y connait pour donner l'intuition, parce que moi, je ne l'ai pas encore... (Ou alors, la trouver tous ensemble) |
| Intéressés : |
Gaétan (3), Julien D (3), Julieng (5), Martin (2), Pascal (3), Paul (4)
|
Apprendre la méthode du col ?
| Proposé par : | Julieng |
| Résumé : | Faisant pourtant de l'arsenal de base du petit combinatoriste analytique, je n'ai jamais pratiqué la méthode du col (à part une fois à un cours à ALEA il y a longtemps) et j'aimerais qu'on organise un GLT pour qu'on puisse réviser nos gammes. Pour rappel, la méthode du col permet d'évaluer le comportement asymptotique d'une intégrale complexe du type $\int_C f(z) e^{\lambda g(z)} dz$. Non non je n'ai pas recopié Wikipédia. En tout cas, ça sert en combinatoire quand le très utilisé théorème de transfert ne peut plus s'appliquer (typiquement quand notre série génératrice a un rayon de convergence infini.) |
| Objectifs : | comprendre et pratiquer la méthode du col sur des exemples. |
| Prérequis : | un peu d'analyse complexe ? j'imagine |
| Intéressés : |
Jerzy (3), Julien (5), Martin (5)
|
Introduction à la combinatoire analytique
| Proposé par : | Martin |
| Résumé : | Vous en avez marre de ne rien comprendre aux exposés de combinatoire analytique. Vous vous demandez pourquoi diable ces gens font des développements limités de leur plein gré. « Théorème de transfert » vous évoque tout sauf de la combinatoire. Alors ce GLT est fait pour vous ! Venez découvrir le b.a.-ba de la combi analytique et calculer vos premières asymptotiques (presque) sans effort. |
| Objectifs : | Raconter aux non-combinatoricien⋅nes ce que les combinatoricien⋅nes font de leurs journées |
| Prérequis : | Rien ? (Être prêt⋅e à admettre un ou deux résultats d'analyse). |
| Intéressés : |
|