Informatique
Le cours d'informatique du semestre 3, sous la responsabilité de František Kardos, demande de réfléchir à des solutions algorithmiques plus complexes qu'au premier semestre. L'objectif est d'apprendre à construire une réflexion algorithmique et à s'abstraire de la machine, plus que d'obtenir à tout prix un code qui fonctionne ; recopier la correction sans la comprendre ni y réfléchir ne sert à rien. Le cours définit la complexité d'un algorithme et les notations , et , étudie le tri rapide et le tri fusion, puis énonce le Master Theorem ; il se termine par les définitions de base sur les graphes. Les TD machine, en Python, reprennent la recherche dichotomique et les tris avant de passer aux graphes avec la bibliothèque bibgraphes : couleurs et degrés, connexité et chemins, 2-coloration, parcours en largeur et couplages.
Notes de cours
Cours2 pages
- Complexité des algorithmes et triComplexité d'un algorithme, notations O, Ω et θ, tri naïf, tri rapide (quick sort), tri fusion (merge sort) et Master Theorem.
- Les graphesDéfinitions de base sur les graphes : sommets, arêtes, boucles, arêtes parallèles, degré, chaîne, connexité, composantes connexes, cycle et arbre.
Travaux dirigés5 pages
- Recherche dichotomique et trisRecherche dichotomique, tri par insertion, tri par insertion dichotomique, quick sort, merge sort et comparaison des temps d'exécution.
- Premiers pas avec les graphes : couleurs et degrésColoriage des sommets, comptage par couleur, voisins communs, degrés minimal et maximal, nombre d'arêtes et sommets isolés.
- Connexité, chemins et 2-colorationMarquage des sommets accessibles, connexité, nombre de composantes connexes, recherche d'un chemin et 2-coloration.
- Parcours en largeurParcours en largeur par coloriage puis par marquage, calcul des distances et des pères, coloriage par palette selon la distance.
- Graphes réguliers et couplagesTest et TP sur les graphes : graphe régulier, arêtes incidentes marquées, sommets libres et saturés, vérification et construction d'un couplage.