Au terme de ce cours, l’étudiant ou l'étudiante aura vu les aspects nouveaux et cruciaux en génie logiciel.

Stratégies technologiques pertinentes liées à la planification, à la conception ou à la gestion des systèmes logiciels actuels ou proposés par les industries qui évoluent dans le domaine du génie logiciel.

• Programmation compétitive

Étude des aspects nouveaux et d'intérêt majeur en génie logiciel. Les concepts abordés couvrent les stratégies technologiques pertinentes liées à la planification, à la conception ou à la gestion des systèmes matériels ou logiciels actuels ou proposés par les industries qui évoluent dans le domaine de génie logiciel.

Le cours LOG780 offert à la session H-2023 portera spécifiquement sur la Programmation Compétitive.

Ce cours 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)

Le cours sera dispensé en mode hybride. Les séances à distance seront confirmées sur moodle.

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.

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 (Third Edition)", MIT Press, Cambridge, MA, 2009

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