Présentation du cours

L’écriture d’un programme est souvent l’objet d’un compromis entre son temps d’exécution (efficacité algorithmique de la solution codée) et son temps de développement (réflexion, implantation et débuguage). Deux attitudes caricaturales sont :

Le but de ce module est de s’entraîner à la résolution effective de problèmes algorithmiques. Pour cela, il faudra trouver un équilibre entre ces deux façons d’agir.

Le choix de la solution à retenir repose typiquement sur le temps disponible d’une part et les caractéristiques particulières des instances à résoudre d’autre part (taille, décomposition éventuelle,…). Le choix de la structure de données est également un paramètre crucial d’efficacité.

Dans ce module, nous étudierons différents problèmes (algorithmiques purs) que nous cherchons à résoudre effectivement en écrivant un programme (en C, C++, Java…) qui sera testé/validé sur des jeux de données.

Les objectifs sont les suivants :

Ce module encadré par Vincent Lanore, Arnaud Lefray, Théophile Trunck et Petru Valicov aura lieu en salle E001 les mercredis de 15h45 à 18h45.

Organisation du cours

Chaque semaine vous aurez un ensemble de problèmes à résoudre. Pour cela il faudra trouver l'algorithme, le coder et le valider contre un jeu de donnée en temps limité (il doit fournir exactement la sortie attendue en un temps limité). Les codes résolvant ces problèmes seront à envoyer (avec l'objet **[ACM]**) à vos TD-Men avant le dimanche de la semaine suivant le TD (par exemple avant le 09/02/2014 pour le premier TD). Le code de chaque problème devra être contenu dans un unique fichier nommé suivant la convention numéro_du_problème-login (par exemple pour le premier problème 10055-ttrunck.cpp).

La validation de ces problèmes vous donnera la note de controle continu, il y aura également un partiel et un examen, la note finale sera une pondération de ces trois notes (a priori 1/2CC+1/6Partiel+1/3Examen).

Même si le concours ACM a lieu en équipe ce cours sera individuel. Chacun est donc tenu de rendre ses propres problèmes. Toutefois quelques TD (et peut-être le partiel) auront lieu en équipes.

Pour démarrer

Lors de ce cours nous utiliserons le site UVA. Commencez par y créer un compte. Une fois connecté au site UVA dans la barre de navigation à gauche il y a un lien My uHunt with Virtual Contest Service vers une adresse http://uhunt.felix-halim.net/id/n avec n un nombre, c'est ce que j'appelle votre idUva, nous l'utiliserons pour vérifier vos problèmes résolus.

Maintenant que vous avez votre idUva vous pouvez vous inscrire sur ce site (en haut à droite). Voici un aperçu de ce site: