Le cours LOG675 permet aux étudiant(e)s le suivant:

• Choisir les structures de données adéquates pour la résolution de problèmes
• Améliorer leurs compétences en conception d'algorithmes et résolution de problèmes
• Développer des programmes efficaces et fiables
• Pratiquer leurs compétences de travail d'équipe dans des compétitions de programmation
• Bien gérer leur temps avec des délais serrés

Le cours comprend:
- Un cours magistral par semaine, couvrant les aspects théoriques ainsi que des exemples et exercices (3 heures)
- Une séance de laboratoire par semaine, permettant aux étudiants de se préparer pour les compétitions (2 heures)

Ci-dessous se trouve le plan de cours prévu avec les heures approximatives d'enseignement pour chaque sujet, incluant le temps alloué pour une compétition de groupe et l'examen intra (compétition individuelle). Des modifications et ajustements au plan du cours pourront avoir lieu durant la session.

1. Introduction à la programmation compétitive (3.5 heures)
   • Introduction aux compétitions et platformes existantes
   • Comment être compétitif
2. Structures de données (SD) (7 heures)
   • SD linéaires avec librairies intégrées
   • SD non linéaires avec librairies intégrées
   • SD avec nos propres librairie
3. Chaines (3.5 heures)
   • Algorithmes de recherches de sous-chaine
   • Arbre et tableau de suffixe
4. Paradigmes de résolution de problèmes (5.5 heures)
   • Recherche exhaustive
   • Diviser pour régner
   • Algorithmes gloutons
   • Programmation dynamique
5. Graphes (5 heures)
   • Algorithmes de parcours de graphes
   • Arbre couvrant de poids minimal
   • Problème du plus court chemin avec source unique
   • Problème de toutes les paires de plus courts chemins
   • Graphes spéciaux
6. Analyse combinatoire (2.5 heures)
   • Nombres de Fibonacci
   • Coefficients binomiaux
   • Nombres Catalans
7. Autres sujets mathématiques (1.5 heure)
   • Probabilités
   • Théorie de jeu
8. Théorie des nombres (3.5 heures)
   • Nombres premiers
   • Décomposition en facteurs premiers
   • Crible d'Érastosthène
   • PGCD et PPCM
   • Factoriel
   • Arithmétique modulaire
   • Algorithme d'Euclide étendu
9. Géométrie (3.5 heures)
   • Objets géométriques de base
   • Périmètre et aire d'un polygone
   • Test de convexité d'un polygone
   • Emplacement d'un point par rapport à un polygone
   • Découpage d'un polygone avec une droite
   • Enveloppe convexe
10. Sujets divers (3.5 heures)
    • Algorithmes de recherche avancés
    • Problème du flot maximum
    • Couplage d'un graphe

Tous les cours sont d'une durée de 3 heures et 30 minutes par semaine (incluant une pause de 30 minutes).

Les étudiant(e)s utiliseront un outil de développement logiciel intégré (IDE) pour développer des logiciels.

Note importante: Les exemples de cours seront en Java. Les exercices, laboratoires, devoirs et compétitions sont vérifiés en Java et en Python. Vous pouvez ainsi choisir un de ces deux langages pour les évaluations.

Dates et modalités :

Veuillez noter qu’une moyenne inférieure à 50% dans les évaluations individuelles de type "examen" (examens intra et final) entraîne automatiquement un échec au cours. Ceci est une condition nécessaire mais non suffisante pour réussir ce cours.

Les devoirs remis en retard auront une pénalité de 15% par jour de retard pour un maximum de deux jours. Une soumission avec un retard de plus que deux jours ne sera pas corrigée.

Afin de faire valider une absence à une évaluation en vue d’obtenir un examen de compensation, l’étudiante ou l’étudiant doit utiliser le formulaire prévu à cet effet dans son portail MonÉTS pour un examen final qui se déroule durant la période des examens finaux ou pour tout autre élément d’évaluation surveillé de 15% et plus durant la session. Si l’absence concerne un élément d’évaluation de moins de 15% durant la session, l’étudiant ou l’étudiante doit soumettre une demande par écrit à son enseignante ou enseignant.

Toute demande de validation d’absence doit se faire dans les cinq (5) jours ouvrables suivant la tenue de l’évaluation, sauf dans les cas d’une absence pour participation à une activité prévue aux règlements des études où la demande doit être soumise dans les cinq (5) jours ouvrables avant le jour de départ de l’ÉTS pour se rendre à l’activité.

Toute absence non justifiée par un motif majeur (voir articles 7.2.6.1 du RÉPC et 6.5.2 du RÉCS) entraînera l’attribution de la note zéro (0).

Aucune documentation obligatoire.

• S. Halim, F. Halim, S. Effendy “Competitive Programming 4 – Book 1", Lulu Independent Publish, 2020
• S. Halim, F. Halim, S. Effendy “Competitive Programming 4 – Book 2", Lulu Independent Publish, 2020
• S. Skienna, M. Revilla, "Programming Challenges", Springer Verlag, 2003
• T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, "Introduction to Algorithms (Fourth Edition)", MIT Press, Cambridge, MA, 2022

Site Moodle/ENA du cours: https://ena.etsmtl.ca/course/view.php?id=25403