Calcolabilita' e Complessita' A e B

Docenti (attuali responsabili) - Teaching Staff:

• Stefano BERARDI (Titolare)

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

• 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
  • 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