Calcolabilita e Complessita A e B 2018
Calcolabilita' e Complessita' A e B
English title: Computability and Complexity - A and B
Codice attività didattica - Activity Code: MFN0612
Numero di CFU - Credits: 6
SSD attività didattica - Scientific Sector of Activity: INF/01 - INFORMATICA
Docenti (attuali responsabili) - Teaching Staff:
- Stefano BERARDI (Titolare)
Erogazione - Teaching Modality: Tradizionale
Lingua - Language: Italiano
Frequenza - Attendance: Facoltativa
Numero di ore - Number of hours: 60 (in aula)
Orari e organizzazione dei moduli - Timetable and module structure:
Periodo | Giorno | Settimana | Orario | Aula |
---|---|---|---|---|
1 | LUN | tutte | 14:00 - 16:00 | Aula F |
1 | GIO | tutte | 14:00 - 16:00 | Aula E |
1 | VEN | tutte | 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.
- Competenze attese in ingresso (richieste all'inizio del corso)
- 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.
- Required incoming expertise
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' dal punto di vista delle macchine di Turing. 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 the classical approach - Turing machines. 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
- Competenze attese in uscita (acquisite durante il corso)
Conoscenza delle definizione del concetto di calcolo, una maggiore consapevolezza delle limitazioni intrinseche all'uso delle macchine ed un'idea delle strategie per sopperire a tali limitazioni.
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
- 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
Il 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.
9. Commissione d'esame - Examination Committee
BERARDI, Stefano
CARDONE, Felice
COPPO, Mario
DE' LIGUORO, Ugo
RONCHI DELLA ROCCA, Simonetta
Reti di Elaboratori
Il corso studia gli elementi fondamentali delle tecnologie di
trasmissione del livello data link, dei protocolli di accesso a mezzi
condivisi e dei protocolli di trasmissione wireless, la suite di
protocolli TCP/IP, e i principi che guidano la strutturazione e la
progettazione di applicazioni distribuite.