<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "
http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"><html xmlns="
http://www.w3.org/1999/xhtml" xml:lang="en" lang="en"><head><meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<meta name="author" content="Matthieu Gallet [Flanker]" />
<meta http-equiv="pragma" content="no-cache" /><link rel="stylesheet" media="screen" type="text/css" href="resources/v9.css" /><link rel="stylesheet" media="print" type="text/css" href="resources/v9_print.css" /><link rel="stylesheet" media="screen" type="text/css" href="resources/v9_webkit.css" /><link rel="stylesheet" media="print" type="text/css" href="resources/v9_print_webkit.css" /><script type="text/javascript" src="resources/scripts.js" ></script><script type="text/javascript" src="resources/ajax.js" ></script><meta name='keywords' content="Matthieu Gallet Flanker divisible load scheduling thesis \" ENS \' Lyon" /><title>Teaching</title><meta name='keywords' content="ACM C++ CamlLight TP ENS Lyon" /></head><body style='font-size: 12pt;' id='body' ><div class="backgroundLogin">
<span class="backgroundLogin">v9admin</span><span class="backgroundLogout"> <a href='index.php?&v9active=background&v9a=logout&v9p=4' class='background' title='' >Déconnexion</a></span><span id='v9clock' title='27/03/2008' class='backgroundClock'>20:15</span><span class='backgroundFontSize'><a onclick="return changeSize('big');" href='index.php?v9p=4&v9font=14' class='backgroundFontSize' title='Grande taille '><big class='backgroundFontSize'>A</big></a><a onclick="return changeSize('normal');" href='index.php?v9p=4&v9font=12' class='backgroundFontSize' title='Taille normale ' style='padding-top: 2px' >A</a><a onclick="return changeSize('small');" href='index.php?v9p=4&v9font=10' class='backgroundFontSize' title='Petite taille '><small class='backgroundFontSize'>A</small></a><a href='index.php?v9p=4&v9lang=en_us' class='backgroundFontSize' title='English '><img alt='Français' class='backgroundLanguage' src='pictures/flag_fr_fr.png' /></a></span>
</div>
<h1 class="background"><span class='module'>19'' v9 </span></h1><div class="pageTitle"><h2 class="pageTitle"><a style="display:none;" name="page"> </a></h2></div>
<div class='site' >
<div class='siteSpacer' > <a href='#' id='ApageList' name='ApageList' class='invisible'></a></div>
<span class='site_left' ><a class="site" title="Page d'accueil du site" href="Accueil.html" >Accueil</a></span><span class='site' ><a class="site" title="" href="_me.html" >/me</a></span><span class='siteSelected'><a class="siteSelected" title="TD de L3 et M1" href="Teaching.html" >Teaching</a></span><span class='site' ><a class="site" title="" href="Research.html" >Research</a></span><span class='site' ><a class="site" title="" href="Photos.html" >Photos</a></span><span class='site' ><a class="site" title="" href="Liens_sympas.html" >Liens sympas</a></span><span class='site' ><a class="site" title="" href="TI-68k.html" >TI-68k</a></span><span class='site' ><a class="site" title="page d'essais divers" href="Essais.html" >Essais</a></span><span class='site_right' ><a class="site" title="Administration du site" href="Admin.html" >Admin</a></span></div>
<div class='pageBody'>
<table class="pageBody" style="width:100%" summary="Contenu de la page" ><tr class="pageBody" style="width:100%"> <td class="pageBody" style="width:10%;" > </td><td class="pageBody" style="width:80%;" ><div class='module' >
<div class="moduleHeader"><h4 class='moduleHeader'>TP ACM 2008</h4>
</div>
<div class="moduleBody" id="m21" ><div class="moduleDesc"><span class='module'>Présentation du cours, par <a class='module' href='
http://www.dim.uchile.cl/%7Eschabanel/' onclick='return url(this);' >Nicolas Schabanel</a> :<br />
<br />
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ébuggage). Deux attitudes caricaturales sont :</span><ol class='module'><li class='module'><span class='module'>rechercher la solution la plus efficace théoriquement (c.-à-d. quand n temps vers l'infini) même si elle est très compliquée à implémenter ou</span></li><li class='module'><span class='module'>implémenter la première idée venue. L'objectif de ce cours est d'essayer de trouver un équilibre entre ces deux façons d'agir, idéalement de développer rapidement et de façon sûre une solution efficace sans avoir à débugguer.</span></li></ol><span class='module'><br />
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é.<br />
<br />
Dans ce cours, nous étudierons différents problèmes (algorithmiques purs) que nous cherchons à résoudre effectivement en écrivant un programme (dans le langage de votre choix - C/C++/Java...) qui sera testé/validé sur des jeux de données.<br />
L'objectif de ce cours est à la fois d'obtenir une compréhension profonde des algorithmes classiques et de leurs performances réelles, et d'apprendre à résoudre efficacement et effectivement un problème algorithmique.<br />
<br />
Ce cours a également pour but de préparer trois équipes d'étudiants (environ) au concours d'algorithmique et programmation « ACM International Collegiate Programming Contest », et dans le cadre de cette préparation, de constituer une base de données d'algorithmes écrits de façon lisible et efficace qui accompagnera nos candidats (un listing de 50 pages de code est autorisé lors des épreuves). </span></div><table id='m21_files' class='fileList' summary='Fichiers présents'><tr class='fileList'>
<th class='fileListL' style='width: 24px;' > </th>
<th class='fileListR'>Nom</th>
<th class='fileList' style='width: 16%' >Taille</th>
<th class='fileList' style='width: 20%' >Modifié le</th>
</tr><tr class='fileList1'>
<td class='fileList'><img class='fileList' alt=' ' src='icones/pdf.png' /></td>
<td class='fileList'><a href='index.php?&v9m=21&v9a=download&v9p=4&f=/tp-acm-2008-01.pdf' class='fileList' title='' >tp-acm-2008-01.pdf</a></td>
<td class='fileList'>67.35 ko</td>
<td class='fileList'>23/01/2008 18:46</td>
</tr><tr class='fileList2'>
<td class='fileList'><img class='fileList' alt=' ' src='icones/pdf.png' /></td>
<td class='fileList'><a href='index.php?&v9m=21&v9a=download&v9p=4&f=/tp-acm-2008-02.pdf' class='fileList' title='' >tp-acm-2008-02.pdf</a></td>
<td class='fileList'>65.05 ko</td>
<td class='fileList'>05/02/2008 17:37</td>
</tr><tr class='fileList1'>
<td class='fileList'><img class='fileList' alt=' ' src='icones/pdf.png' /></td>
<td class='fileList'><a href='index.php?&v9m=21&v9a=download&v9p=4&f=/tp-acm-2008-03.pdf' class='fileList' title='' >tp-acm-2008-03.pdf</a></td>
<td class='fileList'>62.21 ko</td>
<td class='fileList'>12/02/2008 13:58</td>
</tr><tr class='fileList2'>
<td class='fileList'><img class='fileList' alt=' ' src='icones/pdf.png' /></td>
<td class='fileList'><a href='index.php?&v9m=21&v9a=download&v9p=4&f=/tp-acm-2008-04.pdf' class='fileList' title='' >tp-acm-2008-04.pdf</a></td>
<td class='fileList'>39.4 ko</td>
<td class='fileList'>26/02/2008 16:46</td>
</tr><tr class='fileList1'>
<td class='fileList'><img class='fileList' alt=' ' src='icones/pdf.png' /></td>
<td class='fileList'><a href='index.php?&v9m=21&v9a=download&v9p=4&f=/tp-acm-2008-05.pdf' class='fileList' title='' >tp-acm-2008-05.pdf</a></td>
<td class='fileList'>147.21 ko</td>
<td class='fileList'>11/03/2008 09:47</td>
</tr><tr class='fileList2'>
<td class='fileList'><img class='fileList' alt=' ' src='icones/pdf.png' /></td>
<td class='fileList'><a href='index.php?&v9m=21&v9a=download&v9p=4&f=/tp-acm-2008-06.pdf' class='fileList' title='' >tp-acm-2008-06.pdf</a></td>
<td class='fileList'>42.93 ko</td>
<td class='fileList'>18/03/2008 17:43</td>
</tr><tr class='fileList1'>
<td class='fileList'><img class='fileList' alt=' ' src='icones/pdf.png' /></td>
<td class='fileList'><a href='index.php?&v9m=21&v9a=download&v9p=4&f=/tp-acm-2008-07.pdf' class='fileList' title='' >tp-acm-2008-07.pdf</a></td>
<td class='fileList'>45.98 ko</td>
<td class='fileList'>25/03/2008 16:16</td>
</tr></table><script type='text/javascript' >FLinit('m21_files');</script></div>
<div class="moduleFooter"><span class='moduleFooter'>2008-03-22 00:11:54</span><a href='index.php?&v9m=21&v9a=edit&v9p=4' class='moduleFooter' title='Permet de modifier le contenu du module' ><img class="moduleFooter" src="pictures/b_edit.png" alt="Editer" /></a><a href='index.php?&v9m=21&v9a=del&v9p=4' class='moduleFooter' title='Supprime le module' ><img class="moduleFooter" src="pictures/b_drop.png" alt="Supprimer" /></a><a href='index.php?&v9m=21&v9a=left&v9p=4' class='moduleFooter' title='Déplacer à gauche' ><img class="moduleFooter" src="pictures/b_left.png" alt="<" /></a><a href='index.php?&v9m=21&v9a=up&v9p=4' class='moduleFooter' title='Monter' ><img class="moduleFooter" src="pictures/b_up.png" alt="^" /></a><a href='index.php?&v9m=21&v9a=down&v9p=4' class='moduleFooter' title='Descendre' ><img class="moduleFooter" src="pictures/b_down.png" alt="v" /></a><a href='index.php?&v9m=21&v9a=right&v9p=4' class='moduleFooter' title='Déplacer à droite' ><img class="moduleFooter" src="pictures/b_right.png" alt=">" /></a></div></div><div class='module' >
<div class="moduleHeader"><h4 class='moduleHeader'>Arithmétique des ordinateurs 2008</h4>
</div>
<div class="moduleBody" id="m23" ><div class="moduleDesc"><span class='module'>Le cours est assuré par <a class='module' href='
http://perso.ens-lyon.fr/florent.de.dinechin/enseignement/2007-2008/' onclick='return url(this);' >Florent de Dinechin</a>, les TD sont assurés par <a class='module' href='
http://perso.ens-lyon.fr/christoph.lauter/' onclick='return url(this);' >Christoph Lauter</a> et moi-même. </span></div><table id='m23_files' class='fileList' summary='Fichiers présents'><tr class='fileList'>
<th class='fileListL' style='width: 24px;' > </th>
<th class='fileListR'>Nom</th>
<th class='fileList' style='width: 16%' >Taille</th>
<th class='fileList' style='width: 20%' >Modifié le</th>
</tr><tr class='fileList1'>
<td class='fileList'><img class='fileList' alt=' ' src='icones/pdf.png' /></td>
<td class='fileList'><a href='index.php?&v9m=23&v9a=download&v9p=4&f=/TD_01.pdf' class='fileList' title='' >TD_01.pdf</a></td>
<td class='fileList'>449.83 ko</td>
<td class='fileList'>04/02/2008 13:27</td>
</tr><tr class='fileList2'>
<td class='fileList'><img class='fileList' alt=' ' src='icones/pdf.png' /></td>
<td class='fileList'><a href='index.php?&v9m=23&v9a=download&v9p=4&f=/TD_02.pdf' class='fileList' title='' >TD_02.pdf</a></td>
<td class='fileList'>59.34 ko</td>
<td class='fileList'>11/02/2008 16:46</td>
</tr><tr class='fileList1'>
<td class='fileList'><img class='fileList' alt=' ' src='icones/pdf.png' /></td>
<td class='fileList'><a href='index.php?&v9m=23&v9a=download&v9p=4&f=/TD_03.pdf' class='fileList' title='' >TD_03.pdf</a></td>
<td class='fileList'>22.05 ko</td>
<td class='fileList'>25/02/2008 08:02</td>
</tr></table><script type='text/javascript' >FLinit('m23_files');</script></div>
<div class="moduleFooter"><span class='moduleFooter'>2008-03-20 14:34:51</span><a href='index.php?&v9m=23&v9a=edit&v9p=4' class='moduleFooter' title='Permet de modifier le contenu du module' ><img class="moduleFooter" src="pictures/b_edit.png" alt="Editer" /></a><a href='index.php?&v9m=23&v9a=del&v9p=4' class='moduleFooter' title='Supprime le module' ><img class="moduleFooter" src="pictures/b_drop.png" alt="Supprimer" /></a><a href='index.php?&v9m=23&v9a=left&v9p=4' class='moduleFooter' title='Déplacer à gauche' ><img class="moduleFooter" src="pictures/b_left.png" alt="<" /></a><a href='index.php?&v9m=23&v9a=up&v9p=4' class='moduleFooter' title='Monter' ><img class="moduleFooter" src="pictures/b_up.png" alt="^" /></a><a href='index.php?&v9m=23&v9a=down&v9p=4' class='moduleFooter' title='Descendre' ><img class="moduleFooter" src="pictures/b_down.png" alt="v" /></a><a href='index.php?&v9m=23&v9a=right&v9p=4' class='moduleFooter' title='Déplacer à droite' ><img class="moduleFooter" src="pictures/b_right.png" alt=">" /></a></div></div></td><td class="pageBody" style="width:10%;" > </td><td class="pageBody" style="width:0%;" > </td></tr></table></div><div class="footer"><p class="footer"><script type="text/javascript">window.setTimeout("changeDate()", 1000); </script><span class='module'>©2oo<strong class='module'>8</strong> flan </span></p></div></body></html>