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 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
La note de cette 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 des 2 notes de tutorats
- $TEST$ est la moyenne des tests de débuts de séances ($6$ tests).
- $DS$ est la moyenne des deux devoirs surveillées (DS1 et DS2)
- $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 relisez 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
Mardi : qu'est-ce qu'un algorithme
Vendredi : qu'est-ce que le code
Prérequis
- avoir python d'installé et savoir s'en servir (relisez la partie bases de python)
- 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 indispensables
- écrire du code, les parties :
Semaine 2
Mardi : écrire des algorithmes
Vendredi : écrire du code
Prérequis
Lire Espace de noms
Programme de la séance :
- Fin de la partie écrire du code : 3. projet pourcentages
- Déboguer ses programmes
- Pour aller plus loin : annales test code des années précédentes.
On vous remettra également le premier DM à rendre 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.
Semaine 3
Mardi : complexité algorithmique
Prérequis
Reprendre la partie complexité de votre cours de S1. Ce dont nous aurons besoin est rassemblé là :
N'hésitez pas à poser des questions en début de cours si vous avez des questions concernant les prérequis.
Parties abordées :
Vendredi : étude de l'exponentiation
Test de 15min en début de cours. Il faudra rendre plusieurs fichiers python (code et tests) sur AMeTICE.
Parties abordées dans le cours :
- Calculer $x^y$
- Pour aller plus loin : Les suites additives
Semaine 4
Mardi : complexité en moyenne et tris
Vendredi : projet tris
Test de 15min en début de cours. Il faudra rendre une feuille de papier avec des choses écrites dessus.
Semaine 5
Le DM1 est à rendre pour le vendredi 23/02/24 à 23h59
Mardi : Révision
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.
Vendredi : DS1
Au programme tout ce qu'on a vu en algorithmie jusque là. Sur feuille.
De 9h à 12h en amphi CARTAN.
Semaine 6 : Classes et objets
Début du temps 2 de cette UE, consacré à la programmation objet.
On vous donne aussi le sujet du DM à rendre pour le 29 mars.
Il faudra rendre un dossier contenant le projet vscode et les différents programmes.
Semaine 6.5 (semaine de vacances): Composition et agrégation
Il y a un prérequis pour la séance d'après les vacances.
- Terminer les deux projets et leurs améliorations :
- Lire et comprendre la partie Composition et agrégation, le test de début de cours portera dessus.
Semaine 7 : projet composition et agrégation
Test de 15min en début de cours consacré aux prérequis composition et agrégation. Il sera à rendre sur feuille.
Semaine 8
Mardi : Héritage
Vendredi : Projet Héritage
Semaine 9
Le DM1 est à rendre pour le vendredi 29/03/24 à 23h59
Mardi : principes de la programmation évènementielle
Vendredi : projet Arkanoid
Test de 15min en début de cours consacré à programmation objet. Il faudra rendre du code python (code et tests) sur AMeTICE.
Semaine 10
Mardi : Design patterns
TBD
Vendredi : DS 2
Semaine 11
Mardi : Structures de données Linéaires
Vendredi : Programmation dynamique
Semaine 12
Mardi : Algorithmes gloutons
Vendredi : Exercices
Semaine 13
Mardi : Problème du Sac à dos
Vendredi : Sac à dos, projet
Semaine 14 : Fichiers texte
TBD : pour 2024-25, à mettre en premier dans la partie développement. Y ajouter la partie interpréteur.
Semaine 15 : Gestion des données
Dernière semaine de cours. Le début de la séance sera consacrée aux questions et retour sur le cours, puis on terminera la séance sur la suite des fichiers.
Annales
Les annales des tests et contrôles de ce cours