EΘΝΙΚΟ ΚΑΙ ΚΑΠΟΔΙΣΤΡΙΑΚΟ ΠΑΝΕΠΙΣΤΗΜΙΟ ΑΘΗΝΩΝ
ΤΜΗΜΑ ΠΛΗΡΟΦΟΡΙΚΗΣ & ΤΗΛΕΠΙΚΟΙΝΩΝΙΩΝ

ΣΕΜΙΝΑΡΙΟ ΑΛΓΟΡΙΘΜΩΝ
Aκαδημαϊκό έτος 2008-09

Τo σεμινάριο Αλγορίθμων οργανώνεται από τον Τομέα Θεωρητικής Πληροφορικής και παρουσιάζει ερευνητικές δραστηριότητες στην περιοχή του σχεδιασμού και ανάλυσης αλγορίθμων και άλλων σχετικών θεματων. Μπορείτε να δείτε το πρόγραμμα των ετών 03-04, 04-05, 05-06, 06-07 και 07-08. Για περισσότερες πληροφορίες απευθυνθείτε στον Καθηγητή Γιάννη Eμίρη.

Oι ομιλίες δίνονται (πλην εξαιρέσεων) στην Αίθουσα Τηλεσυσκέψεων, 2os όροφος, Kέντρο Δικτύων, στο Tμήμα Πληροφορικής & Tηλεπικοινωνιών, oπότε και μεταδίδονται σε πραγματικό χρόνο στο διαδίκτυο. Για οδηγίες σύγχρονης παρακολούθησης και παρακολούθησης των αποθηκευμένων video, δείτε http://mc.gunet.gr/hlive.html.  Φυσική πρόσβαση με λεωφορείο ή μετρό-λεωφορείο.


ΠΡΟΓΡΑΜΜA

σε αντίστρoφη χρονολογική σειρά
(σε κίτρινο η αμέσως προσεχής ομιλία)
ΗΜΕΡΟΜΗΝΙΑ
ΟΜΙΛΗΤΗΣ
ΤΙΤΛΟΣ ΟΜΙΛΙΑΣ
Παρ. 28 Νοεμβρίου
3.00 μμ
Greg Aloupis
(UBL, Βέλγιο)
Reconfiguration of modular robots
(abstract)
Παρ. 24 Οκτωβρίου
** 11.00 **
Aίθουσα Δ'
Rachid Deriche
(INRIA Sophia-Antipolis)
Computational Diffusion MRI : Models, Algorithms and Applications (abstract) (PDF)
Πέμ. 16 Οκτωβρίου,
2μμ
** Aίθουσα Δ' **
Dimitris P. Tsakiris
(Institute of Computer Science - FORTH)
Bio-inspired pedundulatory robotic locomotion (abstract)
Παρ. 3 Οκτωβρίου, 11.00
** Aμφιθέατρο **
Ιωσήφ Σηφάκης
(Verimag Lab, FRANCE)
The Quest for Correctness: Beyond Verification (abstract) (PDF)
Δευτ. 1 Σεπτεμβρίου,
11.00
Bernard Mourrain
(INRIA, Sophia-Antipolis Mediterranee, France)
On Stable Methods for Solving Polynomial Equations
(abstract)

ΠΕΡΙΛΗΨΕΙΣ ΟΜΙΛΙΩΝ


Παρ. 28 Νοεμβρίου, 3.00 μμ
Greg Aloupis (UBL, Βέλγιο)
ΠΕΡΙΛΗΨΗ

A modular robot consists of several identical individual components (modules) attached together. Groups of modules may co-operate to produce local or global reconfigurations of the robot shape. In this talk, I will discuss algorithmic issues in the reconfiguration of Telecube and Crystalline robots, whose components are shaped as cubes.
The total number of sufficient motions for any reconfiguration depends on the level of "physical realism" that is chosen to be modeled (e.g., bounds on physical strength or maximum velocity). Some of the recent bounds obtained are not yet tight, and thus present themselves as interesting open problems.

Παρ. 24 Οκτωβρίου, ** 11.00 ** Aίθουσα Δ'
Rachid Deriche (INRIA Sophia-Antipolis)

Abstract:

Diffusion MRI is a Magnetic Resonance Imaging (MRI) modality able to quantify in vivo and non invasively the diffusion of water molecules in biological tissues such as the white matter in the brain. In this talk, I will present some variational approaches we developed in the recent years for the estimation, regularization and segmentation of diffusion tensor images (DTI). These algorithms open the possibility of recovering a detailed geometric description of the anatomical connectivity between brain areas and help to distinguish the anatomical structures of the cerebral white matter. I'll also present and discuss some parts of our recent work on HARDI (High Angular Resolution Diffusion Imaging)  data and will present a simple linear and regularized analytic solution for the Q-ball reconstruction of the Orientation Distribution Function (ODF). Applications to white matter segmentation and tractography will be considered and will illustrate this talk. More information and publications related to this talk can be recovered at : http://www-sop.inria.fr/odyssee/en/rachid.deriche.

Πέμ. 16 Οκτωβρίου, 2μμ ** Aίθουσα Δ' **
Dimitris P. Tsakiris (Institute of Computer Science - FORTH)

“Bio-inspired pedundulatory robotic locomotion”

Abstract:

Control of movement, and its relationship to sensing and perception, is one of the most significant issues for emerging robotic applications dealing with unstructured and tortuous environments. Such applications occur, among other domains, in industrial site inspection, in search-and-rescue operations, in planetary exploration, and even in the endoluminal access to the human body. Drawing inspiration from biology, where such problems have been effectively addressed by the evolutionary process, can help in overcoming limitations of present-day robotic systems and in designing agile robots, able to adapt robustly to a variety of environmental conditions.

