EPREUVE ORALE PRATIQUE D'ALGORITHMIQUE ET PROGRAMMATION ... ?· EPREUVE ORALE PRATIQUE D'ALGORITHMIQUE…

  • Published on
    12-Sep-2018

  • View
    212

  • Download
    0

Embed Size (px)

Transcript

<ul><li><p>EPREUVE ORALE PRATIQUE D'ALGORITHMIQUE ET PROGRAMMATION </p><p>ENS : PARIS LYON CACHAN </p><p>Coefficients : PARIS 4 LYON 4 CACHAN 6 MEMBRES DE JURYS : Yves Robert, Benot Caillaud, Damien Mass </p><p>Comme l'anne dernire, cette preuve demandait aux candidats de mettre en uvre la chane complte de rsolution d'un problme informatique: analyse des spcifications, choix des structures de donnes, mise en forme et valuation de l'algorithme et de sa complexit, programmation sur machine et test des programmes. En plus de la partie programmation, la prsentation orale permettait d'valuer les candidats sur leur capacit expliquer leurs approches et solutions. </p><p> Le jury a examin cette anne 114 candidats1 (dont 2 de filire PC), sur 5 sessions organises comme l'anne prcdente en pipeline : les candidats d'une session commune arrivent par groupe de 3 toutes les demi-heures, de sorte que les derniers arrivs rentrent avant que les premiers n'aient fini leur prsentation orale. Une fois encore, le jury a fait un barme rpartissant les points galit entre la partie rsultats pratiques et la prsentation des algorithmes l'oral. </p><p> Comme l'anne dernire, plusieurs langages et environnements de programmation taient proposs : PC sous Windows 2000, avec CamlLight, Objective Caml, Maple, Java ou Pascal (Delphi). PC sous Debian/Linux KDE, avec Caml Light, Objective Caml, C, MuPad et Java. Il tait demand aux candidats de choisir le langage et l'environnement l'avance. Plus encore qu'en 2005, CamlLight sous Windows a t trs majoritairement choisi: 71 % des tudiants ont opt pour cet environnement, 13 % des tudiants ont choisi CamlLight ou Ocaml sous Linux, 10 % ont choisi Pascal sous Windows, 4 % C sous Linux, et 2 % ont choisi Maple sous Windows. Encore une fois, ni Java ni MuPad n'ont t choisi. Plusieurs sujets proposaient plusieurs tailles pour le problme rsoudre. Le but tait la fois de permettre l'utilisation d'algorithmes nafs peu efficaces pour rsoudre la taille moyenne, et d'inciter les candidats tester leur programme sur des petites valeurs solubles la main (ce que beaucoup de candidats ont fait). Dans le cas o le sujet ne proposait pas plusieurs tailles, les candidats devaient tester leurs programmes de leur ct. Le jury rappelle une fois de plus l'importance pour les candidats d'apprendre tester et corriger leur programme, en utilisant ventuellement des commandes d'affichage pour tracer l'excution de l'algorithme. Quelques remarques gnrales : </p><p> Les candidats (surtout sous Caml) utilisent beaucoup les structures de liste chane (ou, plus </p><p>gnralement, des types de donnes rcursifs). Si celles-ci peuvent tre trs utiles, elles peuvent aussi se rveler handicapantes et lourdes grer. Ds lors qu'ils ne sont pas inadapts et que le nombre maximum d'lments est connu, prfrer l'utilisation d'un tableau ou d'une matrice, mme pour reprsenter une structure complexe comme un arbre (comme pour le sujet Apprentissage de Langages Rguliers). </p><p> 1</p><p>Dont 7 candidates, ce qui reprsente une trs lgre augmentation par rapport 2005. </p></li><li><p> De la mme faon, l'utilisation de la rcursivit est parfois trs utile et de nombreux candidats matrisent bien cette technique de programmation, mais tous les algorithmes ne s'y ramnent pas. De nombreux problmes peuvent se rsoudre plus facilement l'aide de boucles, et le jury encourage les candidats programmer aussi des algorithmes itratifs en Caml. </p><p> Les sujets ont probablement t plus longs que l'an pass, et l'exception du sujet Objets Gomtriques Planaires Iso-orients, n'ont t achevs par aucun candidat. Nanmoins, tous les sujets disposaient de questions de difficults croissantes permettant de tester les capacits des diffrents candidats. Voici maintenant des commentaires pour chacune des preuves: Objets gomtriques planaires iso-orients: Le but de ce sujet tait de montrer comment des </p><p>structures de donnes bien conues permettaient d'optimiser certains algorithmes. Tous les problmes pouvaient ainsi tre rsolus avec une complexit linaire (en le nombre d'abscisses plus le nombre de rectangles). La majeure partie des candidats a bien trait la partie 3 (sans forcment suivre la structure propose dans l'nonc) mais n'a pas russi la partie 4. Un candidat (au moins) a trait l'ensemble du sujet. </p><p> Etoiles: Ce sujet a t donn pour une session avec peu de candidats, et demandait un peu de </p><p>reflexion gomtrique. Les meilleurs candidats ont atteint la question 5. Du point de vue algorithmique, la recherche dichotomique doit tre connue des candidats. </p><p> Arbres phylogntiques: Un certain nombre de candidats ont cherch rsoudre les questions </p><p>sans construire l'arbre, ce qui devenait rapidement trs difficile. L'arbre pouvait tre reprsent l'aide d'un tableau, et construit de faon itrative. Traiter parfaitement les quatre premires questions permettait d'avoir la moyenne. </p><p> Apprentissage de langages rguliers: Encore une fois, l'utilisation de tableaux pour la </p><p>construction de l'automate tait plus simple que l'utilisation d'une structure rcursive. Il suffisait de constater que le nombre d'tats de l'automate tait infrieur k (ce que peu d'tudiants ont vu). </p><p> Classifier avec des arbres: La question 4 a t la plus discute l'oral, la fois pour sa difficult </p><p>algorithmique, et l'tude de sa complexit. Un tableau d'arbres tait une solution satisfaisante, et de nombreux tudiants ont trouv un algorithme raisonnable (sans forcment russir le programmer). Peu d'tudiants ont trouv directement une complexit cubique. Les meilleurs tudiants sont alls jusqu' la question 6. </p><p> On peut trouver les cinq sujets proposs cette anne sur le site web de l'preuve : </p><p>http://www.ens-lyon.fr/LIP/ConcoursInfo </p></li></ul>