Florian Renkin

Présentation

Comprendre la théorie et la pratique des langages rationnels :

• Expressions rationnelles
• Automates
• Algorithmes sur les automates

Présentation

Ce cours expose les notions de base de l'algorithmique, avec une emphase sur les calculs de complexité. La présentation des algorithmes de tri et des structures de données classiques (pour la plupart déjà introduits en classes préparatoires intégrées) sert de support à l'introduction de la notion de complexité et des différents outils mathématiques qui permettent de l'étudier.

Sujets centraux

• Introduction aux mesures de complexité (notations, théorème général, exemples du tri par insertion et du tri fusion)
• Autres tri comparatifs (sélection, tri par tas, tri rapide, tri introspectif)
• Borne de complexité des tris comparatifs
• Tris linéaires
• Rangs et médians (sélection stochastique, sélection en O(n))
• Structure de données classiques (tableaux statiques et dynamiques, listes, piles, files, files de priorité)
• Structures associatives (tables de hachage, arbre binaires de recherche, arbre rouge et noir)
• Principaux paradigmes algorithmiques :
  • Diviser pour régner (ex.: tri fusion, Karatsuba)
  • Programmation dynamique (ex.: distance de Levenshtein, chaîne de multiplications de matrices, plus longue sous-séquence commune)
  • algorithmes gloutons (ex.: distributeur de monnaie, codage de Huffman)

Présentation

L'objectif est de maîtriser le langage Java, principalement comme langage orienté objet mais aussi de découvrir quelques ajouts inspirés d'autres paradigmes.

Sujets centraux

• Pouvoir modéliser un système comme un ensemble d'objets
• Hiérarchiser les classes en utilisant l'héritage
• Créer un code générique
• Créer et traiter des exceptions
• Représenter un code source sous forme de diagramme de classes
• Connaître un ensemble de patrons de conception et les problèmes qu'ils résolvent