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

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

DS 1

TBD mettre des exercices pour s'entraîner (ie ds des années précédentes corrigés).

Annales

Les annales des tests et contrôles de ce cours