S2 : Programmation et Algorithmes

Ce cours intitulé Programmation et algorithmes est donné au second semestre de la licence MPCI (lien AMeTICE AMU Informatique S2). Il s'appuie sur le cours de Programmation donné au S1 (lien AMeTICE AMU Informatique S1).

Ce cours montrera l'informatique sous trois aspects complémentaires — théorie, code et algorithmes — que tout honnête informaticien devrait connaître. Il s'adresse à des personnes ayant des connaissances minimales en informatiques mais voulant (ou étant obligé d' 🙂) approfondir le sujet. Nous rentrerons dans les détails tant d'un point de vue algorithmique (Tout algorithme sera démontré) que d'un point de vue code (on montrera comment un programme s'exécute sur un ordinateur).

L'informatique est une science incarnée : elle nécessite à la fois de solides connaissances théoriques pour concevoir des algorithmes efficaces et des capacités d'expérimentation et de rigueur pour les mettre en oeuvre et les faire fonctionner sur un ordinateur.

Cela va vous demander un travail personnel important pour comprendre et assimiler les bases théoriques et un temps certain d’expérimentation pour faire fonctionner le tout sur votre ordinateur en comprenant pourquoi et comment cela fonctionne.

Note

Le cours est composé de deux UEes, l'une consacrée à l'algorithmie, l'autre à la programmation. La note de chaque UE résulte de cette formule :

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

Avec :

• $CC = \frac{1}{2}(TUT + TEST)$ où :
  • $TUT$ est la moyenne formée de la note de tutorat
  • $TEST$ est la moyenne des tests de débuts de séances.
• $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.

Algorithmie

Avoir une notion de ce qu'est une variable, une instruction et une fonction. Aucun autre prérequis algorithmique n'est nécessaire.

Programmation

Il est nécessaire d'avoir des bases de python pour commencer ce cours.

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
• Programmation objet

Semaine 1

19/01 au 23/01

Algorithmie

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

26/01 au 30/01

Programmation

Il est INDISPENSABLE que vous ayez en tête ce que vous avez fait en développement au S1. Pour cela, suivez et faite la partie suivante du cours qui explicite les notions qui vous seront utiles pour débuter ce semestre :

Mercredi : projet de développement

2h

Notions abordées :

• base système : dossiers, fichiers et programmes
• utilisation du terminal
• écrire du code python utilisable et maintenable

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

Vendredi : exercices

2h

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

Pour aller plus loin :

Semaine 3

02/02 au 06/02 Algorithmie

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

2h

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 7

9/03 au 13/03 Programmation

TBD DM2 = et d'algo de l'année dernière

Mercredi : programmation objet

2h

Cours Valentin :

• objet
• héritage

Vendredi : on s'entraîne

4h

Semaine 8

16/03 au 20/03 Programmation

Mercredi : Composition et agrégation

2h

Vendredi : on s'entraîne

2h

Semaine 9

23/03 27/03 Programmation

Mercredi : héritage

2h

pour aller plus loin : design pattern

Vendredi : on s'entraîne

2h

Semaine 10

30/03 au 3/03 Algorithmie

Mercredi : structures de données

2h

• structures de données.

Vendredi :on s'entraîne

2h

• pile/file et listes chaînées. Cours puis exercices dessus.

Semaine 11

16/03 au 20/03 Algorithmie

Mercredi : listes

2h

Vendredi : dictionnaires

2h

Semaine 11

13/04 au 17/04 Algorithmie

Mercredi : Problème de l'enveloppe convexe

Vendredi : on s'entraîne

TBD avec pyglet et/matplotlib

Semaine 12

2h

Semaine 13

04/05 au 08/05 Programmation

présrequis : avoir fait du html/css/js pendant les vacances. En faire un DM.

Mercredi : serveur web et réseau

Vendredi : on s'entraîne

Annales

Les annales des tests et contrôles de ce cours