Prove d'esame Modelli

Elenco delle prove d'esame

09/07/2019 - Prove d'esame Modelli Pagina 9

10/07/2019 - Prove d'esame Modelli Pagina 10

11/07/2019 - Prove d'esame Modelli Pagina 11

05/11/2019 - Prove d'esame Modelli Pagina 12

06/11/2019 - Prove d'esame Modelli Pagina 13

17/01/2020 - Prove d'esame Modelli Pagina 14

18/01/2020 - Prove d'esame Modelli Pagina 15

14/02/2020 - Prove d'esame Modelli Pagina 16

15/02/2020 - Prove d'esame Modelli Pagina 17

11/05/2020 - Prove d'esame Modelli Pagina 18

12/05/2020 - Prove d'esame Modelli Pagina 19

19/07/2021 - Prove d'esame Modelli Pagina 20

20/07/2021 - Prove d'esame Modelli Pagina 21

07/06/2022 - Prove d'esame Modelli Pagina 22

Data una MdT e una sua descrizione DM allora esiste una Macchina di Turing universale U che esegue una computazione del tipo prendendo...

ininput la descrizione della MdT DM e una stringa x se e solo se la MdT M esegue una computazione

Si può dimostrare che la macchina U può simulare una qualsiasi MdT M prendendo in input una sua descrizione DM. Quindi se pensiamo alla macchina U come formata da tre nastri dove il nastro #1 contiene la descrizione DM, il nastro #2 contiene le quintuple di M e il nastro #3 è il nastro di lavoro a cui U si appoggia per effettuare le computazioni di M dettate dalle quintuple.

Quindi U non fa altro che effettuare le computazioni di M ed eliminare alla fine la descrizione DM dal nastro #1.

Questo implica che la macchina U può simulare se stessa se in input le passiamo la sua descrizione DU, quindi questa non farà altro che simulare le computazioni dettate dalle quintuple di U simulando se stessa.

La tesi di Church-Turing afferma che qualunque algoritmo per qualsiasi modello di calcolo può essere simulato da una Macchina di Turing. Questa tesi è

giustificabile considerando che ogni modifica apportata ad una MdT non cambia la sua potenza computazionale, questo implica che una MdT può variare senza cambiare la sua potenza computazionale in modo da simulare qualsiasi algoritmo T-calcolabile.

La tesi non vale per gli ASFND dato che la MdT può essere considerato come un automa a stati finiti deterministico + nastro infinito, con accesso sequenziale e bidirezionale. Questo significa che solo gli algoritmi riconosciuti da un ASFD sono simulabili da una MdT.

La 4DNF è formata da clausole di 4 letterali in and collegate tra di esse in or. Si può pensare ad ogni clausola della 4DNF come una formula in CNF formata solo da clausole unitarie a cui si può applicare pure-literal-asign seguendo l'algoritmo di DPLL. Inoltre sappiamo che una formula in DNF essendo formata da clausole in OR è soddisfatta se è soddisfatta almeno una clausola. Quindi si può applicare l'algoritmo DPLL ad

una formula in 4DNF clausola per clausola finché almeno una clausola non è soddisfatta, interrompendo immediatamente l'esecuzione dell'algoritmo. Se nessuna clausola è soddisfatta allora la formula in 4DNF non è soddisfacibile. Se almeno una clausola è soddisfatta allora la formula in 4DNF è soddisfacibile.

Prove d'esame Modelli Pagina 23

interrompendo immediatamente l'esecuzione dell'algoritmo. Se nessuna clausola è soddisfatta allora la formula in 4DNF non è soddisfacibile. Se almeno una clausola è soddisfatta allora la formula in 4DNF è soddisfacibile.

Prove d'esame Modelli Pagina 24

Esame 13/06/2019 - B

giovedì 14 luglio 2022 10:08

Prove d'esame Modelli Pagina 25

Prove d'esame Modelli Pagina 26

Esame 27/01/2022

giovedì 14 luglio 2022 12:20

