Accès direct au contenu

ED Mathématiques, Information, Ingénierie des Systèmes NORMANDIE_UNIVERSITE


Soutenancessoutenances

Soutenance Mohamad BADAOUI

G-graphs and Expander graph


Vendredi 30 mars 2018 à 13h30
Monsieur Mohamad BADAOUI – laboratoire GREYC
Spécialité : Informatique
Directeur de thèse : Alain BRETTO
Lieu : salle des thèses, bâtiment sciences 3, campus 2, Université de Caen Normandie
Titre de la thèse : G-graphs and Expander graph

Résumé : L’utilisation de  l’algèbre pour résoudre des problèmes de graphes a conduit au développement de trois branches : théorie spectrale des graphes, géométrie et combinatoire des groupes et études des invariants de graphes. La notion de graphe d’expansions (invariant de graphes) est relativement récente, elle a été développée afin d’étudier  la robustesse des réseaux de télécommunication. Il s’avère que la construction de familles infinies de graphes expanseurs est un problème difficile. Cette thèse traite principalement de la construction de nouvelles familles de tels graphes. Les graphes expanseurs possèdent des nombreuses applications en informatique, notamment  dans la construction de certains  algorithmes, en théorie de la complexité, sur les marches aléatoires (random walk), etc. En informatique théorique, ils sont utilisés pour construire des familles de codes correcteurs d’erreur. Comme nous l’avons déjà vu les familles d’expanseurs sont difficiles à construire. La plupart des constructions   s'appuient sur des techniques algébriques complexes, principalement en utilisant des graphes de Cayley et des produit  Zig-Zag. Dans cette thèse, nous présentons une nouvelle méthode de construction de familles infinies d’expanseurs en utilisant les G-graphes. Ceux-ci sont en quelque sorte une généralisation des graphes de Cayley. Plusieurs nouvelles familles infinies d’expanseurs sont construites, notamment la première famille  d’expanseurs irréguliers.

AGENDA 2017

 

avril

3 avril au 30 mai
5e édition des SCOUAT
INSA Rouen Normandie

mai



25
2e Disrupt Day
Rouen

juin


4 au 8
Summer Camp
Caen

8
Fin Appel à projets
Fête de la Science 2018

8
APIE
Fin dépôt dossiers

12
Prix PEPITE
Fin dépôt dossier

18-22
S4D 2018
Caen

20-22
RMR 2018
Rouen

22
SolsTICE 2018
Ensicaen

25
Journée de rencontres EDP
Le Havre

28
10e journée Fédération Normandie-Mathématiques
Caen

juillet


10 -11
Université d'été MESRI
Rennes



Bât sciences 3 / 6 BD Maréchal Juin / 14032 CAEN CEDEX