DENIF – Documents d’Enseignement Numériques en Informatique Fondamentale

   TDs

     TDs

•   Les grands ne valent pas mieux que les petits
•   Du haut de mon arbre
•   Pour imprimer mieux que Gutenberg
•   Huffman
•   Trions tout cela
•   Partiel 2007-2008
•   Tous dans l'arène
•   Discussion partiel et petits exos
•   Pfouu ! J'y comprends rien c'est trop difficile
•   J'y comprends toujours rien, mais je m'en fous j'approxime
•   Comment bien disposer k cafetières dans un labo ?
•   Comme au Judo, il faut amortir...
•   Miam ! Un mille-feuille
•   Révisions
•   Grand méchant partiel

     Cours  

•   poly
•   correction de l'exercice «pièce de 18 centimes»
•   papier complémentaire sur le rendu de monnaie

     Travaux dirigés  

•   td1 énoncé : Les plus petits devant
•   td1 corrigé
•   td2 énoncé : En rang
•   td2 correction
•   td3 énoncé : Programmation dynamique
•   td3 correction
•   td4 énoncé : C'est celui Greedy qui y est
•   td4 correction
•   td5 énoncé : partiel 2006 - 2007
•   td 5 correction
•   partiel sujet en français
•   partiel sujet en anglais
•   corrigé du partiel
•   td6 énoncé : Depuis les gradins
•   corrigé td6
•   td7 énoncé : Minimisons les distances
•   td7 corrigé
•   td8 énoncé : plus court chemin
•   td 8 corrigé

     Cours

•   Structure de données avancées : affinage de partition
•   Structures de données avancées : extension de SD
•   Graphes : définitions, parcours
•   Graphes : arbres
•   Graphes : arbres couvrants, forte connexité
•   Graphes : distances, tri topologique
•   Graphes : flots
•   Graphes : flots, couplages
•   Graphes : flots, applications
•   Mots : recherche de motifs
•   Mots : recherche de motifs, arbre des suffixes
•   arbre des suffixes fin, distance min dans un nuage de points
•   Algorithmique géométrique : enveloppe convexe

     TDs  

•   TD1 : Tables de Hachage
•   TD1 : corrigé
•   TD2 : Tableau vide : Compter avec des compteurs, recherche de mots
•   TD2 : corrigé
•   TD3 : graphes : échauffement, propriétés, petits problèmes
•   TD3 : corrigé
•   TD4 : Graphe à part (ou l'inverse) : Graphe orienté, composante fortement connexe, graphe biparti, clique
•   TD4 : corrigé
•   TD5 : Graphe eulérien, semi-eulérien, arbitrairement eulérien, cheminement maximal
•   TD5 : corrigé
•   TD6 : Zoo graphes : Graphe scorpion, connexité, ensemble dominant, arbre couvrant
•   TD6 : corrigé
•   TD7 : Agence de voyage magique : graphe orienté, pondéré, chemin de poid minimal
•   TD7 : corrigé
•   TD8 : Déluges & Flots : flot maximum, coupe
•   TD8 : corrigé
•   TD9 : Bzzz, Bzzz, Bzzz : flot maximum, théoreme de Hall, couplage
•   TD9 : corrigé
•   TD10 : Coloriage, graphe planaire, recherche de motif
•   TD10 : corrigé

     Examens  

•   Partiel : listes triées, points d'articulation, isthmes, composantes 2-connexes

     Bibliographie  

•   Bibliographie

     Cours  

•   Polycopié (en cours de rédaction)

     TDs  

•   description des TDs de devoirs
•   TD1 : min et max simultané, méthode de l'adversaire
•   TD1 : corrigé
•   TD2 : deux plus grands éléments d'un tableau, matrices de Toeplitz
•   TD2 : corrigé
•   TD3 : programmation dynamique
•   TD3 : corrigé
•   TD4 : exemple glouton : codage de Huffman
•   TD4 : corrigé
•   TD5 - partie 1 : partiel 2004
•   TD5 - partie 1 : Corrigé
•   TD5 - partie 2 : partiel 2005
•   TD5 - partie 2 : Corrigé
•   TD6 : élément majoritaire
•   TD6 : corrigé
•   TD7 : NP-complétude
•   TD8 : NP-complétude de cubic (les deux dernières pages sont à distribuer à la fin du TD)
•   TD8 : article à l'origine
•   TD9 : NP-complétude et 2-approx pour k-centre et sac à dos
•   TD10 : NP-complétude et approximations pour subset-sum et sac à dos
•   TD 10 : corrigé de l'exercice 1
•   TD 10 : corrigé de l'exercice 2
•   TD11 : parcours en profondeur d'un graphe et application à 2-SAT

     Examens  

•   Partiel
•   DM
•   Corrigé

     Examens

•   Partiel
•   Corrigé
•   Examen

     Cours

•   Tout le cours

     TDs corrigés par les étudiants de 2004/2005  

•   TD 1 : Maximum de n entiers, plus petit et plus grand
•   TD 2 : Plus grand et deuxième plus grand de n entiers, matrice de Toepliz
•   TD 3 : Triangulation de polygônes, jeu de construction, impression équilibrée
•   TD 4 : Couverture par intervalles, codage de huffman
•   TD 5 : Du pétrole et des idées, médian pondéré
•   TD 6 : Composantes fortement connexes, 2-SAT, graphe des composantes fortement connexes, tri topologique
•   TD 7 : (Étude du partiel de 2003/2004)
•   TD 8 : (Semaine du partiel de 2004/2005)
•   TD 9 : (!!! n'est pas disponible !!!)
•   TD 10 : Liste de problèmes dont il faut montrer la NP-complétude
•   TD 11 : Approximabilité de Subset-Sum
•   TD 12 : étude de l'examen de 2003/2004

     Examens  

•   Partiel
•   Corrigé

     TDs  

•   TD 1 : Recherche du plus grand, du plus petit et du plus grand simultanément, optimalité
•   TD 2 : Algorithme de majorité : quadratique, nlogn et linéaire
•   TD 3 : Algorithme de majorité : l'optimal ; recherche du deuxième plus grand ; matrices de Toeplitz
•   TD 4 : Programmation dynamique
•   TD 5 : Arbres binaires de recherche, rouges et noirs, B-arbres
•   TD 6 (Correction du partiel)
•   TD 7 : Recherche du quantième, médian pondéré, bureau de poste et champ pétrolier
•   TD 8 : Codage de Huffman
•   TD 9 : Coloriages et périmètres, partiel 99
•   TD 10 : Nombre de coloriages, variantes de SAT
•   TD 11 : NP-complétude de coloriages
•   TD 12 : Couverture des sommets d'un graphe, somme d'un sous-ensemble, partition
•   TD 13 : Recherche de motifs : automates finis, algorithme de Knuth, Morris, Pratt et algorithme de Rabin-Karp