Ce cours est un entrainement à la résolution effective de problèmes algorithmiques. Effectué exclusivement en salle machines avec des séances TD de 3 heures hebdomadaires, le format des exercices est celui de l'ACM Programming Contest, un concours international de programmation en temps limité. La résolution de ces exercices demande une maîtrise des algorithmes théoriques, de leurs implémentations et de leurs performances. En particulier, vous serez confrontés au compromis à trouver entre temps d'exécution (effacité algorithmique de la solution codée) et temps de développement (réflexion, écriture, débugage).
La plateforme Online Judge sera utilisée pour fournir les exercices et valider les solutions. La validation sur ce serveur tient compte de la correction du code mais aussi de la vitesse d'exécution (un seuil de temps est imposé pour chaque exercice). Ces exercices ajoutent aussi une phase de compréhension et de modélisation du problème où il faut exploiter les informations des énoncés et se ramener à des problèmes classiques d'algorithmique. Plusieurs langages sont envisageables : C, C++, Java, Python. Par défaut le langage privilégié sera C++ avec utilisation de la librairie standard, mais le travail sera aussi accompagné et évalué pour tout autre choix de langage.
Ce cours peut donc être vu comme un accompagnement des cours ALGO1 et ALGO2, et une prolongation de PROG. Aussi bien pour l'algorithmique que pour la syntaxe des langages, des rappels pourront être donnés pendant tout le semestre. Les étudiants sont donc encouragés à interagir avec les encadrants du cours, pendant les séances et aussi par email entre les séances.
Ce cours est aussi une préparation aux compétititions de programmation pour ceux qui sont intéressés. Tous les ans, plusieurs équipes de 3 personnes sont choisies pour participer au concours ACM-ICPC. Les qualifications régionales se déroulent fin automne / début hiver. Plusieurs autres compétitions ont lieu sur l'année.
Les séances encadrées par Joël Felderhoff, Quoc Tung Le, Lucas Perotin, et Eric Thierry, auront lieu en salle E001 et 171 (avec ordinateurs locaux ou personnels) ou online (via Discord) les lundis de 13h15 à 16h15 (sauf exceptions, consultez-bien vos emails ou le pad L3).
Commencez par créer un compte sur Online Judge en notant bien votre mot de passe sur ce site. Connectez-vous sur ce site et récupérez votre Online Judge ID dans votre profil. Inscrivez-vous alors sur notre site (Inscription en haut à droite). Veillez à entrer le bon Online Judge ID, le bon email et ne perdez pas le mot de passe choisi sur notre site ! (indispensable pour rendre les TD et pour les examens)
La rubrique TD liste les exercices et la deadline de chaque TD. Le scoreboard vous permet de voir quels exercices ont été resolus. Allez aussi jeter un coup d'oeil aux liens utiles. Ce site a été mis en place par Théophile Trunck.
Un ensemble d'exercices à résoudre est proposé chaque semaine. La résolution s'effectue en cours puis à la maison si besoin. Un exercice est considéré résolu s'il est validé par Online Judge. Néanmoins nous jugerons aussi la lisibilité du code. La validation de ces exercices et la relecture de vos codes par les encadrants du cours donnera lieu à une note de contrôle continu. S'y ajouteront un partiel de mi-semestre et un examen final. La note finale sera une moyenne pondérée de toutes ces notes.
Les codes solutions de chaque semaine devront être rendus au plus tard le dimanche de la semaine suivante. Pour chaque exercice, le code sera stocké dans un fichier nommé avec la convention Prénom.Nom-NuméroExercice (par exemple pour le premier exercice eric.thierry-10055.cpp). Pour chaque TD, stocker tous vos fichiers sources dans un dossier intitulé TDnuméro-Prénom.Nom (par exemple pour le premier TD TD1-eric.thierry). Faites-en une archive et uploadez-la via le formulaire accessible en étant connecté au site (bouton Connexion, puis bouton Rendre TD). Si certains codes ne passent pas, commenter les en expliquant les soucis et vos hypothèses sur les erreurs commises.