Programmation efficace
Modal INF441

 Ce cours entraine les étudiants au concours de programmation ACM, et fait un survol d'un grand nombre d'algorithmes.

cours: Christoph Dürr
exercices: Steve Oudot
.
..

Informations

salle PC 20 de 10h30 à12h et 13h30 à 15h00, ensuite en salle informatique 33 de 15h15 à17h45

Si vous n'êtes pas inscrit au Modal, mais voulez quand même participer au concours ACM, alors inscrivez vous ici. Vous serez informé du lieu, l'heure et des modalitées. Merci. Et contactez le binet ACM.

Documents

Livres: Liens:

01 | Ve 01/02 Introduction

[exploration avec backtracking, techniques de lecture de l'entrée, structures de données]
Inscrivez vous ici (site 'S')
  1. [S] Problem 1 (n reines)
  2. [S] Repair City Hall
  3. [S] Phone List
  4. [S] A concrete simulation
  5. [S] compile error
Et pour ceux qui veulent aller plus loin :
  1. [S] Sudoku 9x9
  2. [S] Sudoku 16x16

02 | Ve 08/02 algorithmes gloutons

[comment trier, union-find, codes de Huffman, graphe bi-partie avec degrées prescrits]
  1. [S] Colours A, B, C, D
  2. [Z] T9
  3. [T] [B] [D] Networking
  4. [T] [D] Variable Radix Huffman Encoding
  5. [T] [D] Magic Sticks Again
  6. [D] Disk Tree
Et encore pour ceux qui veulent aller plus loin :
  1. [T] [D] [C] Huffman Trees

03 | Ve 15/02 programmation dynamique

[plus court chemin dans une grille orienté, distance d'édition, plus longue sous-séquence commune, plus longue sous-séquence croissante, multiplication d'une séquence de matrices]
Juge en panne ? Retrouvez les énoncés ici.
  1. [T] [C] [D] Longest Ordered Subsequence
  2. [T] [D] Tetris
  3. [T] [C] [D] The Separator
  4. [T] [C] [D] Common Subsequence
  5. [T] [A] [Z] Stacking Boxes
Lisez ces exemples pour apprendre comment ne pas faire.

04 | Ve 22/02 programmation dynamique

[subsetsum, coin change, voyageur de commerce, bin packing, minimum hitting set pour un graphe d'intervalles, plus grand rectangle sous un histogramme]]
Ce jour le cours sera exceptionnelement en salle PC 21.
  1. Soumettez ici
  2. [T] [C] [D] Color a Tree
  3. [T] [C] [D] Radar Installation
  4. [T] [D] Is Bigger Smarter?
  5. [T] [C] [D] To The Max
  6. [T] [C] [D] Largest Rectangle in a Histogram
  7. [T] [D] Homework
  8. [T] [D] Playground
  9. [T] [D] Binary Trees

05 | Ve 01/03 calculer

[algorithme d'Euclide, crible d'Eratosthène, résoudre un système d'équations linéaires, multiplier des matrices circulaires, le test de Freivalds, analyse syntaxique d'une expression arithmétique]
  1. [D] Spreadsheet --- a programmer seul !
  2. [T] [A] Ars Longa
  3. [D] Prime Gap
  4. [S] Tiling a Grid With Dominoes
  5. [T] [D] Boolean Expression
  6. [T] [D] Simplified λ-evalutations
Voici des problèmes donnés pendant des entretiens d'embauche.

06 | Ve 15/03 exploration de graphes

[avec pile (DFS), avec file (BFS), avec file à deux bouts (plus courts chemin avec poids {0,1} sur les arcs), composantes fortement connexes, résoudre 2-SAT, points d'articulation et ponts]
  1. Soumettez ici
  2. [T] [C] [D] Finding Nemo
  3. [T] [X] [D] Mine
  4. [C] [D] Traffic Jam
  5. [C] [D] Street Directions
  6. [C] [D] Minesweeper
  7. [C] [D] Australian Voting
  8. [C] [D] The Trip
  9. [C] [D] LC Display

07 | Ve 22/03 couplages

[couplages dans les graphes bi-partis, chemin augmentant, algorithme en O(nm) pour couplage de cardinalité max, couplage parfait de profit maximal, cycle augmentant]
Avant de commencer, vous devez, je dis bien, devez, répondre à ce questionnaire.
  1. [G] Egg Drop
  2. [T] [C] [D] Courses
  3. [X] [D] Poor Wenwen
  4. [C] [D] Pizza delivery
  5. [A] [D] Babel Towers
  6. [T] [X] [D] Make it Manhattan
  7. [Z] Manhattan
Une suggestion de comment boucler en C++.

08 | Ve 05/04 flots

[flot maximal, chemin augmentants, algorithme Ford-Fulkerson, algorithme Edmonds-Karp, algorithme de Dinic]

09 | Ve 12/04 géométrie

[balayage, paire de points les plus proches, paire de points les plus loins, enveloppe convexe, nombre d'intersections de segments, plus petit disque englobant]
  1. [T] [C] [D] Wooden Sticks
  2. [T] [C] [D] Herding Frosh
  3. [T] [H] [D] Rectilinear polygon
  4. [S] [A] [D] Seminar Room
  5. [E] Cutting Sticks
  6. [E] Crimewave

10 | Ma 23/04 contrôle

13:30-15h20 sur papier en salle PC 20, 15h35-17h30 sur machine en salle info 34

Pendant l'examen vous pouvez ammener le poly et 25 pages de code ou de notes. Sur machine vous aurez accès aux documentation de l'API de JDK et de la STL.