---

Module Math du Web

L3 Informatique, L3 Math, L3 Math/Info

GLMA 605

---

    Notes et corrigé du CC:

Notes     Énoncé     Corrigé page 1     Corrigé page 2

    Planning 2011/2012:

Controle Continu le vendredi 16 mars de 15h00 à 16h30

Les créneaux de cours-td sont le vendredi de 9h45 à 11h30 et de 13h15 à 14h45, salle TD.4.04.
Les tps ont lieu le le vendredi de 15h00 à 16h30 au bâtiment 6.
Pour plus de précisions, voir l'emploi du temps de la fac de sciences.

Début des cours le vendredi 27 janvier, pas de td ni de tp ce jour-là.

Intervenants:
  - Stéphane Bessy
  - Pascal Azerad

    Contenu du cours:

• Première partie: graphe du web, étude du moteur de recherche HITS, structure des réseaux pair-à-pair (S. Bessy).
• Seconde partie: étude des algorithmes de PageRank (P. Azerad).

Détails de la première partie:

• Chapitre 1: Modélisation de réseaux, graphe du Web.
  • Outils: probabilités discrètes et théorie des graphes.
    
  • Propriétés de certains grands réseaux, graphe du web.
    
  • Modèles mathématiques
    
• Chapitre 2: Un exemple de moteur de recherche: Hits.
  • Principe de HITS: scores de hub et authority.
    
  • Étude de la convergence (puissances itérées).
    
• Chapitre 3: Modèles pour les Réseaux pair-à-pair.
  • Introduction: définitions des réseaux pair-à-pair, quelques exemples.
    
  • Modèle: algorithmes de routage, forte-connectivité (Théorème de Menger).
  • Structure des réseaux logiques: tables de hachage distribuées.
  • Exemples de graphes logiques structurés: graphes de Cayley (Chord), hypercube (Kademlia), graphe de De Bruijn.

    Fiches de TD:

• TD1: Modélisation de réseaux, algorithmes.
• TD2: Moteur de recherche HITS.
• TD3: Modèles pour les réseaux pair-à-pair.

   Fiches de TP:

• TP1: Graphe du Web, HITS.
  Primitives de bases et trame de programme en C pour:
  - Generation graphe a loi de degres fixe: Gen_A_Com.cc
  -le calcul du vecteur d'authority: authority.cc
  -le calcul des composantes fortement connexes: cfc.cc
  
• TP2: Simulation du réseau Chord.
  Primitives de bases et trame de programme en C pour:
  - l'initialisation du réseau: chord.cc
  un corrigé (pour l'insertion de machines seulement): corrige.cc
  

   Contrôle des connaissances

Il y aura un examen, et un controle continu comptant pour un tiers dans la note finale (avec règle du max...).

   Bibliographie:

• Google's pagerank and beyond, A.N. Langville, C.D. Meyer, Ed. Princeton University Press.
  
• Introduction à l'algorithmique, T. Cormen, C. Leiserson, R. Rivest, Ed. Dunod, (Chap: algorithme des graphes orientés).
  

---