Informatica teorica
L'informatica teorica è una branca dell'informatica 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.
Definizione
Non è facile circoscrivere le aree teoriche precisamente; lo Special Interest Group on Algorithms and Computation Theory dell'ACM (SIGACT), che descrive la sua missione come la promozione dell'informatica teorica, dice: "I campi di ricerca dell'informatica teorica sono così ampi da includere:
- algoritmi,
- strutture dati,
- teoria della complessità computazionale,
- calcolo distribuito,
- VLSI,
- apprendimento automatico,
- biologia computazionale,
- geometria computazionale,
- teoria dell'informazione,
- crittografia,
- calcolo quantistico,
- teoria della computabilità
- algebra,
- semantica,
- verifica e validazione,
- teoria degli automi,
- studi sulla casualità.
Lavori in questo campo si distinguono spesso per la loro enfasi per il rigore e per le tecniche matematiche impiegate dai domini, ad esempio, della matematica discreta, della teoria dei numeri, dell'algebra o della logica matematica.
Nonostante questo, i "teorici" dell'informatica teorica si identificano autonomamente in modi differenti. Alcuni si distinguono come persone che si occupano della parte "scientifica" sottostante quella "computazionale", sebbene questo neghi la parte sperimentale svolta in aree non teoriche come la ricerca di sistemi software.
Organizzazioni
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
- (EN) Theory of Computings Sytems
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
Collegamenti esterni
- (EN) SIGACT directory of additional theory links, su sigact.acm.org.
- (EN) Usenet comp.theory
- (EN) pagina principale del SIGACT, su sigact.acm.org.
- (EN) Sfide per l'informatica teorica, documento del 2000, su research.att.com.
| Controllo di autorità | Thesaurus BNCF 73807 · GND (DE) 4196735-5 |
|---|