S2 : Programmation et Algorithmes
- formation
- MPCI
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
Prérequis
Avoir relu et compris les bases de la programmation. En particulier :
- avoir python d'installé et savoir s'en servir
- fait le tutoriel de prise en main de l'éditeur vscode
N'hésitez pas à poser des questions en début de cours si vous avez des questions concernant les prérequis.
Parties abordées :
- Connaissances systèmes indispensables
- écrire du code, les parties :
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
Test de 15min en début de cours sur la partie preuve et création d'algorithmes. Il faudra rendre une feuille de papier.
Ce cours est basé sur la notion de complexité algorithmique que vous avez du aborder au S1.
Prérequis
Reprendre la partie complexité de votre cours de S1.
N'hésitez pas à poser des questions en début de cours si vous avez des questions concernant les prérequis.
Parties abordées :
Si on a le temps, on le fait en cours sinon faites le chez vous :
Vendredi : stockage de données
On vous remettra également le premier DM à rendre pour le 28 février 23h59 sur AMeTICE au format Markdown.
Il faudra rendre un dossier contenant :
- un dossier contenant le rendu de la partie algorithmie. Il devra être sous la forme d'un fichier markdown et de sa conversion en html.
- un dossier contenant le rendu de la partie code contenant le projet vscode et les différents programmes.
Comment conserver et accéder à des données :
Cas particulier du texte :
On s'entraîne :
Pour aller plus loin, vous pouvez regarder :
Le reste du cours sur les fichier et dossiers
Semaine 4
11/02 au 14/02
Test de 15min en début de cours sur la partie code (main/fonctions/tests). Il faudra rendre des fichiers sur AMeTICE.
Plan de la séance :
Pour aller plus loin :
Semaine 5
24/02 au 28/02
Mercredi : tris TD
Test de 15min en début de cours sur la partie complexité.
Sujet du test 3
Sujets abordés :
Introduction aux algorithmes de tri :
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
Rendre le DM 1.
Sujet DM2
On code ce qu'on a vu mercredi :
Semaine 6
03/03 au 07/03
2h mercredi : listes, dictionnaires et piles (introduction à la complexité amortie) 2h vendredi : Structures de données TP (décurryfication, liste et dictionnaires)
Semaine 7
10/03 au 14/03
2h mercredi : gloutons cours 2h vendredi : gloutons TD
Semaine 8
DS algorithmie 2h , mardi 18/03.
17/03 au 21/03
2h mercredi : classes et objets 2h vendredi : tp objet + code coverage
Semaine 9
Rendre DM2
Sujet DM3 : algorithmie
24/03 au 28/03
2h mercredi : composition / agrégation 2h vendredi : environnement virtuels
Semaine 10
31/03 au 04/04
2h mercredi : héritage 2h vendredi : TP
TBD : tp programmation par les tests à faire chez eux
Rendre DM3
Semaine 11
14/04 au 18/04
4h mercredi : programmation événementielle
Sujet DM4 : programmation évènementielle.
Semaine 12
21/04 au 25/04 4h mercredi : P&NP 2h vendredi : méthode de résolution de problèmes
Semaine 13
DS code 3h, lundi 05/05.
Rendre DM4
05/05 au 09/05 4h mercredi : méthode de résolution de problèmes fin
Annales
Les annales des tests et contrôles de ce cours