Periodo |
Giorno |
Settimana |
Orario |
Aula |
1 |
LUN |
1 |
14:00 - 16:00 |
Aula F |
|
1 |
GIO |
1 |
14:00 - 16:00 |
Aula E |
|
1 |
VEN |
1 |
9:00 - 11:00 |
Aula F |
|
1. Prerequisiti - Prerequisites
-
Italiano
-
Competenze attese in ingresso (richieste all'inizio del corso)
Sono richieste buone conoscenze di logica, programmazione e di
algoritmi; inoltre si assume che lo studente possegga le nozioni di
linguaggio formale, grammatica e di automa.
-
Eventuali corsi propedeutici (forniscono le "competenze attese in ingresso")
Matematica Discreta e Logica, Programmazione 1 e 2, Algoritmi e Strutture Dati, Linguaggi Formali e Traduttori.
-
English
-
Required incoming expertise
The students are expected to have good competencies on logic,
programming and algorithms, and some notions on formal languages,
grammars and automata.
-
Preparatory Courses
Matematica Discreta e Logica, Programmazione 1 e 2, Algoritmi e Strutture Dati, Linguaggi Formali e Traduttori.
2. Obiettivi formativi - Learning objectives
-
Italiano
Che cos'e' un algoritmo? Quali problemi si possono risolvere con un
algoritmo? E in quali casi un algoritmo richiede risorse inaccessibili
nella pratica?
Il corso affronta questi problemi, trattando anzitutto la teoria della
computabilita' sia dal punto di vista matematico - macchine di Turing,
funzioni ricorsive - che da prospettive legate ai linguaggi di
programmazione, come quella dei programmi while. Si discutono poi i vari
possibili criteri di misura delle risorse disponibili (tempo, memoria,
cpu) e le classi di complessita'. Finiamo presentando il problema P = NP
.
-
English
What is an algorithm? which problems can be solved by algorithms? and
what is the amount of resources an algorithm requires?
In this course this kind of problems will be discussed. The
computability theory is presented, following not only the classical
approach - Turing machines, recursive functions- but also more actual
presentations, like while programs. Then the various methods of
measuring the resources necessary to compute (time, space) will be
discussed, and the various complexity classes will be presented. We
eventually introduce the problem P=NP.
3. Risultati dell'apprendimento attesi - Learning outcomes
4. Programma - Course Syllabus
-
Italiano
Teoria della computabilita'
- Le Macchine di Turing
- Problemi non risolubili
- Funzioni ricorsive
- Calcolabilita' e Linguaggi di Programmazione
Teoria della complessita'
- Misure e classi di Complessita'
- Classi di Complessita' Temporale
- Classi di Complessita' Spaziale
- Le classi P ed NP
- Problemi NP completi
-
English
Theory of computable functions
- Turing Machines
- Unsolvable problems
- Recursive functions
- Computability and programming languages
Complexity theory
- Complexity measures and classes
- Temporal complexity classes
- Spatial complexity classes
- The classes P and NP
- NP-complete problems
5. Modalità di verifica dell'apprendimento - Course grade determination
Esame orale.
5.1 Controllo dell'apprendimento durante il corso
Il docente proporra' ed incoraggera' lo svolgimento di esercizi. Tali
svolgimenti, pur non avendo valore ai fini del voto di esame, saranno
corretti e discussi in classe, e fanno parte della preparazione
all'esame.
6. Modalità d'insegnamento - Course structure
Le lezioni si svolgono in aula, ed utilizzano la piattaforma
Moodle sia per inviare messaggi agli studenti che per le verifiche
dell'apprendimento durante il corso.
7. Attività di supporto - Optional activities
Vedi il sito moodle del corso
8. Testi consigliati e bibliografia - Reading materials
L'unico libro di testo del corso e' il seguente:
M. Sipser:"Introduction to the theory of Computation", Course Technology Ptr., 3^edition, 2012.
Le sezioni effettivamente svolte verranno indicate alla fine dell'anno.
(Per chi desiderasse rivedere in italiano i concetti del testo
inglese, segnaliamo il testo: C. Toffalori et alii, Teoria della
calcolabilita' e della complessita', McGraw-Hill 2005. Ribadiamo che,
tuttavia, questo testo non viene utilizzato nel corso.)
9. Commissione d'esame - Examination Committee
BERARDI, Stefano
CARDONE, Felice
COPPO, Mario
DE' LIGUORO, Ugo
RONCHI DELLA ROCCA, Simonetta