Le séminaire du LSV

Le séminaire du LSV a lieu le mardi à 11h00. Le lieu habituel est la salle de conférences au Pavillon des Jardins (plan d'accès). Pour être informé par email des prochains séminaires, contacter Laurent Doyen and Stefan Göller.

Le séminaire du LSV est public et ne nécessite aucune inscription préalable.

Prochain séminaire

Runtime Analysis of Randomized Algorithms: A Dijkstra Déjà Vu

Visiter le site web pour cet événement | Exporter cet événement au format iCalendar

 Joost-Pieter   Katoen
Date
Le mercredi 29 mars 2017 à 10:00
Lieu
Salle de Conférence (Pavillon des Jardins)
Orateur
Joost-Pieter Katoen (RWTH Aachen)

Randomization is an important tool in algorithm design for obtaining efficient solutions; e.g., random pivot selection in quicksort lowers the expected runtime (ER) to O(n log n). Reasoning about the ER of randomized algorithms is subtle and full of nuances, as:

  • they may have diverging runs but have a finite ER;
  • they may almost surely terminate but have an infinite ER;
  • running two finite-ER algorithms in sequence may yield an infinite ER.

ER analysis of randomized algorithms is typically done using classical probability theory, mostly with arguments relying on random variable expectations or martingales. These analyses partially follow an ad-hoc reasoning and take non-trivial relationships between random variables for granted.

In this talk, I'll present a formal verification approach towards the ER analysis using a weakest-precondition approach à la Dijkstra. It allows e.g. to prove the positive almost-sure termination: does a program terminate with probability one in finite expected time? We show proof rules for loops prove the soundness w.r.t a simple operational mode and argue that our approach conservatively extends Nielson's approach for deterministic programs.


Séminaires à venir

TBA

Visiter le site web pour cet événement | Exporter cet événement au format iCalendar

 Sébastien  Bardin and Richard  Bonichon
Date
Le mardi 02 mai 2017 à 11:00
Lieu
Salle de Conférence (Pavillon des Jardins)
Orateur
Sébastien Bardin and Richard Bonichon (CEA, Paris-Saclay)


TBA

Visiter le site web pour cet événement | Exporter cet événement au format iCalendar

Date
Le mardi 13 juin 2017 à 11:00
Lieu
Salle de Conférence (Pavillon des Jardins)
Orateur
Colin Riba (LIP, ENS Lyon)


TBA

Visiter le site web pour cet événement | Exporter cet événement au format iCalendar

 Pablo  Arrighi
Date
Le mardi 20 juin 2017 à 11:00
Lieu
Salle de Conférence (Pavillon des Jardins)
Orateur
Pablo Arrighi (LIF, Université Aix-Marseille)


À propos du LSV

Agenda des séminaires

Exporter l'agenda au format iCalendar | Les séminaires précédents

Aujourd'hui (mer. 29 mars)
mar. 2 mai
mar. 13 juin
mar. 20 juin

Les séminaires précédents