INFO003 C1 : Analyse d'algorithmes

Responsable 2022 : Sébastien Tavenas
Adresse courriel : sebastien.tavenas@univ-smb.fr

Quelques ressources introductives :

• Introduction
• Grand-O de la notation de Landau
• Fonctions mathématiques de base : polynômes, exponentielles et logarithmes

Des ressources sur la complexité d'un algorithme récursif :

• Théorème général
  
• Exercices sur la complexité des fonctions récursives
  
• Correction de l'exercice 4
  
• distance minimale

Programmation dynamique :

• Programme de découpe de barres
• Levenshtein (vous pouvez utiliser le fichier animaux comme dictionnaire)

Problème de livraison par drones :

Ancien sujet de TP
algorithmes
Exemples d'entrées : Taille 10, Taille 15, Taille 20, Taille 100

Autour de la NP-complétude

Notes sur les classes P et NP
Exercices sur la NP-complétude
Examen du cours donné en 2020

TP1 :

Énoncé
Vous pouvez (conseillé) utiliser les outils suivants :
graphChronoGenerator.py et parametresGraphChronoGenerator.json
Les fichiers précédents permettent de de ne pas mesurer le temps de génération des entrées et seulement le temps de calcul, mais en cas de soucis, vous pouvez utiliser ces (petites) variations :
graphChrono.py et parametresGraphChrono.json

Fichiers pour le problème 1

• Trame (en fonction de votre langage) : c++, python, java, c#
• Générateur d'entrées

Fichiers pour le problème 2

• Générateur d'entrées : Générateur d'entrées
• Exemple d'entrée : Exemple de taille 25

Fichiers pour le problème 3

• Générateur d'entrées : Générateur d'entrées
• Exemple d'entrée : Exemple de taille 10, Exemple de taille 23, Exemple de taille 100

TP2 :

Énoncé partie 1
Un générateur d'entrées ainsi que des entrées toutes faites sont données :
generator.py,
3C_vrai.txt, 3C_vrai20.txt, 3C_vrai25.txt, 3C_faux20.txt.

Énoncé partie 2
Des templates pour l'utilisation des SAT-solvers Picosat et Pycosat sont donnés:
Template pour c++, Template pour Python