Introduzione al corso e Automi

Elementi di Teoria della Computazione

Prof. C. De Felice

Lezione 0: Introduzione al corso

3 aree centrali della teoria della c.

• Teoria degli Automi
• Teoria della Calcolabilità
• Teoria della Complessità

La domanda, però, rimane la stessa:

Quali sono le capacità e i limiti dei computer

Teoria degli Automi

Lo scopo della teoria degli automi è studiare definizioni e proprietà dei modelli di computazione.

I modelli di computazione vengono classificati in base a restrizioni sulle risorse di memoria.

La caratteristica comune di tali modelli è che possono trovarsi in un numero finito di stati.

Essi dispongono di risorse di memoria differenti e quindi di potere computazionale diverso.

Il modello più semplice è l'automa a stati finiti, l'altro la macchina di Turing.

Questi modelli sono considerati come riconoscitori di linguaggi, piuttosto che come macchine che dato un input producono un output.

Elementi di Teoria della Computazione

Lezione 0: Introduzione al corso

3 Aree Centrali della Teoria della C.

• Teoria degli Automi
• Teoria della Calcolabilità
• Teoria della Complessità

La domanda, però, rimane la stessa:

Quali sono le capacità e i limiti dei computer

Teoria degli Automi

Lo scopo della teoria degli automi è studiare definizioni e proprietà dei modelli di computazione.

I modelli di computazione vengono classificati in base a restrizioni sulle risorse di memoria.

La caratteristica comune di tali modelli è che possono trovarsi in un numero finito di stati.

Essi dispongono di risorse di memoria differenti e quindi di potere computazionale diverso.

Il modello più semplice è l'automa a stati finiti, l'altro la macchina di Turing.

Questi modelli sono considerati come riconoscitori di linguaggi, piuttosto che come macchine che dato un input producono un output.

Teoria della Calcolabilità

La teoria della calcolabilità studia quali problemi possono essere risolti con un calcolatore.

Trovare una soluzione algoritmica per un problema può essere arduo, in molti casi è impossibile.

Le domande che si pone sono:

1. Quali sono i problemi risolvibili mediante una procedura effettiva?
2. Esistono problemi irrisolvibili?

Gödel, Turing e Church I 10 problemi di Hilbert.

Teoria della Complessità

Si fa distinzione tra problemi "semplici" e problemi "difficili". Anche di algoritmi efficienti e inefficienti.

Problema del commesso viaggiatore

La teoria cerca di capire le ragioni di questa complessità.

Raggruppiamo in una classe tutti i problemi che possono essere risolti con algoritmi della stessa complessità. (Di tempo o di spazio)

La teoria della complessità analizza problemi solubili

Scopo: quantificare le risorse in tempo e lo spazio necessarie a risolvere un problema dato, in funzione della taglia dell'input.

Classificare i problemi (solubili) in base alla difficoltà computazionale.

La classe P che corrisponde alla classe dei problemi risolvibili con un algoritmo di complessità in tempo polinomiale (caso peggiore) e la classe NP.

Uno dei più grandi problemi aperti dell'informatica P=NP?

Lezione 1: Nozioni Matematiche e terminologia

Insieme

Un INSIEME è una collezione non ordinata di oggetti o elementi distinti.

Gli oggetti possono contenere qualsiasi tipo di oggetto, inclusi numeri, simboli e altri insiemi.

Ordine e ridondanza non contano

{3,3 ed 1 sono però oggetti diversi.

Sottoinsieme e sottoinsieme proprio

Moltinsieme

Tipi di Insieme

• U (Universo)
• Vuoto
• Singleton
• Coppia non ordinata
• Ξl m regole per m∋

Esempi

• Quadri Ξl m l m = m², m∈N3
• Pari Ξ2 ml m ≥ 1, m∈N3

Operazioni

• Unione
• Intersezione
• Complemento

Definizione Ricorsiva

Il Passo Base definisce uno o più elementi (elementi, dell'insieme.Il Passo Ricorsivo definisce regole per formare nuovi elementi dell'insieme da elementi già definiti.

Esempio

Sia A l'insieme definito ricorsivamente nel modo seguente: Passo base: 1 2 4 3Passo ricorsivo: Se k ∈ A allora i _i=k+2 ∈ A

Cardinalità

La cardinalità |S| di un insieme S è il numero di elementi in S