Quest’area costituisce il nucleo matematico dell’informatica. L’obiettivo principale è approfondire la comprensione teorica dei processi di calcolo. Da un lato, si mira a progettare algoritmi nuovi o migliorati per uno specifico problema e ad analizzarne rigorosamente le prestazioni dal punto di vista matematico. Dall’altro, si punta a dimostrare che nessun algoritmo per il problema considerato può raggiungere determinate prestazioni.
Leader di area:
Teoria e algoritmi - IDSIA
Area scientifica
SUPSI Image Focus
-
Algoritmi di approssimazione
-
Teoria dei linguaggi formali e degli automi
-
Ottimizzazione combinatoria e matematica discreta
-
Verifica formale
-
Calcolabilità e teoria della complessità computazio
-
Algoritmi numerici
-
Geometria computazionale
-
Algoritmi paralleli e distribuiti
-
Strutture di dati
-
Fondamenti di probabilità
-
Algoritmi dinamici e online
Applichiamo i nostri risultati teorici a una vasta gamma di applicazioni, tra cui:
- grafica computerizzata e progettazione geometrica assistita dal computer
- model checking
- problemi su grafi e reti
- analisi dei programmi
- schedulazione
- sicurezza
- progettazione assistita dal computer di sistemi VLSI
- F. Grandoni and V. V. Williams, Improved Distance Sensitivity Oracles via Fast Single-Source Replacement Paths, 53rd Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS} 2012, New Brunswick, NJ, USA, October 20-23, 2012, 748--757 (2012), https://doi.org/10.1109/FOCS.2012.17
- F. Grandoni, A. Gupta, S. Leonardi, P. Miettinen, P. Sankowski, and M. Singh, Set Covering with Our Eyes Closed, SIAM J. Comput. 42 808--830 (2013), https://doi.org/10.1137/100802888
- K. Hormann, L. Kania, and C. Yap. Novel range functions via Taylor expansions and recursive Lagrange interpolation with application to real root isolation. In Proceedings of the 2021 ACM International Symposium on Symbolic and Algebraic Computation, pages 193-200, Saint Petersburg, Russia, July 2021. ACM.