Appunti completi Fondamenti di informatica

Operatori di confronto

Le proposizioni logiche possono essere formate da operatori di confronto, o di relazione come maggiore, minore, uguale, diverso, maggiore o uguale, minore o uguale. Maggiore, minore, e maggiore o uguale e minore uguale si possono usare solo con elementi che rispettano una relazione d'ordine, mentre uguale o diverso non necessitano di questo requisito.

Esempio:

SE (bollettini-consegnati < 5 OR NOT ci-sono-utenti-in-coda) ALLORA bollettini-consegnati++

Oppure:

SE (NOT(bollettini-consegnati >= 5 AND ci-sono-utenti-in-coda)) ALLORA bollettini-consegnati++

Tramite la logica booleana è facile calcolare la verità di un predicato che contiene operatori logici a partire dalla verità dei predicati che lo compongono; è quindi notevolmente semplificata la possibilità di verificare l'equivalenza di predicati complessi, e di trasformarli per individuare

La formulazione più conveniente.

Algebra di Boole

Una algebra astratta è costituita da un insieme K (detto sostegno), e due leggi binarie di composizione interna ( e ), quindi è definita da una terna K ,+,+.

L'algebra di Boole è una particolare algebra astratta che ha altre caratteristiche. È possibile definirla secondo vari metodi, uno di questi è mediante i reticoli.

Reticoli

Assiomi

L'algebra di Boole è definita da 7 proprietà, ciascuna con un suo assioma per e per+.

• Una algebra astratta è detta reticolo se per ogni elemento di K valgono per entrambi le leggi binarie di composizione interna le proprietà: commutativa (l'ordine degli operandi non cambia il risultato), associativa (l'ordine nel quale una stessa operazione è calcolata tra più operandi non cambia il risultato), idempotenza (ossia che

equivalente per ), ed assorbimento (ossia a + a = a che è equivalente per ). a + ab = a I reticoli sono ordinati, ossia posseggono una relazione d'ordine tale che ≤ ⇔ (si ricorda che una relazione d'ordine deve godere delle proprietà: ≤ y x + y = y ⇒ riflessiva, antisimmetrica () e transitiva) x ≤ y e y ≤ x x = y 2. Un reticolo è distributivo se per ogni elemento di K vale la proprietà distributiva sia () ⋅ ⋅ ⋅ ⋅ = a rispetto a , che di rispetto a : , ea b + c b + a ⋅ c + ¿ + ¿ () = () ⋅ ⋅ (a + a + b c a + b c) 3. Un reticolo distributivo si dice dotato di minimo e massimo assoluti se in K esistono due elementi, detti per comodità 0 e 1, che verificano rispettivamente le ⋅ 0 = 0 proprietà del minimo e del massimo: ea a + 1 = 1 4. Un reticolo distributivo si dice complementato se per ogni elemento di K esiste ed è unico un elemento per il quale è valida la proprietà delcomplemento:
á⋅a=0 eá á+ a=1
Gli assiomi per e sono equivalenti, se non per le proprietà del massimo e–+¿minimo. Pertanto, si può introdurre la proprietà di dualità, che afferma che le operazioni⋅di e in una identità sono intercambiabili a patto di scambiare il minimo ed il+¿massimo (0 e 1), ovvero di considerare il complemento (NOT) di ogni variabile.
Un reticolo distributivo, dotato di minimo e massimo assoluti e complementato, si dice´un’algebra di Boole. In altre parole, è pari alla sestupla ⋅,¿ ❑,K ,+, 0, 1>¿
La precedenza tra gli operatori logici è in ordine decrescente: NOT, AND, OR.
Proprietà derivate
Convoluzione: negando due volte un elemento si ottiene l’elemento stesso.
⋅ ⋅ ma il complemento di deve essere unico, quindia á=0 ; á á=0, á a=á
Elementi neutri: 0 e 1 sono gli elementi neutri rispettivamente della somma e del

prodotto.Considerando le proprietà dell’assorbimento con pari a 0 quando èb( )=a ( )⋅ =amoltiplicato, e pari a 1 quando è sommato ( , e ),a+ a⋅ 0 a a+1usando le proprietà del minimo e massimo le operazioni tra eb aequivalgono a , quindi sostituendo nelle proprietà dell’assorbimento scritteb ⋅1=asi ottengono identità che dimostrano l’enunciato: e .a+0=a a

Assorbimento del complemento:
• a+ á b=a+b
Si dimostra usando la proprietà distributiva ed infine il complemento.´ ´

Teorema di De Morgàn:
• ⋅a+b=á b́ , a⋅ b=á+ b́
A partire dalle tesi, usando la proprietà del complemento, dove nel primo casosi somma il complemento del primo membro e nel secondo si moltiplica, siottengono due tesi equivalenti:( )1=( ) ⋅+a+b á b́ , 0=( á+ b́)( a⋅ b)
A partire dal secondo membro di ciascuno, usando la proprietà associativa epoi del complemento si ottiene il

primo membro e quindi si dimostrano le tesi.( )b́=( ) =( ) ( )⋅ ⋅ ⋅+ =1⋅a+b á a+b+ á a+ b+ b́ 1+b a+1 1=1( ) ( )=a ⋅ ⋅0=0á+ b́ ab á b+ab b́=b 0+a0 e 1 sono l’uno il complemento dell’altro.

