Vai al contenuto principale
Oggetto:
Oggetto:

FONDAMENTI TEORICI DELL'INFORMATICA

Oggetto:

THEORETICAL FOUNDATIONS OF COMPUTER SCIENCE

Oggetto:

Anno accademico 2022/2023

Codice dell'attività didattica
CPS0667
Docente
Luca Console (Titolare dell'insegnamento)
Corso di studi
Corso di laurea triennale in Innovazione sociale, comunicazione, nuove tecnologie (Classe L-20)
Anno
3° anno
Periodo didattico
Da definire
Tipologia
Affine o integrativo
Crediti/Valenza
6
SSD dell'attività didattica
INF/01 - informatica
Modalità di erogazione
Tradizionale
Lingua di insegnamento
Italiano
Modalità di frequenza
Facoltativa
Tipologia d'esame
Orale
Propedeutico a
Corsi di informatica del biennio della laurea in Innovazione sociale comunicazione e nuove tecnologie
Oggetto:

Sommario insegnamento

Oggetto:

Obiettivi formativi

L'obiettivo del corso e' quello di fornire una panoramica ei fondamenti teorici dell'informatica.

Verranno analizzati modelli di computazione che sono alla base della nascita e sviluppo dell'informatica e che ancora oggi sono modelli per sistemi automatici.

Partendo poi dal concetti di algoritmo verranno analizzati aspetti quali la calcolabilita', la correttezza e la complessita' degli algoritmi. Vernao quindi discussi alcuni algoritmi classici per problemi complessi (es. navigazione su mappe, crittografia)

Questo presupporra' l'introduzione di basi di logica.

Verra' inoltre analizzata la teoria dei linguaggi, correlandola con i modelli di calcolo e con le probelmatihe legate alla comprensione e traduzione di linguaggi di programmazioen ad alto livello e (accennato) al linguaggio naturale.

Verranno infine introdotti le basi fondazionali della Intelligenza Artificiale

The aim of the course is to provide an overview of he Theoretical foundations of Computer

The models of computation which are teh bases of modern computer science will be introduced and analyzed, showing how they are still teh bases of many automation processes.

Moving from the concept of algorithm we will analyse the notions on computability, correctenedd and computaional complexity. We will discuss soem classicla algorithms for complex problems (finding paths in maps, cryptography)

These topics will require an introduction to mathematical logic.

We will analyse the foundation of formal languages, rekating them to teh computation models and discussing problems related to the design of compilers and translators for programming and natural languages.

Finally we will discuss the foundations of Artificial Intelligence.

Oggetto:

Risultati dell'apprendimento attesi

Competenze di base di Scienze dell'informazioni fondamentali per persorsi successivi in ambito informatico

Skills for entering second level curricula with a focus on Computer Science

Oggetto:

Modalità di insegnamento

Tradizionale lezioni in aula con materiale distribuito nelle risorse didattica e/o in moodle

Traditional classes

Oggetto:

Modalità di verifica dell'apprendimento

Relazione individuale concordata su tema che copra piu' argomenti del corso

 

Individual presentation that covers some of teh topics of the course

Oggetto:

Programma

  1. Logica per `Computer Science
    1. Fondamenti
    2. Calcolo proposizionale
    3. Logica Primo ordine
    4. Inferenza e Concetti di correttezza, completezza, …
  2. Modelli di calcolo e Teoria dei linguaggi
    1. Dagli Automi alla macchina di Turing alle Reti di Petri
    2. Classi di grammatiche e linguaggi formali
    3. Parser, traduttori, compilatori ed interpreti
  3. Logica e specifica dei programmi
    1. Proprieta’, invarianti
    2. Verifiche di proprieta’ dei programmi (correttezza)
    3. Testing
  4. Cenni di calcolabilita’
  5. Cenni di complessita’
    1. Misure e classi di complessita’
    2. Algoritmi e Complessita’ concreta
  6. Algoritmi su strutture dati ricorsive: liste, alberi, grafi
    1. Esempi per problemi classici (es. cammino su mappe)
  7. Cenni di crittografia e sicurezza
  8. Cenni sulla nascita dell'intelligenza artificiale

  1. Logic for Computer Science
    1. Principles
    2. Propositional calculus
    3. First Order Logic
    4. Inferences and properties of inference systems (completeness, correctness, ..)
  2. Models of computation and Formal languages
    1. From Automata to the Turing Machine to Petri Nets
    2. Classes of grammars and languages
    3. Parsers, ttranlators, compilers
  3. Logics and program specification
    1. Proprties, invariants
    2. Verification of program proprties (correctness)
    3. Testing
  4. Computability
    1. Computable and non computable functions
  5. Complexity
    1. Measuring complexity and complexity classes
    2. Algorithms and complexity in practice
  6. Algorithms on recrise data structure: linked lists, trees, graphs
    1. Example of classical algoritms for complex problems (e.g., shortest path)
  7. Basics of Cryptography and security
  8. Basics of Artificial Intelligence

Testi consigliati e bibliografia



Oggetto:
Libro
Titolo:  
Informatica Teorica, Seconda edizione
Anno pubblicazione:  
2011
Editore:  
Città Studi
Autore:  
Dino Mandrioli, Paola Spoletini
ISBN  
Obbligatorio:  
Si
Oggetto:

.

Altro materiale distribuito a lezione


(English version of the textbook)

Theoretical Fondations of Computer Science

Authors: D. Mandrioli, C. Ghezzi

Krieger 1993

Other materials will be provided during the course




Oggetto:

Note

Pre-requisito: i corsi di informatica del primo biennio di ICT.

Per la parte su algoritmi e' vantaggioso seguire il corso in parallelo a quello su Programamzione Object oriented e Java


Required: the Computer Science coursed in the first 2 years of ICT.

Following the part of the course on algorithms in parallel with the couse on Object Oriented Programming and Java is highly recommended.


Oggetto:
Ultimo aggiornamento: 17/09/2022 13:48
Location: https://www.didattica-cps.unito.it/robots.html
Non cliccare qui!