S2 : Algorithmie 1 (bases)

Ce cours intitulé Algorithmie est donné au second semestre de la licence MPCI (lien AMeTICE AMU Informatique S2).

Note

La note de l'UE résulte de cette formule :

$$ \max (\frac{CC+ DS + ET}{3}, ET) $$

Avec :

• $CC = \frac{1}{4}(TUT + \sum TEST)$ où :
  • $TUT$ est la moyenne formée de la note des 2 tutorats
  • $\sum TEST$ est la somme des autres notes de contrôle continu
• $DS$ est la note du devoir surveillé
• $ET$ est l'examen terminal

Prérequis

Il est nécessaire d'avoir quelques prérequis avant de commencer ce cours, en particulier vos cours d'informatique du S1 qui vous permettrons de coder en python les différents algorithme que ous allons étudier.

Tout ce dont vous aurez besoin est également disponible dans le cours cours ci-après :

Programmer nécessite d'utiliser le web pour lire la doc, técharger des modules, etc. Configurez votre ordinateur pour qu'il puisse utiliser le réseau universitaire EDUROAM :

Cours

Le cours est disponible via le site d'AMeTICE et en suivant les liens de chaque partie ci-après. Cela ne vous dispense pas de prendre des notes, mais vous aide à la révision ou aux divers prérequis que vous aurez à préparer avant le cours.

Plan

Ce cours est composée de plusieurs parties :

• Notion d'algorithmie
• Complexité d'un complexité
• Structures de données

Semaine 1

Mercredi : qu'est-ce qu'un algorithme

2h

Notions abordées :

• définition d'un programme et d'un algorithme
• savoir ce que fait un programme :
  • il faut toujours démonter qu'un programme s'arrête
  • il faut toujours démontrer ce que fait un algorithme
• ce que ne peut pas faire un algorithme

Vendredi : écrire des algorithmes

4h

Notions abordées :

• écrire des algorithme en pseudo-code (et thèse de Church-Turing)
• algorithmes itératif et récursifs
• prouver un algorithme

Si on a le temps, sinon à faire chez soit :

Pour aller plus loin :

Semaine 2

Mercredi matin : complexité

2h

Notions abordées :

• définition
• complexité spatiale et temporelle
• calculs de $\mathcal{O}$ et cas particulier de $\mathcal{O}(1) = \Theta(1) = \Omega(1)$
• différence et usage de $\Theta$, $\Omega$ et $\mathcal{O}$
• règles pour calculer la complexité d'algorithmes itératifs et récursifs

mercredi après-midi : exercices

4h

Semaine 4

16/02 au 20/02 Algorithmie

Mercredi : complexité d'un problème

2h

Notions abordées :

• complexité d'un problème
• comment trouver une borne minimum

Si on a le temps, sinon à faire chez soit :

Pour aller plus loin :

Jeudi : problème de l'exponentiation

2h

Si on a le temps, on commencera le DM :

Pour aller plus loin :

Semaine 5

09/02 au 13/02 Algorithmie

Mercredi : tris

4h

Vendredi : correction du DM

2+h

Séance facultative. Venez si vous voulez voir la correction du DM et/ou avez des questions d'ordre algorithmique/code.

Semaine 6

2h

Pour accélérer vos calculs de complexité :

Pour vous entraîner sur des exercices classiques :

Enfin, pour aller plus loin, n'hésitez pas à vous entraîner sur les DS1 des années précédentes dans les annales. Comme toujours, faites les exercices avant de regarder les corrigés et qui sait vous allez peut-être même y prendre du plaisir, certains exercices étant diablement jolis.

Semaine 11

6/04 au 10/04 Algorithmie

Jeudi : structures de données

2h

Vendredi : structures linéaires

4h

Semaine 12

13/04 au 17/04 Algorithmie

Mercredi : Listes

Vendredi : Dictionnaires

Si on a le temps, sinon à faire chez vous :

Semaine 13

27/04 au 1/05 Programmation

Annales

Le cours était lié au cours de programmation. Les annales concernent donc les 2 matières. Prenez celle qui concerne l'algorithmie.