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

Version du 18 septembre 2019 à 06:10

Responsable 2019: Sébastien Tavenas

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

Quelques ressources bibliographiques

Ouvrage de référence :

Cormen, Leiserson, Rivest et Stein, Algorithmique, 3e edition (2009). ( Aussi appelé "Introduction à l'algorithmique" pour les deux premières éditions )

Autres références bibliographiques :

Wilf, Algorithms and Complexity, (1994). Disponible en ligne
Garey et Johnson, Computers and intractability a guide to the theory of NP-completeness. (1979).
Hopcroft et Ullman, Introduction to automata theory, languages, and computation, (1979).

TP

TP1 le 25 septembre : Analyser la complexité d'algorithmes

TP2 le 9 octobre : Problème NP-complet

TP3 le 18 octobre : Réductions polynomiales

Déroulement (2019-2020)

Cours 1 (10 septembre) : Introduction

- Exemple de différents tris 
- Notions d'instance et de problème
- Notion de complexité asymptotique

Cours 1 (9 septembre) : Introduction

TD 1 (13 septembre) : Rappels de mathématiques

- Grand-O de la notation de Landau
- Fonctions mathématiques de base : polynômes, exponentielles et logarithmes
- Correction des questions 2 et 3 du TD

TD2 (16 septembre) : Analyse des algorithmes

- Complexité d'éléments basiques : instructions, tests, boucles Pour et TantQue
- Cas des algorithmes récursifs.
- Analyse des algorithmes

Cours 2 (18 septembre) : Algorithmes récursifs (Diviser pour régner)

- Présentation des algorithmes Diviser-pour-régner.
- Théorème général.

TD 3 (23 septembre) : Algorithmes récursifs (Diviser-pour-régner)

- Problème de la multiplication de grands entiers.

Cours 3 (30 septembre) : Programmation dynamique.

TD 4 (30 septembre) : Programmation dynamique

Cours 4 (1 octobre) : Complexité des problèmes

Cours 5 (7 octobre) : Réductions de NP-complétude

TD 5 (15 octobre) : NP-complétude

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 1 : / Ligne 1 : @@
- Responsable 2018: Sébastien Tavenas
+ Responsable 2019: Sébastien Tavenas
 Adresse couriel : sebastien.tavenas@univ-smb.fr
@@ Ligne 17 : / Ligne 17 : @@
 == TP ==
+TP1 le 25 septembre : Analyser la complexité d'algorithmes
-TP1 le 17 octobre
+<!--
  '''Seuls les deux premiers problèmes suffisent pour avoir la note maximale!!!'''
  - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP1/tp1_enonce.pdf Énoncé du TP]
  - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP1/fichiersTP1 Fichiers relatifs au TP1]
+-->
-TP2 le 19 octobre
+TP2 le 9 octobre : Problème NP-complet
+<!--
  - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/SurWiki Fichiers relatifs au TP2]
+-->
 <!---
@@ Ligne 38 : / Ligne 42 : @@
 ----->
+TP3 le 18 octobre : Réductions polynomiales
-TP3 le 9 novembre
+<!--
  - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP3/tp-part-2.pdf Énoncé du TP, deuxième partie].
  - Documents pour les réductions :
@@ Ligne 52 : / Ligne 57 : @@
    * [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP3/Instances/3sat_faux 3SAT-faux]
    * [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP3/Instances/CS_faux CS-faux]
+-->
+== Déroulement (2019-2020) ==
-== Déroulement (2018-2019) ==
 Cours 1 (10 septembre) : [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S1Cours/CM1.pdf Introduction]
@@ Ligne 64 : / Ligne 69 : @@
 -->
-TD 1 (14 septembre) : Rappels de mathématiques
+Cours 1 (9 septembre) : Introduction
+TD 1 (13 septembre) : Rappels de mathématiques
  - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S2TD/grandO.pdf Grand-O de la notation de Landau]
  - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S2TD/rappelsLog.pdf Fonctions mathématiques de base : polynômes, exponentielles et logarithmes]
  - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S2TD/Correction_exercices_2et3.pdf Correction des questions 2 et 3 du TD]
-TD2 (18 septembre) : Analyse des algorithmes
+TD2 (16 septembre) : Analyse des algorithmes
  - Complexité d'éléments basiques : instructions, tests, boucles Pour et TantQue
  - Cas des algorithmes récursifs.
@@ Ligne 80 : / Ligne 87 : @@
  - [http://lama.univ-savoie.fr/~provencal/enseignement/INFO704/distance_min.pdf Problème du calcul de la distance minimum entre deux points]. -->
-Cours 2 (21 septembre) : Algorithmes récursifs (Diviser pour régner)
+Cours 2 (18 septembre) : Algorithmes récursifs (Diviser pour régner)
  - Présentation des algorithmes Diviser-pour-régner.
  - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S4Cours/fct_rec.pdf Théorème général.]
-TD 3 (24 septembre) : Algorithmes récursifs (Diviser-pour-régner)
+TD 3 (23 septembre) : Algorithmes récursifs (Diviser-pour-régner)
+<!--
  - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S5TD/Solution-TD.pdf Correction des derniers exos de la feuille de TD.]
+-->
 <!--
  - Comparaison d'approches naïves VS diviser-pour régner (théorie et implémentation).
@@ Ligne 92 : / Ligne 101 : @@
  <!-- - [http://lama.univ-savoie.fr/~provencal/enseignement/INFO704/graphChrono.tgz Deuxième version du script graphChrono.py pour fabriquer une courbes des temps de calcul (utilise gnuplot)]. -->
-Cours 3 (1 octobre) : Fin correction "Diviser pour régner" + Début programmation dynamique.
+Cours 3 (30 septembre) : Programmation dynamique.
 <!-- - Problème de la distance minimum dans un nuage de points. [https://mycore.core-cloud.net/index.php/s/fh9C1oJ4HymuJI0 Distance]
  - Problème du rendu de monnaie. [https://mycore.core-cloud.net/index.php/s/taOj7Moq8gDy9vz Rendu monnaie]
@@ Ligne 104 : / Ligne 113 : @@
 -->
-TD 4 (5 octobre) : Programmation dynamique
+TD 4 (30 septembre) : Programmation dynamique
-Cours 4 (8 octobre) : Complexité des problèmes
+Cours 4 (1 octobre) : Complexité des problèmes
 <!-- - Complexité d'un problème.
  - Classe P.
@@ Ligne 115 : / Ligne 124 : @@
 -->
-Cours 5 (9 octobre) : NP-complétude
+Cours 5 (7 octobre) : 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]
@@ Ligne 121 : / Ligne 130 : @@
 -->
-TD 5 (19 octobre) : NP-complétude
+TD 5 (15 octobre) : NP-complétude
 == Annales Examen ==

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

Version du 18 septembre 2019 à 06:10

Sommaire

Quelques ressources bibliographiques

TP

Déroulement (2019-2020)

Annales Examen

Historique

Menu de navigation

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

Version du 18 septembre 2019 à 06:10

Quelques ressources bibliographiques

TP

Déroulement (2019-2020)

Annales Examen

Historique

Menu de navigation

Rechercher

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