---

Module Math du Web

L3 Informatique, L3 Math, L3 Math/Info

GLMA 605

---

    Corrigé de l'examen de mai 2014:

Énoncé     Corrigé   (barême: Ex1:1-2.5 Ex2:1.25-1.25-1-1-1-1)

    Corrigé et Notes du controle continu du vendredi 14 mars 2014:

Énoncé     Corrigé 1 et Corrigé 2
Notes

    Planning 2013/2014:

Les créneaux de cours-td sont le vendredi de 9h45 à 11h30 salle TD4.04 et de 13h15 à 14h45, salle TD.4.04.
Les tps ont lieu le le vendredi de 15h00 à 16h30 en salle TD5.08 ( ou exceptionnellement 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 24 janvier, pas de td-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...).

Controle Continu: le vendredi 14 mars de 9h45 à 11h15, aucun document autorisé.

   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).
  

---