Altre algebre di Boole ´L’algebra di Boole definita mediante reticoli non specifica quali siano le operazioni ⋅,+, ❑, ma solo le loro proprietà. Per questo motivo è possibile definire algebre di Boole con leproprie simbologie e specifiche; un esempio è l’algebra degli insiemi (con sestupla¿ >¿ ), o un altro esempio è l’algebra dei circuiti.K ,∪ , ∩, ¬ ,Φ ,T

Esercizio:

1) NOT a OR NOT b AND NOT c AND b AND NOT a OR b

Con precedenze evidenziate: (NOT a) OR ((NOT b) AND (NOT c) AND b AND (NOT a)) OR b

In reticoli: ⋅b+ ⋅ ⋅(b ⋅ ⋅ ⋅0+b=á+bá+ á⋅ b́⋅ ć b= á+ á ć b́)+ b=á+ á ć( )

(Più rapidamente:

• ⋅ ⋅ ⋅ +b=á+á+ á⋅ b́⋅ ć b+ b= á 1+ b́ ć b b2) a OR NOT a AND bb=( ) ( )=1 ( )=a+⋅ ⋅ ⋅
• In reticoli: a+ á⋅ a+ á a+b a+b b⇒ a+ á b=a+ b
• Scrittura duale: ⋅á a+ b́=á⋅ b́

Algoritmi ed elaboratori

Ci sono diverse fasi per la manipolazione delle informazioni volta alla risoluzione di un problema: principalmente, consistono nell’analisi del problema, e la successiva progettazione di una soluzione, ossia di un algoritmo, che tratti delle informazioni in modo corretto ed efficiente. Tale soluzione può inoltre richiedere manutenzione, ossia l’applicazione di modifiche o migliorie mentre l’algoritmo è applicato, difatti anche tale passaggio è incluso nel procedimento di risoluzione.

Un algoritmo è definito come una sequenza precisa di operazioni il cui svolgimento sequenziale è necessario per la soluzione di un problema dato.

Il concetto di algoritmo è alla base

della programmazione procedurale, ossia la risoluzione di un problema mediante una sequenza esplicita di operazioni. Dividere un problema in problemi più semplici (dal generale al particolare) è invece un approccio definito top-down, mentre partire da moduli elementari per risolvere un problema è definito bottom-up. Considerando gli algoritmi, l'informatica può essere definita come lo studio sistematico di essi. Si definisce specifica la descrizione in linguaggio naturale del problema da risolvere, e l'algoritmo è la soluzione del problema da essa descritto. Con la specifica vanno considerate anche le informazioni in ingresso (input) e quelle in uscita (output). È da notare che, così come esistono problemi risolvibili mediante algoritmi efficienti, esistono anche problemi non risolvibili, così come altri non risolvibili in modo efficiente. Colui che è in grado di risolvere il problema eseguendo l'algoritmo èin generale definito esecutore. In particolare, il calcolatore è un esecutore di algoritmi progettato in modo che abbia una potenza tale da poter gestire una quantità di informazioni altrimenti non trattabili, mediante l'esecuzione rapida e autonoma di operazioni "elementari" che possono combinarsi rappresentando varie attività. La descrizione di un algoritmo in un linguaggio comprensibile ad un calcolatore è detto programma, ed il linguaggio in cui esso viene scritto è detto linguaggio di programmazione. Si definisce processo il lavoro svolto eseguendo l'algoritmo, ossia la sequenza delle azioni svolte nel tempo, e processore il suo esecutore. Poiché i valori associati alle variabili in ingresso possono far variare le azioni eseguite mediante un programma, si distinguono la sequenza statica, o lessicografica, come l'insieme di tutte le possibili sequenze di azioni eseguibili, e la sequenza dinamica come l'effettiva sequenza di azioni eseguite durante l'esecuzione del programma.

sequenza di istruzioni eseguite. Esempi concreti di dati in ingresso e icorrispettivi dati in uscita attesi rispetto a varie esecuzioni costituiscono i casi di test.

Esempio:

Input: bollettini consegnati, utenti in coda, orario di apertura

Funzioni: APRI_postazione, CHIUDI_postazione, SERVI_cliente

INIZIO
IMPOSTA ora_chiusura = 18, max_richieste = 5; //identificatori
APRI_postazione
MENTRE (ora_attuale < ora_chiusura) RIPETI{
    SE (cliente_diverso == VERO) ALLORA {
        IMPOSTA richieste_utente = 0
    }
    SE ((richieste_utente < max_richieste) OR (utenti_coda == 0)) ALLORA{
        IMPOSTA richieste_utente = richieste_utente + 1
        SERVI_cliente
    }
}
CHIUDI_postazione
FINE

Architettura degli elaboratori

Un modello è una rappresentazione semplificata della realtà volta ad analizzarne degli aspetti precisi.

Il modello di Von Neumann (pronunciato "Von Nòimann") descrive la struttura semplificata di un calcolatore generico, dato dai suoi componenti e le interazioni reciproche. Il modello fu

proposto nel secondo Dopoguerra, quando i calcolatori costruiti erano ancora ad uno stadio primitivo ed era quindi necessario definire un modello per la loro costruzione. Inoltre, fino ad allora i calcolatori costruiti avevano solo uno scopo bellico e non erano facilmente riprogrammabili. Secondo il modello di Von Neumann, un calcolatore può essere visto come l'interazione di più sottosistemi, o organi, ciascuno dedito a scopi ben precisi: - La memoria ha lo scopo di memorizzare un programma ch