Linguaggi e Sistemi


Logica per l'Informatica 17/18

Si vogliono fornire agli studenti strumenti formali per il ragionamento rigoroso sia in linguaggio naturale che in linguaggi formali. Si vuole utilizzare la logica come strumento per una descrizione rigorosa della specifica di un programma e per porre le basi della verifica automatica di proprietà di programmi.

Calcolabilita e Complessita A e B 2017


 

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)

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




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

    • 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