Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Algorithmique Avanc´ ee et Complexit´ e: Pr´ esentation du cours AAC Sophie Tis

Algorithmique Avanc´ ee et Complexit´ e: Pr´ esentation du cours AAC Sophie Tison-USTL-Master1 Informatique Objectifs Avoir des outils pour concevoir un ”bon” algorithme pour r´ esoudre un probl` eme. Objectifs Avoir des outils pour concevoir un ”bon” -c.` a.d. correct et efﬁcace - algorithme pour r´ esoudre un probl` eme. Cela pose de nombreuses questions...et demande pas mal de savoir-faire... Existe-il un algorithme pour r´ esoudre le probl` eme? Cela pose de nombreuses questions...et demande pas mal de savoir-faire... Existe-il un algorithme pour r´ esoudre le probl` eme? Connaˆ ıtre quelques Notions de Calculabilit´ e et de d´ ecidabilit´ e. Cela pose de nombreuses questions...et demande pas mal de savoir-faire. Est-ce un probl` eme classique? Cela pose de nombreuses questions...et demande pas mal de savoir-faire. Est-ce un probl` eme classique? Connaˆ ıtre et savoir reconnaˆ ıtre des grands classiques Cela pose de nombreuses questions...et demande pas mal de savoir-faire. Est-ce un probl` eme classique? Connaˆ ıtre et savoir reconnaˆ ıtre des grands classiques Tris, m´ ethodes de s´ election, recherche Cela pose de nombreuses questions...et demande pas mal de savoir-faire. Est-ce un probl` eme classique? Connaˆ ıtre et savoir reconnaˆ ıtre des grands classiques Tris, m´ ethodes de s´ election, recherche algorithmique des graphes, Cela pose de nombreuses questions...et demande pas mal de savoir-faire. Est-ce un probl` eme classique? Connaˆ ıtre et savoir reconnaˆ ıtre des grands classiques Tris, m´ ethodes de s´ election, recherche algorithmique des graphes, m´ ethodes de hachages Cela pose de nombreuses questions...et demande pas mal de savoir-faire. Est-ce un probl` eme classique? Connaˆ ıtre et savoir reconnaˆ ıtre des grands classiques Tris, m´ ethodes de s´ election, recherche algorithmique des graphes, m´ ethodes de hachages Programmation lin´ eaire... Cela pose de nombreuses questions...et demande pas mal de savoir-faire. Est-ce un probl` eme classique? Connaˆ ıtre et savoir reconnaˆ ıtre des grands classiques Tris, m´ ethodes de s´ election, recherche algorithmique des graphes, m´ ethodes de hachages Programmation lin´ eaire... .... Cela pose de nombreuses questions...et demande pas mal de savoir-faire Comment concevoir un algorithme? Cela pose de nombreuses questions...et demande pas mal de savoir-faire Comment concevoir un algorithme? Sch´ emas d’algorithmes, Algorithmic design patterns Cela pose de nombreuses questions...et demande pas mal de savoir-faire Comment concevoir un algorithme? Sch´ emas d’algorithmes, Algorithmic design patterns ”Diviser pour r´ egner” Cela pose de nombreuses questions...et demande pas mal de savoir-faire Comment concevoir un algorithme? Sch´ emas d’algorithmes, Algorithmic design patterns ”Diviser pour r´ egner” Programmtion Dynamique Cela pose de nombreuses questions...et demande pas mal de savoir-faire Comment concevoir un algorithme? Sch´ emas d’algorithmes, Algorithmic design patterns ”Diviser pour r´ egner” Programmtion Dynamique Algorithmes gloutons Cela pose de nombreuses questions...et demande pas mal de savoir-faire. L ’algorithme est-il correct? Cela pose de nombreuses questions...et demande pas mal de savoir-faire. L ’algorithme est-il correct? Savoir prouver un algorithme... ou tout du moins avoir un minimum de rigueur Cela pose de nombreuses questions... et demande pas mal de savoir-faire. L ’algorithme est-il efﬁcace? Cela pose de nombreuses questions... et demande pas mal de savoir-faire. L ’algorithme est-il efﬁcace? Savoir analyser la complexit´ e d’algorithmes Cela pose de nombreuses questions...et demande de multiples comp´ etences. Peut-on trouver un algorithme plus efﬁcace pour le probl` eme? Est-ce un probl` eme dur? Cela pose de nombreuses questions...et demande de multiples comp´ etences. Peut-on trouver un algorithme plus efﬁcace pour le probl` eme? Est-ce un probl` eme dur? ...Avoir quelques notions de Complexit´ e des probl` emes Cela pose de nombreuses questions...et demande pas mal de savoir-faire. Si le probl` eme est dur, comment l’appr´ ehender! Cela pose de nombreuses questions...et demande pas mal de savoir-faire. Si le probl` eme est dur, comment l’appr´ ehender! Connaˆ ıtre quelques techniques d’ Algorithmique Avanc´ ee: M´ eta-heuristiques, Algorithmes probabilistes,... Backtracking, minmax, s´ eparation-´ evaluation Ce que nous ferons Quelques sch´ emas d’algorithmes (2-3 cours) Un peu de complexit´ e de probl` emes (2-3 cours) Un peu d’agorithmique avanc´ ee (2-3 cours) Quelques notions de d´ ecidabilit´ e et calculabilit´ e (1-2 cours) Ce que nous ferons Quelques sch´ emas d’algorithmes (2-3 cours) Un peu de complexit´ e de probl` emes (2-3 cours) Un peu d’agorithmique avanc´ ee (2-3 cours) Quelques notions de d´ ecidabilit´ e et calculabilit´ e (1-2 cours) Ce que nous ferons Quelques sch´ emas d’algorithmes (2-3 cours) Un peu de complexit´ e de probl` emes (2-3 cours) Un peu d’agorithmique avanc´ ee (2-3 cours) Quelques notions de d´ ecidabilit´ e et calculabilit´ e (1-2 cours) Ce que nous ferons Quelques sch´ emas d’algorithmes (2-3 cours) Un peu de complexit´ e de probl` emes (2-3 cours) Un peu d’agorithmique avanc´ ee (2-3 cours) Quelques notions de d´ ecidabilit´ e et calculabilit´ e (1-2 cours) Bibliographie : de nombreuses ressources en ligne . Le dictionnaire recensant les algorithmes et probl` emes classiques du NIST . The Stony Brook Algorithm Repository” qui contient des impl´ ementations d’algorithmes pour des dizaines de probl` emes classiques, . Algorithms Courses on the WWW, qui contient une collection de cours d’algorithmique, . Le site du cours ”Algorithms in the Real World”, . ”A compendium of NP optimization problems”: Bibliographie : de nombreuses ressources en ligne . Le dictionnaire recensant les algorithmes et probl` emes classiques du NIST . The Stony Brook Algorithm Repository” qui contient des impl´ ementations d’algorithmes pour des dizaines de probl` emes classiques, . Algorithms Courses on the WWW, qui contient une collection de cours d’algorithmique, . Le site du cours ”Algorithms in the Real World”, . ”A compendium of NP optimization problems”: Bibliographie : de nombreuses ressources en ligne . Le dictionnaire recensant les algorithmes et probl` emes classiques du NIST . The Stony Brook Algorithm Repository” qui contient des impl´ ementations d’algorithmes pour des dizaines de probl` emes classiques, . Algorithms Courses on the WWW, qui contient une collection de cours d’algorithmique, . Le site du cours ”Algorithms in the Real World”, . ”A compendium of NP optimization problems”: Bibliographie : de nombreuses ressources en ligne . Le dictionnaire recensant les algorithmes et probl` emes classiques du NIST . The Stony Brook Algorithm Repository” qui contient des impl´ ementations d’algorithmes pour des dizaines de probl` emes classiques, . Algorithms Courses on the WWW, qui contient une collection de cours d’algorithmique, . Le site du cours ”Algorithms in the Real World”, . ”A compendium of NP optimization problems”: Bibliographie : de nombreuses ressources en ligne . Le dictionnaire recensant les algorithmes et probl` emes classiques du NIST . The Stony Brook Algorithm Repository” qui contient des impl´ ementations d’algorithmes pour des dizaines de probl` emes classiques, . Algorithms Courses on the WWW, qui contient une collection de cours d’algorithmique, . Le site du cours ”Algorithms in the Real World”, . ”A compendium of NP optimization problems”: Bibliographie : de nombreux livres .Cormen, Leiserson, Rivest, ”Introduction ` a l’algorithmique”, Dunod (disponible ` a la BU) vraiment ”une” r´ ef´ erence essentielle en algorithmique, . S. Skiena, ”Algorithm Design Manual”, une ”mine”! (Une version on-line proche du livre papier ), . Sur l’aspect ”algorithmic pattern”, ”Data Structures and Algorithms with object-oriented design patterns in Java”. 2000, disponible sur le Web , ... Bibliographie : de nombreux livres .Cormen, Leiserson, Rivest, ”Introduction ` a l’algorithmique”, Dunod (disponible ` a la BU) vraiment ”une” r´ ef´ erence essentielle en algorithmique, . S. Skiena, ”Algorithm Design Manual”, une ”mine”! (Une version on-line proche du livre papier ), . Sur l’aspect ”algorithmic pattern”, ”Data Structures and Algorithms with object-oriented design patterns in Java”. 2000, disponible sur le Web , ... Bibliographie : de nombreux livres .Cormen, Leiserson, Rivest, ”Introduction ` a l’algorithmique”, Dunod (disponible ` a la BU) vraiment ”une” r´ ef´ erence essentielle en algorithmique, . S. Skiena, ”Algorithm Design Manual”, une ”mine”! (Une version on-line proche du livre papier ), . Sur l’aspect ”algorithmic pattern”, ”Data Structures and Algorithms with object-oriented design patterns in Java”. 2000, disponible sur le Web , ... Organisation: les TPs Il y aura 6 s´ eances de TP (langage : Java) encadr´ ees pour la mise en oeuvre directe des m´ ethodes ´ etudi´ ees en cours: . Programmation dynamique, Algorithmes gloutons(2 s´ eances) . Propri´ et´ es NP , r´ eductions polynˆ omiales (2 s´ eances) . Heuristiques, M´ etaheuristiques (2 s´ eances) Organisation: les TPs Il y aura 6 s´ eances de TP (langage : Java) encadr´ ees pour la mise en oeuvre directe des m´ ethodes ´ etudi´ ees en cours: . Programmation dynamique, Algorithmes gloutons(2 s´ eances) . Propri´ et´ es NP , r´ eductions polynˆ omiales (2 s´ eances) . Heuristiques, M´ etaheuristiques (2 s´ eances) Organisation: les TPs Il y aura 6 s´ eances de TP (langage : Java) encadr´ ees pour la mise en oeuvre directe des m´ ethodes ´ etudi´ ees en cours: . Programmation dynamique, Algorithmes gloutons(2 s´ eances) . Propri´ et´ es NP , r´ eductions polynˆ omiales (2 s´ eances) . Heuristiques, M´ etaheuristiques (2 s´ eances) Organisation: les TPs Il y aura 6 s´ eances de TP (langage : Java) encadr´ ees pour uploads/Management/ algo-c0-p.pdf