Fiodor Fomine
Pour les articles homonymes, voir Fomine.
Ne doit pas être confondu avec Sergueï Vladimirovitch Fomine.
Fiodor Vladimirovitch Fomine (en russe : Фёдор Владимирович Фомин, orthographe anglaise : Fedor Fomin) est un professeur d'informatique à l'université de Bergen. Il est connu pour ses contributions à l'algorithmique et à la théorie des graphes.
Фёдор Владимирович Фомин
| Naissance |
|---|
| Domaines | Algorithmique et théorie des graphes |
|---|---|
| Institutions | Université de Bergen |
| Formation | Université d'État de Saint-Pétersbourg |
| Directeur de thèse | Nikolaï Nikolaïevitch Petrov |
| Distinctions | prix IPEC Nerode 2015 et 2017 |
| Site | www.ii.uib.no/~fomin/ |
Carrière modifier
Fiodor Fomine obtient sa maîtrise (1992) et son doctorat (1997) à l'université d'État de Saint-Pétersbourg sous la supervision de Nikolaï Nikolaïevitch Petrov[1]. Il est professeur assistant à l'université d'État de Saint-Pétersbourg (chaire de recherche opérationnelle) jusqu'en 1999. Il est chercheur postdoctoral au Chili (Centro de Modelamiento Matemático de l'Universidad de Chile), en République tchèque (Institute for Theoretical Computer Science de l'université Charles de Prague, en Allemagne (université de Paderborn). Depuis 2002, Fomine est professeur d'algorithmique au département d'informatique de l'université de Bergen.
En 2011-2016, il dirige un projet ERC (Advanced Investigator Grant) intitulé Rigorous Theory of Preprocessing. Il dirige également un projet financé par la Russie sur les Algorithms and complexity beyond polynomial time, qui a pour objectif de créer l'infrastructure de recherche en informatique théorique au département de l'Institut Steklov.
Travaux modifier
Fomine travaille principalement dans les domaines de l'algorithmique et de la combinatoire. Il contribue principalement en complexité paramétrée[2] , kernelisation, algorithmes exacts en temps exponentiel, algorithmes de théorie des graphes, et notamment mineurs de graphes , coloration de graphes et ses variantes, graphes avec paramètres de largeur (largeur arborescente, largeur de branchement, largeur de clique), et des problèmes de poursuite-évasion et de recherche dans un graphe.
Fomine est connu par ses publications sur la bidimensionnalité, sur laquelle il travaille depuis 2004, et qu'il présente notamment dans l'article de synthèse
- Fedor V. Fomin, Erik D. Demaine, Mohammad Taghi Hajiaghayi et Dimitrios M. Thilikos, « Bidimensionality », dans Ming-Yang Kao (éditeur), Encyclopedia of Algorithms, (ISBN 978-1-4939-2863-7), p. 203-207.
Fomine est coauteur de deux livres :
- Fedor V. Fomin et Dieter Kratsch, Exact Exponential Algorithms, Springer, , 203 p. (ISBN 978-3-642-16532-0, lire en ligne)
- Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michal Pilipczuk et Saket Saurabh, Parameterized Algorithms, Springer, , 555 p. (ISBN 978-3-319-21274-6, lire en ligne)
Honneurs et récompenses modifier
Fiodor Fomine a reçu en 2004 le Young Investigator Award du Conseil norvégien de la recherche. Il a reçu deux fois le prix IPEC Nerode attribué par l'European Association for Theoretical Computer Science[3] :
- une première fois en 2015, avec ses coauteurs Erik D. Demaine, Mohammad Hajiaghayi et Dimitrios M. Thilikos, pour leur article :
- Erik D. Demaine, Fedor V. Fomin, Mohammadtaghi Hajiaghayi et Dimitrios M. Thilikos, « Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs », Journal of the ACM, vol. 52, no 6, , p. 866–893 (ISSN 0004-5411, DOI 10.1145/1101821.1101823).
- une deuxième fois en 2017, avec ses coauteurs Fabrizio Grandoni et Dieter Kratsch :
- Fedor V. Fomin, Fabrizio Grandoni et Dieter Kratsch, « A measure & conquer approach for the analysis of exact algorithms », Journal of the ACM, vol. 56, no 5, , p. 1–32 (ISSN 0004-5411, DOI 10.1145/1552285.1552286)
Notes et références modifier
- (en) « Fedor Vladimirovich Fomin », sur le site du Mathematics Genealogy Project.
- Par exemple : Pradeesha Ashok, Fedor V. Fomin, Sudeshna Kolay, Saket Saurabh et Meirav Zehavi, « Exact Algorithms for Terrain Guarding », ACM Transactions on Algorithms, vol. 14, no 2, , p. 1–20 (DOI 10.1145/3186897).
- « Nerode Prize » (consulté le )
Liens externes modifier
- Page personnelle de Fomine à l'université de Bergen
- Publications de Fomine sur DBLP
- Google Scholar
- Ressources relatives à la recherche :
