From: daumas@lip (Marc Daumas)
To: eleves.dmi@lip, tous.lip@lip, claire@cri
Subject: Séminaire du Magistère d'Informatique [17/10]
Date: Thu, 12 Oct 1995 12:50:41 +0100


Bonjour,

Notre  deuxième séminaire du  Magistère d'Informatique de l'année aura
lieu le Mardi 17 Octobre avec un exposé de Yves Robert qu'il n'est pas
nécessaire de  présenter.  Les horaires restent inchangés 13h30-14h30,
amphi A.

Titre	La visibilité des segments dans le plan
-----

Résumé
------

	Ce séminaire est construit autour de l'épreuve d'algorithmique
du concours d'entrée 1995 à l'ENS de Lyon ... mais il n'est pas besoin
d'avoir séché sur la dite épreuve pour y assister !

	On expliquera le lien entre  le problème de la visibilité  des
segments dans le plan, les suites  de Davenport-Schinzel et la gestion
des partitions.   On en  profitera  pour parler des  fonctions log* et
d'Ackermann,   puisqu'elles   interviennent dans la   complexité   des
problèmes précédents.

	L'idée n'est pas de faire les démonstrations difficiles (on se
contentera  de quelques  résultats simples,  et  on renverra au  cours
d'algorithmique)  mais   d'expliquer comment on    a  pu  résoudre  ce
problème, et pourquoi il a fallu plusieurs années pour y arriver.

Notes
-----

---> Corrige et pointeurs sur des articles seront a la disposition des
plus courageux.

--->  Je tiens à  la disposition  des  élèves intéressés une copie des
tous  les transparents de l'exposé   de Jean-Michel Moreau (03/10) sur
les  problèmes de   géométrie.   Cela  comprend  une description    de
l'algorithme qui n'a pu être présenté  lors du séminaire par manque de
temps. Passer à mon bureau.

-- 
     .    _  .       ______________________________________
     |\_|/__/|      /                                      \   
    / / \/ \  \    /    Don't let people drive you crazy    \
   /__|O||O|__ \   \ when you know it's in walking distance /
  |/_ \_/\_/ _\ |   \  ____________________________________/
  | | (____) | ||    |/
  \/\___/\__/  // ___/
  (_/         ||    
   |          ||\   Marc Daumas (Marc.Daumas@Lip.Ens-Lyon.Fr)
    \        //_/   Lab. LIP - Equipe SAAO - ENS Lyon
     \______//      46, allee d'Italie - 69364 Lyon Cedex 07
    __|| __||       Ph  : (+33) 72 72 85 49
   (____(____)      Fx  : (+33) 72 72 80 80