BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//GREYC UMR CNRS 6072 - Groupe de Recherche en Informatique, Image, et Instrumentation de Caen - ECPv5.7.0//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:GREYC UMR CNRS 6072 - Groupe de Recherche en Informatique, Image, et Instrumentation de Caen
X-ORIGINAL-URL:https://www.greyc.fr
X-WR-CALDESC:évènements pour GREYC UMR CNRS 6072 - Groupe de Recherche en Informatique, Image, et Instrumentation de Caen
BEGIN:VTIMEZONE
TZID:Europe/Paris
BEGIN:DAYLIGHT
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
DTSTART:20230326T010000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
DTSTART:20231029T010000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Europe/Paris:20230627T100000
DTEND;TZID=Europe/Paris:20230627T110000
DTSTAMP:20260423T073316
CREATED:20240108T100025Z
LAST-MODIFIED:20240108T100025Z
UID:11392-1687860000-1687863600@www.greyc.fr
SUMMARY:Séminaire Algorithmique : “Robustness of the RAM model” or “how to perform a division in constant time”\, Etienne Granjean (GREYC\, Caen)
DESCRIPTION:Accurately measuring the complexity of algorithms and establishing the intrinsic computational complexity of problems are among the most important tasks/goals in computer science. For this\, everyone agrees that the right model of computation (for sequential algorithms) is the random access machine (RAM). Contrary to this general agreement\, paradoxically\, there is no consensus on how to define the RAM model. It is like a Babel tower. Since the 1970s\, the literature has presented a plethora of definitions of RAMs and their complexity with no unifying result. \nIn this talk\, I will present a simple model of RAM. I will show that this model on the one hand sticks to the algorithms\, their data structures and their fine-grained complexity (linear time\, or even constant time\, etc.) and on the other hand is robust to many variations. In particular\, we demonstrate that the complexity classes — linear time\, quadratic time\, enumeration complexity classes\, etc. — do not change depending on whether the only primitive operation of a RAM is addition\, or whether the usual arithmetic operations — subtraction\, multiplication or even division (!!!!) and many others — are allowed. This is a joint work with Louis Jachiet.
URL:https://www.greyc.fr/event/seminaire-algorithmique-robustness-of-the-ram-model-or-how-to-perform-a-division-in-constant-time-etienne-granjean-greyc-caen/
LOCATION:Sciences 3- S3 351
CATEGORIES:Amacc,General,Séminaire Algo
END:VEVENT
END:VCALENDAR