- Oggetto:
- Oggetto:
Calcolabilità e Complessità
- Oggetto:
Computability and Complexity
- Oggetto:
Anno accademico 2022/2023
- Codice dell'attività didattica
- INF0090
- Docente
- Stefano Berardi (Docente)
- Corso di studi
- [008707] Laurea in Informatica
- Anno
- 3° anno
- Periodo didattico
- Primo semestre
- Tipologia
- Caratterizzante
- Crediti/Valenza
- 6 CFU - Numero di ore - Number of hours: 48 (in aula)
- SSD dell'attività didattica
- INF/01 - informatica
- Modalità di erogazione
- Tradizionale
- Lingua di insegnamento
- Italiano
- Modalità di frequenza
- Facoltativa
- Tipologia d'esame
- Scritto
- Prerequisiti
-
Sono richieste buone conoscenze di logica, programmazione e di algoritmi. E' utile ma non indispensabile che lo studente possegga le nozioni di linguaggio formale, grammatica e di automa.
Insegnamenti propedeutici (forniscono le competenze attese in ingresso): Programmazione I e IIThe students are expected to have good competencies on logic, programming and algorithms, and some notions on formal languages, grammars and automata.
Preparatory Courses (providing the expected entry skills): Programmazione I, II - Oggetto:
Sommario insegnamento
- Oggetto:
Obiettivi formativi
Questo insegnamento appartiente all'area Informatica caratterizzante e ha il seguente obiettivo formativo specifico del CdS in Informatica (L31): fornire approfondimenti su linguaggi di programmazione e strumenti correlati, in particolare per quanto riguarda gli strumenti per valutare l'efficienza in tempo e spazio di un algoritmo.
Iniziamo il corso chiedendoci: 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. Si discutono poi i vari possibili criteri di misura delle risorse disponibili (tempo, memoria) e le classi di complessita'. Finiamo presentando il problema P = NP .
This course belongs to the area "Informatica caratterizante", and it has the following specific educational objective of the CdS in Computer Science (L31): to provide insights into programming languages and related tools, in particular with regard to the tools for evaluating the time and space efficiency of an algorithm.
We begin the course by asking ourselves: 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. 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. .
- Oggetto:
Risultati dell'apprendimento attesi
Conoscenza delle definizione del concetto di calcolo in un modo indipendente dalla macchina e dal particolare linguaggio di programmazione usato. Conoscenza dei problemi aperti in questo campo, in particolare P=/=NP. una capacità di classificare i problemi in non risolubili con un programma, in risolubile in tempo tempo polinomiale, in tempo polinomiale non deterministico e in tempo esponenziale, e dei più importanti algoritmi in ognuno di questi gruppi. Un'idea dei limiti delle soluzioni non polinomiali e delle strategie per affrontare tali limitazioni.
CONOSCENZA E CAPACITÀ DI COMPRENSIONE. Classificazione delle risorse di tempo e spazio richieste da un algoritmo e comprensione dei limiti che esse pongono all'utilizzo dei programmi.
CAPACITÀ DI APPLICARE CONOSCENZA E COMPRENSIONE. Capacità di valutare i tempi e spazi di calcolo richiesti dagli algoritmi utilizzati nei corsi.
AUTONOMIA DI GIUDIZIO. Acquisizione dei criteri di base per confrontare l' efficenza in tempo e spazio tra diverse soluzioni di un problema.
ABILITÀ COMUNICATIVE. Capacità di capire le richieste di tempi di calcolo e di spazio di memoria attese per un programma, e di comunicare tempi e spazi effettivamente realizzati.
CAPACITÀ DI APPRENDIMENTO. Acquisizione di capacità autonome di apprendimento e di autovalutazione della propria preparazione in teoria della complessità.
Knowledge of the definition of the concept of computation in a way independent from the machine and from the particular programming language used. Knowledge of open problems in this field, in particular of P=/=NP. An ability to classify problems into non-computable, solvable in polynomial time, solvable in nondeterministic polynomial time, and in exponential time, and the major algorithms representative for each of these groups. An idea of the limitations of non-polynomial solutions and strategies for dealing with those limitations.
KNOWLEDGE AND UNDERSTANDING. Classification of time and space resources required by an algorithm and understanding of the limits they place on the use of programs.
APPLYING KNOWLEDGE AND UNDERSTANDING. Ability to evaluate the computational time and space required by the algorithms used in the courses.
MAKING JUDGMENTS. Acquisition of the basic criteria to compare the efficiency in time and space between different solutions to a problem.
COMMUNICATION SKILLS. Ability to understand the requests for calculation times and memory space expected for a program. Ability to communicate times and spaces actually achieved.
LEARNING SKILLS. Acquisition of autonomous learning skills and self-assessment of one's preparation in complexity theory.
- Oggetto:
Modalità di insegnamento
In presenza con lezioni registrate. Utilizziamo la piattaforma Moodle sia per inviare messaggi agli studenti che per distribuire il materiale del corso.
- Oggetto:
Modalità di verifica dell'apprendimento
Esame scritto in presenza, fatto di due parti. Nella prima parte dell'esame, indicativamente di 25 minuti, lo studente deve rispondere a delle domande a risposta chiusa formulate sul sito Moodle di esame, e le cui risposte vengono valutate automaticamente da moodle. Nella seconda parte dell'esame, indicativamente di 90 minuti, lo studente deve rispondere a delle domande a risposta aperta formulate sullo stesso sito, le cui risposte vengono corrette manualmente.
Written exam, made in presence, in two parts. In the first part of the exam, about 25 minutes, the student must answer closed-ended questions formulated on the Moodle exam site, and whose answers are automatically evaluated by Moodle. In the second part of the exam, about 90 minutes, the student must answer open-ended questions formulated on the same site, the answers to which are corrected manually.
- Oggetto:
Programma
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 completiDefinizione di PSPACE e NPSPACE. Teorema di Savich. Inclusioni P in NP in PSPACE in EXPTIME. Classi L e NL e inclusioni note.
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 Definition of PSPACE and NPSPACE. Savich Theorem. Inclusions of P in NP in PSPACE in EXPTIME. The classes L e NL and known inclusions. .
Testi consigliati e bibliografia
- Oggetto:
- Libro
- Titolo:
- Introduction to the theory of Computation
- Anno pubblicazione:
- 2004
- Editore:
- Thompson Course Technology
- Autore:
- M. Sipser
- ISBN
- Capitoli:
- 3,4,5,7
- Obbligatorio:
- No
- Oggetto:
