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 gruppo distinto tra i ricercatori informatici.

Descrzione

Definizione

Non è facile circoscrivere le aree teoriche precisamente. Lo Special Interest Group on Algorithms and Computation Theory dell'ACM (SIGACT) descrive la sua missione come la promozione dell'informatica teorica e afferma che i campi di ricerca dell'informatica teorica sono così ampi da includere:

Lo stesso SIGACT definisce l'informatica teorica come "l'analisi formale della computazione efficiente e dei processi computazionali".^[1]

I lavori in questo campo si distinguono spesso per l'impiego di tecniche matematiche mutuate da una varietà di campi come la matematica discreta, la teoria dei numeri, l'algebra e la logica matematica.

Organizzazioni

EATCS, l'Associazione europea per l'informatica teorica
SIGACT
Associazione olandese per l'informatica teorica

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)

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) Alberto Apostolico (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

Wikiversità contiene risorse su informatica teorica
Wikimedia Commons contiene immagini o altri file su informatica teorica

Collegamenti esterni

(EN) Special Interest Group on Algorithms and Computation Theory, su sigact.acm.org.
(EN) Usenet comp.theory^{[collegamento interrotto]}
(EN) Sfide per l'informatica teorica, documento del 2000, su research.att.com.

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

^ SIGACT, ACM SIGACT, su sigact.org.

[1] SIGACT, ACM SIGACT, su sigact.org.

[1]