« INFO704 : Analyse d'algorithmes » : différence entre les versions

Version du 10 octobre 2021 à 16:15

Responsable 2021: Sébastien Tavenas

Adresse couriel : sebastien.tavenas@univ-smb.fr

Problèmes

Problème 1 :

- Il y a N produits à acheter, chacun ayant un certain prix. Vous avez une somme E d'euros à votre disposition. Le but est d'obtenir le nombre maximum d'objets possible.

- Entrée : La première ligne indique le nombre de tests à réaliser. Chaque test commence par une ligne avec les valeurs N et E. La ligne suivante contient N entiers: la liste des prix des N produits. - Sortie : Le nombre de produits que l'on peut obtenir à chaque test. - Taille maximale des paramètres :

1. Hopcroft et Ullman, Introduction to automata theory, languages, and computation, (1979).
== TP ==
Dates provisoires :
- 22/25 septembre
- 9 octobre
- 16 octobre
TP1 les 22/25 septembre : Analyser la complexité d'algorithmes
- Sujet du TP 1
- Fichiers pour le TP
- Nécessité d'importer la librairie matplotlib
TP2 le 9 octobre : Problème NP-complet
- Sujet du TP 2 (Partie I)
- Exemples d'entrée
- Générateur aléatoire d'entrées
TP3 le 16 octobre : Réductions
- Sujet du TP 2 (Partie II)
- Esquisse de résolveur pour Clique
- Nécessité d'importer la librairie pycosat
!---
TP les 10 octobre et 6 novembre.
- Énoncé du TP, première partie : tp-part-1.pdf. Plus de détails pour chacuns des #trois sujets :
* tp-part-1-CHO.pdf
* tp-part-1-CHNO.pdf
* tp-part-1-3C.pdf
Voici aussi un exemple d'entrée pour chaque sujet :
* Graphe-vrai-CHO.pdf
* Graphe-vrai-CHNO.pdf
* Graphe-vrai-3C.pdf
-----
TP3 le 18 octobre : Réductions polynomiales
- Énoncé du TP, deuxième partie.
- Documents pour les réductions :
* Avro #Chapitre 10
* Cormen-Leiserson-Rivest-Stein #Coloration
* Cormen-Leiserson-Rivest-Stein HNO
(Attention la figure 34.16 est incorrecte. La remplacer par la figure 34.16 de la Version anglaise)
* Hon HO Version francaise
* Garey-Johnson HNO
* wiki proof
- Voici des exemples d'entrée pour 3SAT et Couverture par Sommets :
* 3SAT-vrai
* CS-vrai
* 3SAT-faux
* CS-faux
--
== Déroulement (2020) ==
Cours 1 (7 septembre) : Introduction
- Introduction
- Exemple de différents tris
- Notions d'instance et de problème
- Notion de complexité asymptotique
- Grand-O de la notation de Landau
TD 1 (10 septembre) : Analyses d'algorithmes
- Sujet du TD
- Fonctions mathématiques de base : polynômes, #exponentielles et logarithmes
Cours 2 (17 septembre) : Algorithmes récursifs (Diviser pour régner)
- Présentation des algorithmes Diviser-pour-régner.
- Théorème général.
- distance minimale
TD 2 (29 septembre) : Exercices d'analyse pour des algos récursifs ("Master Theorem")
- Exercices, complexité des fonctions #récursives.
- Solutions des questions 6 et 7.
- Solution de la question 5.
Cours 3 (2 octobre) : Programmation dynamique
- Algorithme récursif pour les nombres de Fibonacci
- Programme python pour le problème #de découpe de barres
- Algorithme de Levenshtein
- Présentation 'tablette' vue en #cours
TD 3 (5 octobre) : Exercices sur la programmation dynamique
- Sujet du TD
- Si besoin, problème du sous-tableau de somme maximale.
- Notes lors de la correction
Cours 4 (13 octobre) : Premières réductions algorithmiques
- Un liste de réductions algorithmiques entre différents problèmes
- Note sur les mathématiques derrière la #réduction de 3SUM vers 3COLLINEAR
!-- Réductions de NP-complétude
!-- - Problèmes NP-difficiles et NP-complets.
- Théorème de Cook-Levin. Cook-Levin
- Preuve de NP-Complétude. !-- : Couverture des arêtes et k-coloriage. --
--
!-- Complexité des problèmes
- Introduction aux classes de complexité.
!-- - Complexité d'un problème.
- Classe P.
!-- - Types de problèmes ( décision, optimisation, existence ). --
- Réduction polynomiale.
- Algorithme de vérification.
- Classe NP.
--
TD 4 (14 octobre) : Clique et consorts
- Réductions autour de Clique et NP-complétude de #Clique
- Notes sur le problème SAT
!-- Programmation dynamique
- Énoncé de TD.
- Correction sur la distance de Levenshtein.
--
Cours 5 (23 octobre, matin) : Classes de complexité et NP-complétude
- Petite introduction en survol de la NP-#complétude
- Notes de cours sur les classes #de complexité
- Petit Vrai/Faux sur la NP-complétude
- Hors programme : slides sur les classes de #complexité que j'avais utilisé lors d'une année antérieure quand je faisais la preuve du théorème de Levin-Cook
TD 5 (23 octobre, après-midi) : Classes de complexité et NP-complétude
- Énoncé du TD
- Problème du sac à dos
- Corrigé de l'exercice 3 du TD
== Annales Examen ==
Examen 2017
== Historique ==
Ce cours était donné précédemment par Xavier Provençal.
Ce cours est une refonte de INFO724 Algorithmique avancée, graphes et NP-complétude.

