Prove d'esame Modelli

Esami e prove d'esame

Esame 08/06/2021 - Avenerdì 8 luglio 2022 15:33

Prove d'esame Modelli Pagina 1

Prove d'esame Modelli Pagina 2

Esame 13/06/2019 - Asabato 9 luglio 2022 12:37

Prove d'esame Modelli Pagina 3

Prove d'esame Modelli Pagina 4

Prove d'esame Modelli Pagina 5

Esame 17/09/2019 sabato 9 luglio 2022 16:14

Prove d'esame Modelli Pagina 6

Prove d'esame Modelli Pagina 7

Prove d'esame Modelli Pagina 8

Esame 09/07/2019 domenica 10 luglio 2022 10:16

Prove d'esame Modelli Pagina 9

Prove d'esame Modelli Pagina 10

Prove d'esame Modelli Pagina 11

Esame 05/11/2019 lunedì 11 luglio 2022 10:20

Prove d'esame Modelli Pagina 12

Prove d'esame Modelli Pagina 13

Esame 17/01/2020 lunedì 11 luglio 2022 16:32

Prove d'esame Modelli Pagina 14

Prove d'esame Modelli Pagina 15

Esame 14/02/2020 martedì 12 luglio 2022 10:54

Prove d'esame Modelli Pagina 16

Prove d'esame Modelli Pagina 17

Esame 11/05/2020 martedì 12 luglio 2022 15:27

Prove d'esame Modelli Pagina 18

Prove d'esame Modelli Pagina 19

Esame 19/07/2021 mercoledì 13 luglio 2022 10:16

Prove d'esame Modelli Pagina 20

Prove d'esame Modelli Pagina 21

Esame 07/06/2022 mercoledì 13 luglio 2022 15:43

Prove d'esame Modelli Pagina 22

Macchina di Turing universale

Data una MdT e una sua descrizione DM, esiste una Macchina di Turing universale U che esegue una computazione del tipo prendendo in input 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: 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.

Tesi di Church-Turing

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 considerata 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.

4DNF e algoritmo DPLL

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

Esame 13/06/2019 - Bgiovedì 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

Valutazione del costo dei programmi

• 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.
• 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.
• L'analisi tight viene definita con la notazione := data una funzione t(n).