Informatica teorica

L'informatica teorica è una branca dell'informatica e della matematica che riguarda gli aspetti più astratti e matematici della computazione, come la teoria della computazione, la semantica della programmazione e la teoria della complessità computazionale. La prima studia cosa in generale possa essere calcolato tramite algoritmi, la seconda cosa e come sia calcolato da uno specifico algoritmo, la terza le risorse ad esso necessarie. Nonostante non abbia come oggetto un singolo argomento, i suoi ricercatori spesso formano un sottogruppo compatto all'interno degli informatici.

Una rappresentazione artistica della macchina di Turing

Descrizione

Definizione

Lo dell'ACM () definisce l'informatica teorica come "l'analisi formale della computazione efficiente e dei processi computazionali".

Lo stesso SIGACT afferma che l'informatica teorica "include un'ampia varietà di temi fra cui algoritmi, strutture dati, complessità computazionale, computazione parallela e distribuita, computazione probabilistica, computazione quantistica, teoria degli automi, teoria dell'informazione, crittografia, semantica e verifica dei programmi, apprendimento automatico, biologia computazionale, economia computazionale, geometria computazionale, teoria dei numeri computazionale e algebra. Il lavoro in questo campo si caratterizza spesso per la sua enfasi su tecniche e rigore matematici."

Organizzazioni

• , l'Associazione europea per l'informatica teorica
• , Special Interest Group on Algorithms and Computation Theory

Pubblicazioni e newsletter

• Chicago Journal of Theoretical Computer Science
• Information and Computation
• Formal Aspects of Computing
• Journal of the ACM
• SIAM Journal on Computing
• SIGACT News
• Theoretical Computer Science
• Theory of Computing Systems

Conferenze

• Annual ACM Symposium on the Theory of Computing (STOC)
• IEEE Symposium on Foundations of Computer Science (FOCS)
• Symposium on Discrete Algorithms (SODA)
• International Colloquium on Automata, Languages and Programming (ICALP)
• Symposium on Theoretical Aspects of Computer Science (STACS)
• European Symposium on Algorithms (ESA)
• Algebraic Methodology And Software Technology (AMAST)
• IEEE Symposium on Logic in Computer Science (LICS)
• International Symposium on Algorithms and Computation(ISAAC)
• (APPROX/RANDOM)
• Computational Complexity Conference (CCC)
• Symposium on Parallelism in Algorithms and Architectures (SPAA)
• Computability in Europe (CiE)

Note

1. SIGACT, ACM SIGACT, su sigact.org. URL consultato il 6 febbraio 2021.

Bibliografia

• (EN) Jan Van Leeuwen ed. (1990): Handbook of Theoretical Computer Science volume A, Elsevier, ISBN 0-444-88071-2
• (EN) Jan Van Leeuwen ed. (1990): Handbook of Theoretical Computer Science volume B, Elsevier, ISBN 0-444-88074-7
• (EN) Jan Van Leeuwen ed. (1995): Computer Science Today. Recent Trends and Developments, Springer, ISBN 3-540-60105-8
• (EN) Donald Knuth (1997): The Art of Computer Programming Volume 1 Fundamental algorithms, 3rd ed., Addison-Wesley, ISBN 0-201-89683-4
• (EN) Donald Knuth (1997): The Art of Computer Programming Volume 2 Seminumerical algorithms, 3rd ed., Addison-Wesley, ISBN 0-201-89684-2
• (EN) Donald Knuth (1997): The Art of Computer Programming Volume 3 Sorting and Searching, 2nd ed., Addison-Wesley, ISBN 0-201-89685-0
• (EN) (2002) Border of strings in automata analysis, 1st ed., McGraw-Hill, ISBN 0-448-22039-3
• Carlo Ghezzi, Dino Mandrioli (1999) Informatica Teorica, Città Studi Edizioni, ISBN 8-825-17241-9

Altri progetti

Altri progetti

• Wikizionario
• Wikiversità
• Wikimedia Commons

• Wikizionario contiene il lemma di dizionario «informatica teorica»
• Wikiversità contiene risorse sull'informatica teorica
• Wikimedia Commons contiene immagini o altri file sull'informatica teorica

Collegamenti esterni

• Giorgio Ausiello, Informatica teorica, in Enciclopedia della scienza e della tecnica, Istituto dell'Enciclopedia Italiana, 2007-2008.
• (EN) Special Interest Group on Algorithms and Computation Theory, su sigact.acm.org.

Controllo di autorità	Thesaurus BNCF 73807 · GND (DE) 4196735-5

Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica