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érimentations 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 devoirs surveillé
• $ET$ est l'examen terminal

Prérequis

Il est nécessaire d'avoir quelques prérequis avant de commencer ce cours.

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. Il est indispensable que vous relisiez le cours ci-après pour s'assurer que vous avez bien les bases nécessaires en programmation 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
• Méthodes de résolution de problèmes

Semaine 1

20/01 au 24/01

Mercredi : qu'est-ce qu'un algorithme

Vendredi : qu'est-ce que le code

Parties abordées :

Semaine 2

27/01 au 31/01

Mercredi : écrire des algorithmes

Si on a le temps, on le fait en cours sinon faites le chez vous :

Vendredi : écrire du code

Si on a le temps, on le fait en cours sinon faites le chez vous :

Semaine 3

03/02 au 07/02

Mercredi : complexité algorithmique

Ce cours est basé sur la notion de complexité algorithmique que vous avez du aborder au S1.

Parties abordées :

Si on a le temps, on le fait en cours sinon faites le chez vous :

Vendredi : stockage de données

Comment conserver et accéder à des données :

Cas particulier du texte :

On s'entraîne :

Pour aller plus loin, vous pouvez regarder :

Semaine 4

11/02 au 14/02

Plan de la séance :

Pour aller plus loin :

Semaine 5

24/02 au 28/02

Semaine basée sur les tris.

Mercredi : tris TD

Sujets abordés :

L'analyse de ces algorithme simple nous permettra de formaliser la notion de complexité en moyenne :

Puis on abordera des notion plus avancées du tri :

Vendredi : tris TP

On code ce qu'on a vu mercredi :

Semaine 6

03/03 au 07/03

Mercredi : Liste/dictionnaires et piles

Analyse de structures de données fondamentales en algorithmie :

Un autre type de complexité, très utile pour l'analyse de structures complexes et que l'on a utilisé pour les listes :

N'hésitez pas à aller jeter eu coup d'œil aux exercices sur les piles et les files :

Vendredi : Fonctions de hachages et dictionnaires

Semaine 7

10/03 au 14/03

Venez avec vos questions d'algorithmie, de complexité et de preuves. On passera la séance à caler les notions du DS et à s'entraîner avec des exercices mercredi et vendredi.

Mercredi : algorithmes classiques

On passera la séance de TD à résoudre des algorithmes classiques :

Vendredi : Jolis DS

Ayez déjà commencé vos révisions. On répondra aux questions que vous vous posez sur les anciens DS et ET (et il y en a des jolis) d'algorithmie.

Semaine 8

17/03 au 21/03

Mercredi : classes et objets

Vendredi : on s'entraîne puis composition et agrégation

On s'entraîne :

Puis :

Semaine 9

24/03 au 28/03

Mercredi : on s'entraîne

On s'entraîne :

Vendredi : héritage

Pour aller plus loin, amélioration des dès et des cartes :

Semaine 10

31/03 au 04/04

Mercredi : projet héritage

On s'entraîne sur l'héritage :

Vendredi : Méthodes de résolution de problèmes

On refait de l'algorithmie :

Semaine 11

14/04 au 18/04

On se focalise sur une méthode particulière de design d'algorithme, les algorithmes gloutons :

Semaine 12

21/04 au 25/04

Mercredi : Sac à dos

Au programme, on prépare les vacances et son sac-à-dos :

Vendredi : Enveloppe convexe

Semaine 13

Annales

Les annales des tests et contrôles de ce cours