This talk will focus on work inspired by organisms locomoting by body undulations. In particular, a class of marine worms, the polychaete annelids, offers an intriguing biological paradigm of locomotion on sand, mud, sediment, as well as underwater: the variety of their morphology, sensory apparatus and nervous system structure is a direct consequence of their adaptation to so diverse habitats. Such locomotion capabilities could benefit, if properly replicated, robotic systems functioning in unstructured environments.

The described work focuses on the use of detailed computational models for the mechanics, sensing and motion control of this type of bio-inspired robotic locomotion; these models involve the dynamics of the system's motion, its interaction with the environment and neural control by central pattern generators. Dedicated computational tools (the SIMUUN simulation environment) have been developed. These are exploited to study the generation of novel pedundulatory robotic locomotion gaits, which combine body undulations with the action of numerous leg-like appendages. Appropriate use of sensory information leads to reactive behaviors, a first step towards adaptation of these robotic systems to their environment. A number of robotic prototypes have been developed, which demonstrate the generation of pedundulatory gaits and reactive behaviors on a variety of unstructured, granular and deformable locomotion substrates.

Short Bio:

Dr. Dimitris P. Tsakiris is a Principal Researcher at the Institute of Computer Science of the Foundation for Research and Technology - Hellas (FORTH) in Heraklion, Greece, and a faculty member of the Graduate Program in the Brain and Mind Sciences of the University of Crete. He holds a B.S. degree from the Department of Electrical Engineering of the National Technical University of Athens, Greece, and M.S. and Ph.D. degrees from the Department of Electrical Engineering of the University of Maryland at College Park, USA. Prior to his current appointment, he was a Marie Curie/TMR postdoctoral fellow with the robotics group Icare of the Institut National de Recherche en Informatique et en Automatique (INRIA) in Sophia-Antipolis, France. His research interests lie in the areas of biologically-inspired robotics, sensor-based navigation and control, undulatory locomotion, nonlinear control and computational vision. He is a principal investigator and co-investigator of several national and European R&D projects, related to his research interests, and is currently leading the ICS-FORTH efforts on pedundulatory and hyper-redundant robotics and on robot-assisted endoscopy.


Παρ. 3 Οκτωβρίου, 11.00, Aμφιθέατρο
Ιωσήφ Σηφάκης (Verimag Lab, FRANCE)
The Quest for Correctness: Beyond Verification

I discuss main achievements in the area of formal verification, in particular regarding their impact on the development of Computer Science as a discipline as well as future research directions. The presentation starts with a short overview of formal verification techniques and their main characteristics followed by an analysis of their current status with respect to 1) requirements specification; 2) faithfulness of modeling; 3) scalability of verification methods. Compositional modeling and verification is  the main challenge for tackling complexity. I identify two complementary research directions for overcoming  current  difficulties in compositional techniques. 1) Moving from low‐level automata‐based composition to component‐based composition, by developing frameworks encompassing heterogeneous components 2) Use such frameworks to study compositionality techniques for particular architectures and/or specific properties. I argue that these directions are not only an opportunity for reinvigorating formal verification, but they also lead to constructivity results which will help to close the gap between Formal Methods Verification and Algorithms and Complexity.

Η ομιλία θα μεταδοθεί σε πραγματικό χρόνο στο διαδίκτυο: http://lessons.di.uoa.gr/amfith/

Σύντομο βιογραφικό:

Ο Ι. Σηφάκης έλαβε το δίπλωμα Ηλεκτρολόγου Μηχανικού από το Εθνικό Μετσόβειο Πολυτεχνείο και το διδακτορικό του στην Πληροφορική, καθώς και Δίπλωμα Υφηγεσίας, από το Πανεπιστήμιο J. Fourier της Grenoble, Γαλλία. Σήμερα είναι Διευθυντής ερευνών στο CNRS και Διευθυντής του Ινστιτούτου Intelligent Software and Systems, ενώ υπήρξε ιδρυτής και Διευθυντής του Εργαστηρίου Verimag. Οι ερευνητικές δραστηριότητες του επεκτείνονται σε πολλές περιοχές της Πληροφορικής μεταξύ των οποίων περιλαμβάνονται οι εξής: μοντελοποίηση και επαλήθευση συστημάτων, ενσωματωμένα συστήματα, συστήματα πραγματικού χρόνου, σχεδίαση αρθρωτών συστημάτων, δίκτυα Petri.  Το επιστημονικό έργο του αριθμεί περίπου 100 δημοσιεύσεις σε κορυφαία επιστημονικά περιοδικά και συνέδρια. Η προσφορά του έχει αναγνωριστεί πολλαπλά από την διεθνή κοινότητα και έχει τιμηθεί με το Αργυρό Μετάλλιο του CNRS το 2001, ενώ φέτος τιμήθηκε με το βραβείο Turing της ACM, από κοινού με τους E.M.Clarke και E.A.Emerson, για την έρευνά τους στην περιοχή του Model Checking.

Δευτ. 1 Σεπτεμβρίου, 11.00
Bernard Mourrain (INRIA, Sophia-Antipolis Mediterranee, France)
On Stable Methods for Solving Polynomial Equations

Solving polynomial equations with approximate coefficients is ubiquitous in many applications. Typically, in domains such as geometric modeling, we are interested in computing characteristic points on curves or surfaces which are given with incertitude on the input coefficients. An important and difficult question is then to isolate the (real) roots of these equations and to analyse their multiplicities. To tackle this issue we discuss subdivision algorithms.