Le notazioni che vengono utilizzate per descrivere la valutazione del costo dei programmi in funzione della dimensione dell'input sono upper bound, lower bound e analisi tight1. L'upper bound viene definito con la notazione O(.) O-grande := data una funzione t(n) questa O(f(n))

<=> t(n)<=c*f(n) con c esistente >0 e n>=n0 condizione iniziale per il calcolo del costo => l'upper bound definisce il costo massimo che un determinato algoritmo può avere in funzione dell'input n nel caso peggiore

2. Il lower bound viene definito con la notazione := data una funzione t(n) questa <=>t(n) >=c*g(n) con c esistente >0 e n>=n0 condizione iniziale del calcolo del costo => il lower bound fornisce il costo minimo che un determinato algoritmo può avere in funzione dell'input n nel caso migliore

3. L'analisi tight viene definita con la notazione := data una funzione t(n) questa <=>=> l'analisi tight fornisce il costo preciso e corretto, caratterizzato dal fatto che il lower bound e l'upper bound coincidono, dell'algoritmo in funzione dell'input n

Il problema di SAT appartiene alla classe NPDIM in 3 passi:

1. Si considera il problema di SAT formato da n variabili con valore vero o falso

> ci saranno 2^n possibili assegnazioni dei valori2. Si considera un algoritmo non deterministico che utilizza il passo GUESS per creare tutte le 2^n possibili assegnazioni delle n variabili in tempo polinomiale3. Si verificano gli AND in tempo polinomiale=> SAT appartiene ad NP perché è simulabile attraverso un algoritmo non deterministico che utilizza GUESS da una NTM in tempo polinomiale. Data un MdT M e una sua descrizione DM, esiste una Macchina di Turing Universale U che prende in input una stringa x e la descrizione DM della macchina M ed effettua una computazione del tipo<=> la macchina M esegue la computazione. Il risultato che dimostra l'esistenza di una MdT universale è importante perché presa in input la descrizione di una qualsiasi macchina M la macchina universale può simulare la macchina M => ogni problema T-calcolabile può essere calcolato da una macchina di Turing universale. Il fatto che la MdT universale possa

Simulare una MdT M viene dimostrato considerando la macchina U formata da tre nastri: nastro #1 prende in input la descrizione DM della TM M, il nastro #2 contiene le quintuple che caratterizzano le computazioni della TM M e il nastro #3 è un nastro di lavoro utilizzato dalla macchina U come appoggio per effettuare le computazioni di M dettate dalle sue quintuple. La macchina U non fa altro che effettuare le computazioni di M e poi cancellare la descrizione DM in input => la macchina U può simulare una qualunque TM.

Il problema della fermata o Halting Problem è un problema indecidibile o non T-calcolabile. Questo significa che non è simulabile attraverso una MdT.

Consideriamo una MdT M con descrizione CM e una stringa x fornita in input, l'halting problem si può considerare come una funzione h(CM, x) che restituisce 1 se h termina con l'input x e 0 se h non termina con l'input x.

DIM HP non T-calcolabile per assurdo. Supponendo che esista una

macchina H che riesce a simulare l'algoritmo h, allora si può creare una MdTH' formata dalla concatenazione della macchina H e di una macchina C che duplica la stringa in input in modo che la funzione h prenda in input solo la descrizione CM della macchina M. In seguito si può costruire una macchina H'' formata dalla concatenazione di H' e una macchina E che cicla se la funzione h(CM) termina su input CM e termina se la funzione h(CM) non termina sull'input CM. Se, però, forniamo in input alla funzione h la descrizione CH'' della macchina H'' allora si arriva ad una contraddizione perché l'algoritmo dovrebbe ciclare quando la funzione h(CH'') termina sull'input CH'' e terminare quando non termina sull'input CH''. Questo però crea una contraddizione con la descrizione di H'' che non può mai terminare sull'input CH'' dato che entra in

un loop infinito. Questo assurdo porta alla conclusione che la macchina H'' formata dalle macchine C, E ed H'' non può esistere e quindi non può esistere neanche la macchina H. L'HP non è T-calcolabile. Prove d'esame Modelli Pagina 27