-->

@@ Ligne 10 : / Ligne 10 : @@
 - Taille maximale des paramètres :
+<!--
 #== Quelques ressources bibliographiques ==
 #
@@ Ligne 18 : / Ligne 19 : @@
 ## Wilf, Algorithms and Complexity, (1994). [http://www.math.upenn.edu/%7Ewilf/AlgoComp.pdf Disponible en ligne]
 ## Garey et Johnson, Computers and intractability a guide to the theory of NP-completeness. (1979).
-#<!-- # Paschos, Complexité et approximation polynomiale, (2004). -->
+#!-- # Paschos, Complexité et approximation polynomiale, (2004). -->
 ## Hopcroft et Ullman, Introduction to automata theory, languages, and computation, (1979).
 #
@@ Ligne 46 : / Ligne 47 : @@
 # - Nécessité d'importer la librairie pycosat
 #
-#<!---
+#!---
 #TP les 10 octobre et 6 novembre.
 #
@@ Ligne 74 : / Ligne 75 : @@
 #   * [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP3/Instances/CS_faux CS-faux]
 #
-#-->
+#--
 #
 #== Déroulement (2020) ==
@@ Ligne 120 : / Ligne 121 : @@
 # - Un liste de réductions algorithmiques entre différents problèmes
 # - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S7TD/Notes_red_3SUM_3Collinear.pdf Note sur les mathématiques derrière la #réduction de 3SUM vers 3COLLINEAR]
-#<!-- Réductions de NP-complétude
+#!-- Réductions de NP-complétude
 #!-- - Problèmes NP-difficiles et NP-complets.
 # - Théorème de Cook-Levin. [https://mycore.core-cloud.net/index.php/s/V9OUMtvnDuezpKl Cook-Levin]
 # - Preuve de NP-Complétude. !-- : Couverture des arêtes et k-coloriage. --
-#-->
+#--
-#<!-- Complexité des problèmes
+#!-- Complexité des problèmes
 # - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S8Cours/presentation1.0.pdf Introduction aux classes de complexité.]
 #!-- - Complexité d'un problème.
@@ Ligne 133 : / Ligne 134 : @@
 # - Algorithme de vérification.
 # - Classe NP.
-#-->
+#--
 #TD 4 (14 octobre) : Clique et consorts
 # - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S8Cours/Clique-EI-CS.pdf Réductions autour de Clique et NP-complétude de #Clique]
 # - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S8Cours/ProblemeSAT.pdf Notes sur le problème SAT]
-#<!-- Programmation dynamique
+#!-- Programmation dynamique
 # - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S7TD/TD-prog_dynamique.pdf Énoncé de TD.]
 # - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S8Cours/Levenshtein.pdf Correction sur la distance de Levenshtein.]
-#-->
+#--
 #
 #Cours 5 (23 octobre, matin) : Classes de complexité et NP-complétude
@@ Ligne 162 : / Ligne 163 : @@
 #Ce cours est une refonte de [http://lama.univ-savoie.fr/mediawiki/index.php/INFO724_:_Algorithmique_avanc%C3%A9e,_graphes_et_NP-#Compl%C3%A9tude INFO724 Algorithmique avancée, graphes et NP-complétude].
 #
+-->

« INFO704 : Analyse d'algorithmes » : différence entre les versions

Version du 10 octobre 2021 à 16:15

Problèmes

Menu de navigation

Rechercher

« INFO704 : Analyse d'algorithmes » : différence entre les versions