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:

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:

Compl A (BERARDI Stefano)

PeriodoGiornoSettimanaOrarioAula
1LUNtutte14:00 - 16:00Aula F
1GIOtutte14:00 - 16:00Aula E
1VENtutte9:00 - 11:00Aula 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' 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


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.