Torna alla pagina di Programmazione degli Elaboratori

Torna alla pagina di Programmazione degli Elaboratori

Torna alla pagina di Programmazione degli Elaboratori

:: Capitolo 1: Concetti di base ::

Torna alla pagina di Tetty? | Guarda le domande sul capitolo

UniCrema

La logica dei predicati mette inoltre a disposizione due utili elementi, i quantificatori, grazie ai quali è possibile specificare se le variabili di una data proposizione si riferiscono a tutte le loro istanze o solo ad un numero più ristretto. Ne esistono di due tipi, quello esistenziale ∃ (“esiste”) e quello universale ∀ (“per ogni”). Molto importante ricordare come i quantificatori possano essere applicati alle sole variabili libere di una formula.

L'algoritmo è una procedura passo per passo grazie alla quale un'operazione può essere svolta senza alcun esercizio di intelligenza e quindi, per esempio, da una macchina. Se il suo scopo è quello di risolvere problemi, capite bene con quanti algoritmi abbiamo a che fare tutti i giorni. Un esempio legittimo di algoritmo potrebbe essere perfino una ricetta di cucina?.

• poter essere risolto in un numero finito di operazioni, perché va da sé che se il numero fosse infinito non si arriverebbe mai a risolvere il problema. Ad esempio, se trovare i primi dieci numeri primi è un algoritmo (basta applicare determinate operazioni per un numero finito di volte), trovare tutti i numeri primi non lo è più (le operazioni da eseguire sono le stesse, ma non si finirà mai di ripeterle);

L' analisi di un algoritmo è lo studio della sua complessità computazionale, che dipende dalla quantità di risorse necessarie alla sua esecuzione, a loro volta strettamente dipendenti dalla difficoltà del problema da risolvere. Le due risorse principali sono:

Lo spazio e il tempo dipendono fortemente dal particolare ingresso dell'algoritmo, quindi per il loro studio non possiamo interessarci di pochi casi particolari, ma di una statistica su tutte le possibili esecuzioni. Le statistiche possibili sono tre (caso migliore, caso medio, caso peggiore), ma l'analisi degli algoritmi si concentra sul caso peggiore (maggior impiego di tempo e di spazio possibile) per tre buoni motivi:

Ciò che però realmente determina la complessità di un algoritmo non è la quantità precisa di risorse, ma l' ordine, ovvero il suo tasso di crescita (logaritmico, lineare, cubico, esponenziale, ...) al crescere delle dimensioni dell'ingresso. Ovviamente più l'ordine è basso e più l'algoritmo è semplice ed efficiente.

Dati n insiemi U₁, U₂, ... U_n, il loro prodotto cartesiano U₁ X U₂ X ... X U_n è l'insieme di tutte le n-uple ordinate (u₁ X u₂ X ... X u_n) dove u_i ∈ U_i per i = 1, 2, ... , n.

Dati due insiemi A e B, una funzione f di dominio A e codominio B è una mappa che associa ad ogni elemento a ∈ A un elemento b = f(a) ∈ A. In formula, f: A → B.

La logica dei predicati è un passo avanti nel livello di astrazione della descrizione degli eventi, perché offre strumenti di descrizione molto più potenti e versatili di quelli della logica delle proposizioni. Facendo un esempio, se abbiamo dieci lampadine e dobbiamo dire se funzionano o se sono fulminate, nella logica delle proposizioni dovremo definire una proposizione per ogni lampadina. Il che può andare bene quando le lampadine sono dieci, ma quando sono diecimila? E' qui che giunge in soccorso la logica dei predicati, in grado di parametrizzare e quindi "riassumere" i vari eventi.

Le tabelle di verità sono tabelle (!) che indicano il valore di verità di una fbf a seconda del valore di verità delle sue “sotto-fbf”. Da notare che se una fbf è combinazione di n atomiche, la sua tabella di verità sarà formata da 2ⁿ righe. Le tabelle di verità dei connettivi logici sono:

• valida (tautologia), se è vera per qualsiasi interpretazione. Es. "io sono io";
• inconsistente (contraddizione), se è falsa per ogni interpretazione. Es. "io sono un sasso";
• soddisfacibile, se e solo se esiste almeno un'interpretazione per cui essa è vera, ovvero che la soddisfa. Es. "io sono alto".

1. P ∧ T = P , P ∨ ⊥ = P ; (T è la proposizione sempre vera, mentre ⊥ è sempre falsa)

(:title Dispense Tetty - Capitolo 1:)

Torna alla pagina di Tetty? | Guarda le domande sul capitolo

Torna alla pagina di Tetty? | Guarda le domande sul capitolo

1. Che cos'è la programmazione degli elaboratori

2. Elementi di matematica e logica per la programmazione

La logica proposizionale si occupa della verità o falsità delle proposizioni, dove per proposizione si intende una frase di senso compiuto che può essere vera o falsa. Un esempio di proposizione potrebbe essere che è pomeriggio, o che il sole è freddo, o che questa? è una donna. Per comodità di manipolazione, viene spesso associato ad ogni proposizione un simbolo, così da sfruttare le più compatte ed esaustive notazioni matematiche per descrivere le interazioni dei vari eventi (ad esempio, N: “io sono nudo”).

Il valore di verità di una fbf ci dice se questa è vera o falsa, e dipende dai valori di verità delle proposizioni che la compongono. Questi ultimi cambiano a seconda del contesto in cui li caliamo, dalla loro interpretazione, ovvero dal particolare assegnamento di valori di verità dato ad ogni proposizione atomica (riprendendo l'esempio di prima, N è vero quando prendo il sole integrale ma è falso quando sono in università).

• inconsistente (o contraddizione), se è falsa per ogni interpretazione. Es. A ∧  A;

3. La nozione di "algoritmo"

4. I linguaggi di programmazione

5. Fasi della programmazione

6. Strumenti di modellazione della programmazione

7. Documentazione

Domande sul capitolo

La documentazione interna di un programma è costituita principalmente dai commenti introdotti nel codice nella fase di codifica, con lo scopo di chiarire il suo funzionamento. Perfino la formattazione di un programma (indentazione, distribuzione su più righe, ...) e le asserzioni (vedi Capitolo 3) sono una forma di documentazione interna.

La documentazione esterna di un programma è costituita dai vari documenti di progetto prodotti separatamente dal programma. Sono documenti di specifica, spiegazioni scritte, manuali di riferimento, schemi e diagrammi, ... praticamente tutto il materiale prodotto nella fase di modellazione.

La documentazione non deve limitarsi alla mera fase di codifica del programma, ma anche a quella di collaudo, con la spiegazione dei sistemi di verifica applicati e dei risultati che hanno restituito.

Per quanto riguarda i manuali, consigliati per ogni programma complesso, si distinguono due tipi: il manuale utente (per l'utente comune che dovrà utilizzare il programma) e il manuale di riferimento (per l'utente avanzato o per un eventuale programmatore che potrebbe riutilizzare il programma come componente di un altro più grande).

Esistono fondamentalmente due strumenti più o meno formali per aiutare il programmatore nella delicata fase di modellazione (quella intermedia tra l'algoritmo e il programma): i diagrammi di flusso e lo pseudocodice.

Un diagramma di flusso è la rappresentazione grafica simbolica dell'algoritmo, realizzata come sequenza di blocchi contenenti i vari passi dell'algoritmo stesso.

Un altro strumento di modellazione della programmazione è lo pseudocodice, ovvero un linguaggio fittizio che permette di descrivere un algoritmo senza utilizzare la sintassi di un linguaggio di programmazione specifico. Non può essere eseguito direttamente dal computer, ma aiuta il programmatore nella stesura del codice vero e proprio.

Le carte sintattiche sono dei diagrammi che permettono di visualizzare le regole di una grammatica in forma grafica. In un diagramma i simboli non terminali vengono rappresentati da rettangoli, mentre quelli terminali da elementi rotondi o rettangolari con gli angoli smussati. I simboli sono collegati tra loro con delle frecce orientate.

1. specifica;
2. progettazione;
3. modellazione;
4. codifica;
5. verifica e correzione.

La specifica è la fase in cui viene descritto in modo più o meno formale il problema che il programma deve risolvere, più gli eventuali vincoli e requisiti che dovrà rispettare.

Una specifica informale non è altro che un testo con la descrizione del problema da risolvere e le relazioni che si desidera mantenere tra ingressi e uscite.

Una specifica formale è una quadrupla S = <X, Y, I, U>, dove:

• X sono gli ingressi, ovvero i dati da fornire al programma;
• Y sono le uscite, cioè i risultati che il programma deve produrre;
• I sono le precondizioni, cioè le condizioni che gli ingressi devono rispettare;
• U sono le postcondizioni, ovvero le condizioni che le uscite devono soddisfare perché il programma sia corretto.

Esprimendo i concetti in formule, per ogni dato x ∈ X che soddisfa la formula I(x), il risultato y ∈ Y prodotto dal programma deve soddisfare la formula U(x, y).

La progettazione consiste nell'analisi del problema da risolvere e nella progettazione in modo astratto dell'algoritmo. Esistono due approcci antitetici alla progettazione:

• analisi top-down (dall'alto verso il basso), che scompone i requisiti da soddisfare in un numero minore di sotto-requisiti, a loro volta scomposti in... ecc. fino a che il programma è scomposto in una sequenza di compiti elementari;
• analisi bottom-up (dal basso verso l'alto), che parte dai compiti elementari che si sanno già svolgere e che cerca di combinarli nel modo più opportuno per ottenere la soluzione al problema. Con questo sistema si creano collezioni di piccoli programmi funzionali, comodamente organizzabili in librerie da cui poi prelevarli e riutilizzarli.

Questi due approcci di progettazione possono essere combinati, ad esempio scomponendo un problema dall'alto e individuando quali sottorequisiti comuni e ricorrenti possono essere progettati in stile bottom-up.

La modellazione è la fase in cui viene rappresentato l'algoritmo in maniera più formale e dettagliata, con lo scopo di renderne più evidenti i passaggi e più chiara la struttura concettuale.

La codifica è il momento in cui il programma viene effettivamente scritto nel linguaggio di programmazione prescelto. Tale scelta può dipendere da vari fattori, sia interni (ad esempio, preferenze) che esterni (ad esempio, imposizioni del richiedente).

La verifica è quella fase eterna in cui viene testato il programma, un momento necessario dato che è molto improbabile che esso sia privo di errori al primo colpo. La correzione degli errori è la logica conseguenza della fase di verifica, in cui vengono corrette (!) le parti del codice segnalate dal testing.

Tutte queste attività si basano sul concetto che un programma è corretto solo quando soddisfa tutte le sue specifiche.

Esistono altri tipi di notazione per definire le grammatiche, di più pratica lettura e scrittura. Ne è un esempio quella di Backus e Naur (abbreviato BNF), creata negli anni '60 per definire la sintassi del linguaggio Algol 60.

Alcune differenze rispetto alla notazione vista prima:

• i simboli non terminali sono rappresentati da stringhe alfanumeriche tra parentesi angolari, come <esempio> ;

<cifra> ::== '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' | '0' che associa al non terminale cifra uno dei 10 valori messi tra virgolette e separati dal metasimbolo di alternativa |.

Le carte sintattiche sono dei diagrammi che permettono di visualizzare le regole di una grammatica in forma grafica.
In un diagramma i simboli non terminali vengono rappresentati da rettangoli, mentre quelli terminali da elementi rotondi o rettangolari con gli angoli smussati. I simboli sono collegati tra loro con delle frecce orientate.

Un linguaggio di programmazione può essere o direttamente comprensibile dalla macchina o più vicino al modo di ragionare di chi lo dovrà utilizzare. Nel primo caso si parla di un linguaggio di basso livello (come l'assembly o il MIXAL), nel secondo caso di alto livello (come il C++ o il Java).

Per rendere anche questi ultimi comprensibili dalla macchina, ci sarà bisogno di:

• un interprete, che interpreta ed esegue le istruzioni di un altro programma scritto in un altro linguaggio, rendendo difatto i programmi portabili, oppure
• un compilatore, che traduce automaticamente il programma di alto livello in uno direttamente eseguibile dalla macchina.

• N sono i non terminali, ovvero simboli che non compaiono negli enunciati ma che servono a indicarne gli elementi. Da notare che: N ∩ Σ = ∅;
• ∑ è l'alfabeto del linguaggio, i cui simboli sono chiamati terminali (in quanto usati per costruire gli enunciati);
• R è l' insieme delle regole di produzione. \\

• S è il simbolo di partenza, un simbolo non terminale speciale (e quindi S ∈ N) che indica un enunciato valido.

• R è l' insieme delle regole di produzione. \\

  se A ⊆ B ⊆ C, allora A ⊆ C

∑ = {c,a}, ∑* = {є, c, a, ca, ac, acc, ..., acca, caca, ..., cacca, ...}.

Una definizione più formale di linguaggio potrebbe essere: un linguaggio L è un sottoinsieme delle parole costruibili su un alfabeto ∑, L ⊆ ∑*. Ne consegue che, data una parola w ∈ ∑* ci sono due possibilità:

Un modo esauriente per rappresentare il linguaggio L è definire una procedura in grado di generare tutte le sue parole. Una grammatica è proprio uno di questi sistemi generativi, quindi un insieme di regole di produzione impiegate per descrivere in modo finito linguaggi infiniti.

• N sono i non terminali, ovvero simboli che non compaiono negli enunciati ma che servono a indicarne gli elementi. Da notare che: N ∩ Σ = ∅;
• ∑ è l'alfabeto del linguaggio, i cui simboli sono chiamati terminali (in quanto usati per costruire gli enunciati);
• R è linsieme delle regole di produzione.
  Queste hanno forma α → β, dove α ∈ N* \ {є} e β ∈ (N ∪ Σ)*
  (tradotto in parole: "se ho alfa allora' produco beta, dove alfa appartiene all'insieme dei non terminali (meno la parola vuota) mentre beta appartiene all'unione tra i non terminali e l'alfabeto (parola vuota compresa)");
• S è il simbolo di partenza, un simbolo non terminale speciale (e quindi S ∈ N) che indica un enunciato valido.

La relazione di produzione in una grammatica G è espressa come:\\

Una definizione più formale di linguaggio potrebbe essere: un linguaggio L è un sottoinsieme delle parole costruibili su un alfabeto ∑, L ≤ ∑*. Ne consegue che, data una parola w ∈ ∑* ci sono due possibilità:

• poter essere risolto in un numero finito di operazioni, perché va da sé che se fosse infinito non si arriverebbe mai a risolvere il problema. Se quindi trovare i primi dieci numeri primi è un algoritmo (basta applicare determinate operazioni per un numero finito di volte), trovare tutti i numeri primi non lo è più (le operazioni da eseguire sono le stesse, ma non si finirà mai di ripeterle);

Un linguaggio di programmazione è un linguaggio non ambiguo ed estremamente preciso, grazie al quale è possibile comunicare ad una macchina le operazioni che deve eseguire in modo del tutto meccanico e automatico.

Non esiste un unico linguaggio di programmazione, ed un buon programmatore non deve impararne uno a menadito ed usare sempre e solo quello, ma dovrà scegliere l'uno o l'altro a seconda delle necessità e di ciò che deve fare.

Un linguaggio è un repertorio di segni convenzionali e di regole per combinarli in enunciati più complessi, più altre regole che associano un significato ad ogni enunciato.

Esistono tre livelli di linguaggio:

• sintattico, l’insieme delle regole che specificano in quali modi i segni possono essere combinati per formare enunciati. Ad esempio, nel linguaggio italiano ad una "q" non può seguire una "f";

L’insieme dei segni convenzionali (anche detti simboli o token) con i quali si possono costruire gli enunciati di un linguaggio, viene chiamato indifferentemente alfabeto o vocabolario. Una parola (in alcuni casi detta stringa o frase) è invece una sequenza di lunghezza finita di simboli dell’alfabeto. Un linguaggio è completamente definito dall'insieme delle parole che gli appartengono.

Una parola vuota è una sequenza di zero simboli, uguale per qualsiasi alfabeto e indicata con є. Se ∑ è un alfabeto, ∑* indica l’insieme di tutte le parole composte da elementi di ∑, є compresa. Per esempio se
∑ = {c,a}, ∑* = {є, c, a, ca, ac, acc, ..., acca, ..., cacca, ...}.

Il complemento di un insieme A è l'insieme di tutti gli elementi che non appartengono ad A.

Una funzione f si dice iniettiva se e solo se x₁ ≠ x₂ implica f (x₁) ≠ f (x₂).

La logica dei predicati mette inoltre a disposizione due utili elementi, i quantificatori, grazie ai quali è possibile specificare se le variabili di una data proposizione si riferiscono a tutte le loro istanze o solo ad un numero più ristretto. Ne esistono di due tipi, quello esistenziale ∃ (“esiste”) e quello universale ∀ (“per ogni”). Molto importante ricordare come i quantificatori possano essere applicati alle sole variabili libere di una formula.

L'algoritmo è una procedura passo per passo grazie alla quale un'operazione può essere svolta senza alcun esercizio di intelligenza? e quindi, per esempio, da una macchina. Se il suo scopo è quello di risolvere problemi, capite bene con quanti algoritmi abbiamo a che fare tutti i giorni. Un esempio legittimo di algoritmo potrebbe essere perfino una ricetta di cucina?.

• poter essere risolto in un numero finito di operazioni, perché va da sé che se fosse infinito non si arriverebbe mai a risolvere il problema. Se quindi ad esempio trovare i primi dieci numeri primi è un algoritmo (basta applicare determinate operazioni per un numero finito di volte), trovare tutti i numeri primi non lo è più (le operazioni da eseguire sono le stesse, ma non si finirà mai di ripeterle);
• essere il meno ambiguo possibile. Ad esempio, in una ricetta di cucina la frase "un pizzico di sale" non potrebbe essere ben interpretata da tutti (un milligrammo? Dieci milligrammi? Sedici tonnellate?).

L'analisi di un algoritmo è lo studio della sua complessità computazionale. Questa dipende dalla quantità di risorse necessarie alla sua esecuzione, strettamente dipendenti dalla difficoltà del problema da risolvere. Le due risorse principali, strettamente collegate, sono:

Dal momento che sarebbe troppo complicato studiare la complessità di un algoritmo su una macchina reale, il suo studio avviene su un modello generico della tecnologia che verrà utilizzata per realizzarlo. Il nostro modello sarà una macchina con accesso casuale alla memoria e con un processore singolo, la random-access machine (RAM). Peculiarità della RAM è che le istruzioni vengono eseguite in sequenza, con lo stesso tempo di esecuzione e senza operazioni concorrenti. Questo significa che il tempo di esecuzione di un algoritmo su un dato ingresso è dato dal numero di passi necessari per eseguirlo moltiplicato per una costante di tempo t_i. Per quanto riguarda lo spazio occupato, si considera invece la quantità massima di informazione da mantenere durante l'esecuzione.

Se spazio e tempo dipendono dal particolare ingresso dell'algoritmo, per il loro studio non possiamo interessarci di pochi casi particolari, ma di una statistica su tutte le possibili esecuzioni. Di tutte le statistiche possibili (caso migliore, caso medio, caso peggiore), l'analisi degli algoritmi si concentra sul caso peggiore (maggior impiego di tempo e di spazio possibile) per tre buoni motivi:

• stabilisce un limite superiore alle risorse che l'esecuzione dell'algoritmo potrebbe richiedere (quindi le risorse messe a disposizione saranno sufficienti per ogni caso possibile);

• è molto frequente che il caso medio sia molto simile a quello peggiore.

Ciò che però realmente determina la complessità di un algoritmo non è la quantità precisa di risorse, ma il suo tasso di crescita (logaritmico, lineare, cubico, esponenziale, ...) al crescere delle dimensioni dell'ingresso, detto ordine. Ovviamente, più l'ordine è basso e più l'algoritmo è semplice ed efficiente.

• indecidibili, quando non possono essere risolti in un tempo finito da nessun algoritmo e quindi da nessun programma. Ne è un classico esempio il problema "dell'arresto", che consiste nello stabilire se, dato un programma, questo termina su un particolare ingresso.

In base alla loro complessità computazionale, gli algoritmi possono essere suddivisi in classi di complessità, assegnate in base alla scelta del modello di calcolo (come la RAM o, ancora più astratto, la macchina di Turing e la macchina di Turing con oracolo) ed al concetto di riduzione del problema.

...e tanto per sapere: La macchina di Turing è un dispositivo governato da una logica interna costituita da un automa a stati finiti ed equipaggiato con una testina che legge e scrive simboli di un certo alfabeto su un nastro infinito, sul quale si può spostare di una casella alla volta. La macchina di Turing con oracolo o “non deterministica” è una macchina di Turing ideale nella quale ogni volta che l’algoritmo prevede il compimento di una scelta, lui fa sempre quella giusta.

Ultimo concetto da prendere in considerazione nell'analisi di un algoritmo è quello di riduzione o riducibilità, che permette di verificare se un certo algoritmo associato alla risoluzione di uno specifico problema può essere adoperato per risolverne anche altri.

Un insieme è una qualsiasi collezione di elementi.
Un elemento x che appartiene ad un insieme A si indica con la notazione x ∈ A.
Due insiemi si dicono uguali se e solo se contengono gli stessi elementi.
Un insieme A è sottoinsieme di B se e solo se ogni elemento di A è anche elemento di B.
L'intersezione di due insiemi A ∩ B è l'insieme di tutti gli elementi comuni ad A e B.
L'unione di due insiemi A U B è l'insieme di tutti gli elementi che appartengono ad A o a B, o ad entrambi.
Un insieme che non contiene nessun elemento si chiama insieme vuoto e si indica con Ø.
Il complemento di un insieme A è l'insieme di tutti gli elementi che non appartengono ad A.

  A U Ø = A --- A ∩ U = A --- A ∩ Ø = Ø --- A U U = U

  se A ≤ B ≤ C, allora A ≤ C

  A U  = A --- A ∩ U = A --- A ∩ Ø = Ø --- A U U = U

Le proposizioni possono essere atomiche (semplici) oppure composte. Le seconde sono ottenute combinando una o più atomiche con i connettivi logici non (¬), e (∧), o (∨), implica (⊃), se e solo se (≡). Le proposizioni atomiche e quelle composte prendono anche il nome di formule ben formate o fbf.

Le proposizioni possono essere atomiche (semplici) oppure composte. Le seconde sono ottenute combinando una o più atomiche con i connettivi logici non (¬), e (∧), o (∧), implica (), se e solo se (≡). Le proposizioni atomiche e quelle composte prendono anche il nome di formule ben formate o fbf.

1. P ∧ T = P , P ∨ ⊥ = P ;

La logica dei predicati è un passo avanti nel livello di astrazione della descrizione degli eventi. Tradotto in italiano, significa che offre strumenti di descrizione molto più potenti e versatili di quelli della logica delle proposizioni. Facendo un esempio, se abbiamo dieci lampadine e dobbiamo dire se funzionano o se sono fulminate, nella logica delle proposizioni dovremo definire una proposizione per ogni lampadina. Ok quando sono dieci lampadine, ma quando sono diecimila? In questo caso giunge in soccorso la logica dei predicati, in grado di parametrizzare e riassumere i vari eventi.

• simboli individuali (i nomi degli oggetti coinvolti nel ragionamento, chiamati anche istanze);
• variabili (ad esempio x, y e z), che possono assumere dei valori attinti dall'insieme dei simboli individuali;
• simboli di funzione, utilizzati per costruire nuove istanze;
• simboli di predicato, utilizzati per costruire proposizioni su particolari istanze.

I termini sono gli argomenti di un predicato nella logica dei predicati, e rappresentano quelle entità sulle quali è possibile costruire affermazioni. Possono essere:

• simboli individuali;
• variabili;
• se f è una funzione n-aria e t₁, ... , t_n sono termini, anche f(t₁, ... , t_n) è un termine.

Attraverso l'utilizzo dei termini diventa possibile scrivere della formule in cui ciascuna variabile può essere sostituita da una qualsiasi delle istanze.

La logica dei predicati mette inoltre a disposizione due utili elementi, ovvero i quantificatori, grazie ai quali è possibile specificare se le variabili di una data proposizione si riferiscono a tutte le loro istanze o solo ad un numero più ristretto. Ne esistono di due tipi, quello esistenziale ∃ (“esiste”) e quello universale ∀ (“per ogni”). Molto importante ricordare come i quantificatori possano essere applicati alle sole variabili libere di una formula.

Un insieme è una qualsiasi collezione di elementi.

Dati n insiemi U₁, U₂, ... U_n, il loro prodotto cartesiano U₁ X U₂ X ... X U_n è l'insieme di tutte le n-uple ordinate (u₁ X u₂ X ... X u_n) dove ui ∈ Ui per i = 1, 2, ... , n.

Dati due insiemi A e B, una funzione f di dominio A e codominio B, in simboli f: A → B, è una mappa che associa ad ogni elemento a ∈ A un elemento b = f(a) ∈ A.

Una funzione f si dice iniettiva se e solo se x1  x2 implica f (x1)  f (x2). Una funzione si dice suriettiva se la sua immagine coincide con il suo codominio. Una corrispondenza biunivoca (o funzione biiettiva) è una funzione sia iniettiva che suriettiva.

La cardinalità di un insieme A è il numero di elementi che appartengono all'insieme A, e si denota ║A║. Dati due insiemi A e B:

• l'insieme delle funzioni f: A → B ha una cardinalità esponenziale data da ║B║^║A║;
• l'insieme di tutti i sottoinsiemi di A ha cardinalità 2^║A║.

Gli elaboratori elettronici sono delle macchine per elaborare informazioni, dove per macchine si intendono dispositivi - anche molto complessi - il cui scopo è sostituire o facilitare il lavoro umano nello svolgimento di compiti ripetitivi, difficili o faticosi.

Il concetto che sta alla base della programmazione è che una macchina in grado di compiere più compiti è meglio di una che ne sa svolgere uno solo, dal momento che con un unico dispositivo (e quindi un'unica spesa, trasporto, manuale, ...) otterremo qualcosa che normalmente richiederebbe l'impiego di più strumenti diversi. Gli elaboratori elettronici sono quindi programmabili per motivi economici e per versatilità.

La logica proposizionale si occupa della verità o falsità delle proposizioni, dove per proposizione si intende una frase di senso compiuto che può essere vera o falsa. Un esempio di proposizione potrebbe essere che è pomeriggio, o che il sole è freddo, o che questa? è una donna. Per comodità di manipolazione, viene spesso associato ad ogni proposizione una simbolo, così da sfruttare le più compatte ed esaustive notazioni matematiche per descrivere le interazioni dei vari eventi (ad esempio, N: “io sono nudo”).

Le proposizioni possono essere atomiche (semplici) oppure composte. Le seconde sono ottenute combinando una o più atomiche con i connettivi logici non (), e (), o (), implica (), se e solo se (≡). Le proposizioni atomiche e quelle composte prendono anche il nome di formule ben formate o fbf.

Il valore di verità di una fbf ci dice se questa è vera o falsa, e dipende dai valori di verità delle proposizioni che la compongono. Questi ultimi cambiano a seconda del contesto in cui li caliamo, dalla loro interpretazione, ovvero dal particolare assegnamento di valori di verità dato ad ogni proposizione atomica (riprendendo l'esempio di prima, N è vero quando prendo il sole integrale ma è falso quando sono in università).

Le tabelle di verità sono tabelle (!) che indicano il valore di verità di una fbf a seconda del valore di verità delle sue “sotto-fbf”. Da notare che se una fbf è combinazione di n atomiche, la sua tabella di verità sarà formata da 2n righe. Le tabelle di verità dei connettivi logici sono:

• valida (o tautologia), se è vera per qualsiasi interpretazione. Es. A   A;
• inconsistente (o contraddizione), se è falsa per ogn interpretazione. Es. A ∧  A;
• soddisfacibile, se e solo se esiste almeno un'interpretazione per cui essa è vera, ovvero che la soddisfa.

1 Che cos'è la programmazione degli elaboratori

2 Elementi di matematica e logica per la programmazione

2.1 Logica Proposizionale

2.2 Insiemistica

2.3 Logica dei predicati

3 La nozione di "algoritmo"

4 I linguaggi di programmazione

4.1 Definizione formale di linguaggio

4.2 Grammatica

4.3 Grammatiche nel formato di Backus e Naur

4.4 Carte sintattiche

4.5 Linguaggi di alto e basso livello

5 Fasi della programmazione

5.1 Specifica

5.2 Progettazione

5.3 Modellazione

5.4 Codifica

5.5 Verifica e correzione

6 Strumenti di modellazione della programmazione

6.1 Diagrammi di flusso

6.2 Pseudocodice

7 Documentazione

7.1 Documentazione interna

7.2 Documentazione esterna

1 Che cos'è la programmazione degli elaboratori\\

1 Che cos'è la programmazione degli elaboratori

1.2.3 Logica dei predicati

1.6.2 Pseudocodice

ed il linguaggio generato da questa grammatica, indicato con L(G) è definito come:\\

Torna su

1.5 Fasi della programmazione

Esistono cinque fasi distinte nella scrittura di un programma:

• specifica;
• progettazione;
• modellazione;
• codifica;
• verifica e correzione.

1.5.1 Specifica

La specifica è la fase in cui viene descritto in modo più o meno formale il problema che il programma deve risolvere, più gli eventuali vincoli che dovrà rispettare.

Una specifica informale non è altro che un testo con la descrizione del problema da risolvere e le relazioni che si desidera mantenere tra ingressi e uscite.

Una specifica formale è una quadrupla S = <X, Y, I, U>, dove:

• X sono gli ingressi, ovvero i dati da fornire al programma;
• Y sono le uscite, cioè i risultati che il programma deve produrre;
• I sono le precondizioni, cioè le condizioni che gli ingressi devono rispettare;
• U sono le postcondizioni, ovvero le proprietà che i risultati del programma devono soddisfare perché si possa dire che è corretto.

Per ogni dato x ∈ X che soddisfa la formula I(x) il risultato y ∈ Y prodotto dal programma deve soddisfare la formula U(x, y).

1.5.2 Progettazione

La progettazione consiste nell'analisi del problema da risolvere e nel concepimento in modo astratto dell'algoritmo. Esistono due approcci antitetici alla progettazione:

• analisi top down (dall'alto verso il basso), che scompone i requisiti da soddisfare per risolvere il problema in un numero minore di sotto-requisiti, a loro volta scomposti fino ad essere costituiti da soli compiti elementari;
• analisi bottom up (dal basso verso l'alto), che parte dai compiti elementari che si sanno già svolgere e cerca di combinarli nel modo più opportuno per ottenere la soluzione al problema. In questo modo si creano tanti piccoli programmi funzionali, organizzabili in librerie da cui poterli prelevare e riutilizzare.

I due approcci di progettazione possono essere anche combinati, ad esempio scomponendo un problema dall'alto e individuando quali sottorequisiti comuni e ricorrenti possono essere progettati in stile bottom-up.

Un sistema di progettazione tra i più recenti è quello ad oggetti, che consiste nell'individuare tutti gli elementi rilevanti che compaiono nella definizione del problema (gli oggetti) e quindi modellizzarli e strutturarli tra loro.

1.5.3 Modellazione

La modellazione è la fase in cui viene rappresentato l'algoritmo in maniera più formale e dettagliata, con lo scopo di renderne evidenti i passaggi e la struttura concettuale.

È una fase molto importante e troppo spesso sottovalutata, che aiuta il programmatore a creare un programma corretto e corredato di una buona documentazione.

1.5.4 Codifica

La codifica è il momento in cui il programma viene effettivamente scritto nel linguaggio di programmazione prescelto. Tale scelta può dipendere da vari fattori, sia interni che esterni.

1.5.5 Verifica e correzione

La verifica è quella fase più o meno lunga in cui viene testato il programma, essendo molto improbabile che esso venga prodotto privo di un errori al primo colpo. La correzione degli errori è la logica conseguenza della fase di verifica, in cui vengono corrette le parti del codice segnalate dal testing. Si può dire che un programma è corretto solo quando soddisfa le sue specifiche.

Torna su

1.6 Strumenti di modellazione della programmazione

Esistono diversi strumenti più o meno formali per aiutare il programmatore nella delicata fase di modellazione, ovvero quella intermedia tra l'algoritmo e il programma. Questi strumenti sono i diagrammi di flusso e lo pseudocodice.

1.6.1 Diagrammi di flusso

Un diagramma di flusso è la rappresentazione grafica simbolica dell'algoritmo, realizzata come sequenza di blocchi contenenti i passi dell'algoritmo stesso. Ogni diagramma di flusso ha uno stato di partenza e zero o più stati finali (rappresentati come cerchietti), più altri blocchi intermedi rappresentati come rettangoli per le istruzioni e come rombi per i test. Blocchi e stati sono collegati con delle frecce, che puntano al blocco successivo da eseguire.

1.6.2 Pseudocodice

Un altro strumento di modellazione della programmazione è lo pseudocodice, ovvero un linguaggio di programmazione finto, con una sintassi ben precisa, un certo repertorio di comandi predefiniti, ecc. ma con una maggiore flessibilità, un repertorio di comandi predefiniti espandibile a piacere e idealmente coincidente con quelli che il programmatore considera dei “compiti elementari” e con la possibilità di utilizzare delle espressioni in linguaggio naturale laddove sia necessario specificare con maggiore chiarezza che cosa debba fare una particolare linea di codice.

Torna su

1.7 Documentazione

La documentazione di un programma è tutto quel materiale informativo prodotto per facilitare la comprensione - e quindi l'utilizzo - del programma stesso. Può essere di due tipi: interna ed esterna.

1.7.1 Documentazione interna

La documentazione interna di un programma è costituita principalmente dai commenti introdotti nel corpo del programma nella fase di codifica, con lo scopo di chiarire il suo funzionamento. Perfino la formattazione di un programma (indentazione, distribuzione su più righe, ...) e le asserzioni sono una forma di documentazione interna.

1.7.2 Documentazione esterna

La documentazione esterna di un programma è costituita dai vari documenti di progetto prodotti separatamente dal programma. Essi sono documenti di specifica, spiegazioni scritte, manuali di riferimento, schemi e diagrammi (praticamente tutto il materiale prodotto nella fase di modellazione).

La documentazione non deve limitarsi alla mera codifica del programma, ma anche alla fase di collaudo, con la spiegazione dei sistemi di verifica applicati e dei risultati che hanno restituito. Terminata anche la fase di collaudo (e relativa documentazione), ogni programma complesso dovrebbe essere fornito di un proprio manuale. Ne esistono di due tipi: il manuale utente (per l'utente comune che dovrà utilizzare il programma) e il manuale di riferimento (per l'utente avanzato o per un eventuale programmatore che potrebbe utilizzare il programma come componente di un altro più grande). Fasi della programmazione

Torna su

3 La nozione di “algoritmo”\\

1.3 La nozione di "algoritmo"

• semplici, quando sono risolvibili da algoritmi di ordine logaritmico o lineare;
• trattabili, quando hanno complessità polinomiale in tempo di calcolo;
• difficili o intrattabili, quando richiedono una quantità esponenziale di tempo;
• indecidibili, quando non possono essere risolti in un tempo finito da nessun algoritmo e quindi da nessun programma. Ad esempio il problema "dell'arresto", che consiste nello stabilire se, dato un programma, questo termina su un dato ingresso, è un classico esempio di algoritmo indecidibile.

1.4 I linguaggi di programmazione

Un linguaggio di programmazione è un linguaggio non ambiguo e molto preciso, grazie al quale è possibile comunicare ad una macchina quali operazioni deve eseguire in modo del tutto meccanico e automatico.

Un programmatore non dovrà scegliere un linguaggio di programmazione ed usare sempre quello, ma dovrà man mano scegliere l'uno o l'altro a seconda delle necessità.

1.4.1 Definizione formale di linguaggio

Un linguaggio è un repertorio di segni convenzionali e di regole per combinarli in enunciati più complessi, più altre regole che associano un significato ad ogni enunciato. Esistono tre livelli di linguaggio:

• sintattico, l’insieme delle regole che specificano in quali modi i segni possono essere combinati per formare enunciati;
• semantico, l’insieme delle regole che permettono di associare un significato a segni ed enunciati;
• pragmatico (non interessa ai nostri fini), che riguarda le conseguenze pratiche di un enunciato.

L’insieme dei segni convenzionali (simboli o token) grazie ai quali è possibile costruire gli enunciati di un linguaggio è chiamato indifferentemente alfabeto o vocabolario. Una parola (in alcuni casi detta stringa o frase) è una sequenza di lunghezza finita di simboli dell’alfabeto. Un linguaggio è completamente definito dall'insieme delle parole che gli appartengono.

Una parola vuota è una sequenza di zero simboli, uguale per qualsiasi alfabeto e indicata con є. Se ∑ è un alfabeto, ∑* indica l’insieme di tutte le parole composte da elementi di ∑, є compresa. Per esempio se ∑ = {0,1}, ∑* = {є, 0, 1, 00, 01, 10, 11, …}.

Una definizione più formale di linguaggio potrebbe essere: un linguaggio L è un sottoinsieme delle parole costruibili su un alfabeto ∑, L ∑*. Ne consegue che, data una parola w ∈ ∑* ci sono due possibilità:

• w appartiene al linguaggio e quindi rappresenta un enunciato di L;
• w non appartiene al linguaggio e dunque non ne rappresenta un enunciato valido.

1.4.2 Grammatica

Per rappresentare L è necessario definire una procedura in grado di generare tutte le sue parole. Una grammatica è uno di questi sistemi generativi, un insieme di regole di produzione impiegate per descrivere in modo finito linguaggi infiniti.

Più formalmente, una grammatica G è una quadrupla (N, ∑, R, S), dove:

• N sono i non terminali, ovvero simboli che non compaiono negli enunciati ma che servono a indicarne gli elementi. Da notare che: N ∩ Σ = ∅;
• ∑ è l'alfabeto del linguaggio, i cui simboli sono chiamati terminali (in quanto usati per costruire gli enunciati);
• R è l'insieme delle regole di produzione.
  Queste hanno forma α → β, dove α ∈ N* \ {є} e β ∈ (N ∪ Σ)*;
• S è il simbolo di partenza, un simbolo non terminale speciale (e quindi S ∈ N) che denota un enunciato valido.

La relazione di produzione in una grammatica G è espressa come: ⇒G ⊆ (N ∪ Σ)^∗ × (N ∪ Σ)^∗

ed il linguaggio generato da questa grammatica, indicato con L(G) è definito come: L(G) = {w : w ∈ Σ^∗ ∧ S ⇒^∗w}

ovvero tutte le stringhe w ∈ Σ^∗ che derivano dal simbolo di partenza S utilizzando le regole della grammatica.

1.4.3 Grammatiche nel formato di Backus e Naur

Esistono altri tipi di notazione per definire le grammatiche, di più pratica e comoda lettura e scrittura. Ne è un esempio quella di Backus e Naur (abbreviato BNF), creata negli anni '60 per definire la sintassi del linguaggio Algol 60.

Alcune differenze rispetto alla notazione precedente:

• la freccia a destra → delle regole viene sostituita da ::= ;
• i simboli non terminali sono rappresentati da stringhe alfanumeriche racchiuse tra parentesi angolari, come <espressione> ;
• i simboli terminali sono racchiusi tra virgolette, singole o doppie.

Un esempio di notazione in BNF potrebbe essere: <cifra_iniziale> ::== '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' | '0' che associa al non terminale cifra_iniziale uno dei i valori messi tra virgolette e separati dal metasimbolo di alternativa |.

1.4.4 Carte sintattiche

Le carte sintattiche sono dei diagrammi che esprimono le regole di una grammatica in forma grafica. Nel diagramma i simboli non terminali vengono rappresentati da rettangoli, mentre quelli terminali da elementi rotondi o rettangolari con gli angoli smussati. I simboli sono collegati tramite frecce orientate.

1.4.5 Linguaggi di alto e basso livello

Un linguaggio di programmazione può essere o direttamente comprensibile da una macchina o più vicino al modo di ragionare di chi lo dovrà utilizzare. Nel primo caso si tratta di un linguaggio di basso livello (come l'assembly o il MIXAL), nel secondo caso invece di alto livello. Per rendere anche quest'ultimo comprensibile alla macchina, ci sarà bisogno di:

• un interprete, che interpreta ed esegue le istruzioni di un altro programma scritto in un altro linguaggio, rendendo difatto i programmi portabili, oppure
• un compilatore, che traduce automaticamente il programma di alto livello in uno direttamente eseguibile dalla macchina.

2 Elementi di matematica e logica per la programmazione

3 La nozione di “algoritmo” 4 I linguaggi di programmazione

5 Fasi della programmazione

6 Strumenti di modellazione della programmazione

7 Documentazione

La nozione di "algoritmo"

L'algoritmo è una procedura passo per passo grazie alla quale un'operazione può essere svolta senza alcun esercizio di intelligenza e quindi, per esempio, da una macchina. Il suo scopo è dunque quello di risolvere problemi. Un esempio legittimo di algoritmo potrebbe essere una ricetta di cucina.

Requisiti essenziali per un algoritmo sono:

• poter essere risolto in un numero finito di operazioni, perché se fosse infinito non si risolverebbe il problema. Ad esempio non è un algoritmo la procedura per trovare i numeri primi, che pur avendo passi ben precisi non ha una fine;
• essere il meno ambiguo possibile. Ad esempio, in una ricetta di cucina la frase “un pizzico di sale” non potrebbe essere ben interpretata da tutti (un milligrammo? Dieci milligrammi? Sedici tonnellate?).

Non esiste un unico linguaggio per esprimere un algoritmo, dipende da cosa bisogna fare, come bisogna farlo e da chi farlo eseguire.

L'analisi di un algoritmo è lo studio della sua complessità computazionale. La complessità computazionale di un algoritmo dipende dalla quantità di risorse necessarie alla sua esecuzione, strettamente dipendenti dalla difficoltà del problema da risolvere. Le due risorse principali, strettamente collegate, sono:

• il tempo impiegato per eseguire l'algoritmo;
• lo spazio, ovvero la quantità di memoria necessaria per contenere i dati iniziali, intermedi e finali del problema che si sta risolvendo.

Da notare che la difficoltà di un problema è misurata dalla complessità computazionale del più efficiente algoritmo che lo risolve.

Dal momento che sarebbe troppo complicato studiare la complessità di un algoritmo su una macchina reale, il suo studio avviene su un modello generico della tecnologia che verrà utilizzata per realizzarlo. Il nostro modello sarà una macchina con accesso casuale alla memoria e con un processore singolo, la random-access machine (RAM). Peculiarità della RAM è che le istruzioni vengono eseguite in sequenza, con lo stesso tempo di esecuzione e senza operazioni concorrenti. Questo vuol dire che il tempo di esecuzione di un algoritmo su un dato ingresso è dato dal numero di passi necessari per eseguirlo moltiplicato per una costante di tempo t_i. Per quanto riguarda lo spazio occupato, si considera invece la quantità massima di informazione da mantenere passo per passo durante l'esecuzione.

Dal momento che spazio e tempo dipendono dal particolare ingresso dell'algoritmo, non ci interessano molto i casi particolari, ma una statistica su tutte le possibili esecuzioni. Di tutte le statistiche possibili (caso migliore, caso medio, caso peggiore), l'analisi degli algoritmi si concentra sul caso peggiore (maggior impiego di tempo e di spazio possibile) perché:

• stabilisce un limite superiore alle risorse che l'esecuzione dell'algoritmo potrebbe richiedere;
• per alcuni algoritmi il caso peggiore è quello che accade più spesso;
• accade molto spesso che il caso medio è molto simile a quello peggiore.

Ciò che però realmente determina la complessità di un algoritmo non è la quantità precisa di risorse, ma il suo tasso di crescita (logaritmico, lineare, cubico, esponenziale, ...) al crescere delle dimensioni dell'ingresso, detto ordine. Ovviamente, più l'ordine è basso e più l'algoritmo è semplice ed efficiente.

Facciamo due esempi:

1. abbiamo due algoritmi A e B. Il primo nel caso peggiore gira in un tempo pari a nlogn, mentre il secondo in un tempo pari a 100logn. Anche se per n piccolo è A il più veloce, l'ordine di crescita di A è esponenziale, mentre quello di B logaritmico. Quindi B è un algoritmo più efficiente di A;
2. abbiamo due algoritmi A e B. Il primo nel caso peggiore gira in un tempo pari a nlogn, mentre il secondo in un tempo pari a 6nlogn. Il coefficiente 6 non deve trarre in inganno, perché l'ordine di crescita al crescere delle dimensioni dell'ingresso è esponenziale per entrambi. Quindi A e B hanno stessa complessità computazionale.

In base al loro ordine, i problemi si possono suddividere in:

• semplici, quando sono risolvibili da algoritmi di ordine logaritmico o lineare;
• trattabili, quando hanno complessità polinomiale in tempo di calcolo;
• difficili o intrattabili, quando richiedono una quantità esponenziale di tempo;
• indecidibili, quando non possono essere risolti in un tempo finito da nessun algoritmo e quindi da nessun programma. Ad esempio il problema "dell'arresto", che consiste nello stabilire se, dato un programma, questo termina su un dato ingresso, è un classico esempio di algoritmo indecidibile.

In base alla loro complessità computazionale, gli algoritmi possono essere suddivisi in classi di complessità, assegnate in base alla scelta del modello di calcolo (come la RAM o, ancora più astratto, la macchina di Turing e la macchina di Turing con oracolo) ed al concetto di riduzione del problema.

La macchina di Turing è un dispositivo governato da una logica interna costituita da un automa a stati finiti ed equipaggiato con una testina che legge e scrive simboli di un certo alfabeto su un nastro infinito, sul quale si può spostare di una casella alla volta. La macchina di Turing con oracolo o “non deterministica” è una macchina di Turing ideale nella quale ogni volta che l’algoritmo prevede il compimento di una scelta, lui fa sempre quella giusta.

La riduzione o riducibilità permette di verificare se un certo algoritmo associato alla risoluzione di uno specifico problema può essere adoperato per risolverne anche altri.

Torna su

• l'insieme delle funzioni f: A → B ha una cardinalità esponenziale data da ║B║^║A║;
• l'insieme di tutti i sottoinsiemi di A ha cardinalità 2^║A║.

1.2.3 Logica dei predicati

La logica dei predicati è costituita da:

• simboli individuali (i nomi degli oggetti coinvolti nel ragionamento, chiamati istanze);
• variabili (tipo x, y e z), che assumono valori dall'insieme dei simboli individuali;
• simboli di funzione, utilizzati per costruire nuove istanze;
• simboli di predicato, utilizzati per costruire proposizioni su particolari istanze.

I termini sono gli argomenti di un predicato nella logica dei predicati, ovvero delle entità sulle quali è possibile costruire affermazioni. Possono essere:

• simboli individuali;
• variabili;
• se f è una funzione n-aria e t1, ... , tn sono termini, anche f(t1, ... , tn) è un termine.

Attraverso l'utilizzo dei termini sarà possibile scrivere formule in cui ciascuna variabile può essere sostituita da una qualsiasi delle istanze. Usando dei quantificatori è possibile specificare se le variabili di una data proposizione si riferiscono a tutte le loro istanze o solo ad un numero più ristretto. Esistono due tipi di quantificatori, quello esistenziale ∃ (“esiste”) e quello universale ∀ (“per ogni”), applicabili alle sole variabili libere di una formula.

Torna su

• il prodotto cartesiano A × B ha una cardinalità data dal prodotto delle cardinalità degli insiemi A e B, cioè ║A × B║ = ║A║ · ║B║;
• l'insieme delle funzioni f: A → B ha una cardinalità esponenziale data da ║B║║A║;
• l'insieme di tutti i sottoinsiemi di A ha cardinalità 2║A║.

1. Leggi di De Morgan:
   http://doppioclic.altervista.org/wiki/local/tetty/deMorgan.jpg

Torna alla pagina di Tetty?

Attraverso l'utilizzo dei termini sarà possibile scrivere formule in cui ciascuna variabile può essere sostituita da una qualsiasi delle istanze. Usando dei quantificatori è possibile specificare se le variabili di una data proposizione si riferiscono a tutte le loro istanze o solo ad un numero più ristretto. Esistono due tipi di quantificatori, quello esistenziale ∃ (“esiste”) e quello universale ∀ (“per ogni”), applicabili alle sole variabili libere di una formula.

Torna alla pagina di Tetty?

3 La nozione di “algoritmo”\\

• valida (o tautologia), se è vera per qualsiasi interpretazione. Es. A   A;
• inconsistente (o contraddizione), se è falsa per ogn interpretazione. Es. A ∧  A;
• soddisfacibile, se e solo se esiste almeno un'interpretazione per cui essa è vera, ovvero che la soddisfa.

1. ¬(P ∧ Q) = ¬P ∨ ¬Q,
2. ¬(P ∨ Q) = ¬P ∧ ¬Q. (leggi di De Morgan)

In generale una fbf Q segue logicamente da una fbf P se e solo se ogni interpretazione che soddisfa P soddisfa anche Q. In questo caso la formula P ⊃ Q si dice teorema, dove P è l'ipotesi e Q la sua tesi. La dimostrazione di un teorema è una successione di passaggi, verificabili in modo meccanico e oggettivo, che trasformano l'ipotesi nella tesi. Scrivere programmi spesso richiede la dimostrazione di teoremi.

1.2.2 Insiemistica

1. Proprietà commutativa:
   A U B = B U A --- A ∩ B = B ∩ A
2. Proprietà associativa:
   A U ( B U C) = (A U B) U C
   A ∩ ( B ∩ C) = (A ∩ B) ∩ C
3. Proprietà distributiva:
   A U ( B ∩ C) = (A U B) ∩ (A U C)
   A ∩ ( B U C) = (A ∩ B) U (A ∩ C)
4. Idempotenza:
   A U A = A --- A ∩ A = A
5. Identità:
   A U  = A --- A ∩ U = A --- A ∩  =  --- A U U = U
6. Proprietà transitiva dell'inclusione:
   se A  B  C, allora A  C
7. Involuzione:
   Ā = A
8. Leggi di De Morgan:
   A ∩ B = A U B --- A U B = A ∩ B

http://doppioclic.altervista.org/wiki/local/tetty/tabelle_verita.jpg

Una fbf può essere:

• valida (o tautologia), se è vera per qualsiasi interpretazione. Es. A   A;
• inconsistente (o contraddizione), se è falsa per ogn interpretazione. Es. A ∧  A;
• soddisfacibile, se e solo se esiste almeno un'interpretazione per cui essa è vera, ovvero che la soddisfa.

Esistono in logica proposizionale alcune relazioni tra proposizioni così importanti da essere considerate leggi:

1. P ≡ Q = (P ⊃ Q) ∧ (Q ⊃ P );
2. P ⊃ Q = ¬P ∨ Q;
3. 1. P ∧ Q = Q ∧ P ,
   2. P ∨ Q = Q ∨ P ; (leggi commutative)
4. 1. P ∧ (Q ∧ R) = (P ∧ Q) ∧ R,
   2. P ∨ (Q ∨ R) = (P ∨ Q) ∨ R; (leggi associative)
5. 1. P ∧ (Q ∨ R) = (P ∧ Q) ∨ (P ∧ R),
   2. P ∨ (Q ∧ R) = (P ∨ Q) ∧ (P ∨ R); (leggi distributive)
6. P ∧ > = P , P ∨ ⊥ = P ;
7. P ∧ ⊥ = ⊥, P ∨ T = T;
8. P ∧ ¬P = ⊥, P ∨ ¬P = T;
9. ¬(¬P ) = P ;
10. 1. ¬(P ∧ Q) = ¬P ∨ ¬Q,
    2. ¬(P ∨ Q) = ¬P ∧ ¬Q. (leggi di De Morgan)

In generale una fbf Q segue logicamente da una fbf P se e solo se ogni interpretazione che soddisfa P soddisfa anche Q. In questo caso la formula P ⊃ Q si dice teorema, dove P è l'ipotesi e Q la sua tesi. La dimostrazione di un teorema è una successione di passaggi, verificabili in modo meccanico e oggettivo, che trasformano l'ipotesi nella tesi. Scrivere programmi spesso richiede la dimostrazione di teoremi

1.2.2 Insiemistica

Un insieme è una qualsiasi collezione di elementi. Un elemento x che appartiene ad un insieme A si indica con la notazione x ∈ A. Due insiemi si dicono uguali se e solo se contengono gli stessi elementi. Un insieme A è sottoinsieme di B se e solo se ogni elemento di A è anche elemento di B. L'intersezione di due insiemi A ∩ B è l'insieme di tutti gli elementi comuni ad A e B. L'unione di due insiemi A U B è l'insieme di tutti gli elementi che appartengono ad A o a B, o ad entrambi. Un insieme che non contiene nessun elemento si chiama insieme vuoto e si indica con . Il complemento di un insieme A è l'insieme di tutti gli elementi che non appartengono ad A.

Gli insiemi godono delle seguenti proprietà:

1.Proprietà commutativa: A U B = B U A A ∩ B = B ∩ A 2.Proprietà associativa: A U ( B U C) = (A U B) U C

				A ∩ ( B ∩ C) = (A ∩ B) ∩ C

3.Proprietà distributiva: A U ( B ∩ C) = (A U B) ∩ (A U C)

				A ∩ ( B U C) = (A ∩ B) U (A ∩ C)

4.Idempotenza: A U A = A A ∩ A = A 5.Identità: A U  = A A ∩ U = A

				A ∩  = 		A U U = U

6.Proprietà transitiva dell'inclusione: se A  B  C, allora A  C 7.Involuzione: Ā = A 8.Leggi di De Morgan: A ∩ B = A U B A U B = A ∩ B

Dati n insiemi U1, U2, ... Un, il loro prodotto cartesiano U1 X U2 X ... X Un è l'insieme di tutte le n-uple ordinate (u1 X u2 X ... X un) dove ui ∈ Ui per i = 1, 2, ... , n.

Dati due insiemi A e B, una funzione f di dominio A e codominio B, in simboli f: A → B, è una mappa che associa ad ogni elemento a ∈ A un elemento b = f(a) ∈ A.

Una funzione f si dice iniettiva se e solo se x1  x2 implica f (x1)  f (x2). Una funzione si dice suriettiva se la sua immagine coincide con il suo codominio. Una corrispondenza biunivoca (o funzione biiettiva) è una funzione sia iniettiva che suriettiva.

La cardinalità di un insieme A è il numero di elementi che appartengono all'insieme A, e si denota ║A║. Dati due insiemi A e B: il prodotto cartesiano A × B ha una cardinalità data dal prodotto delle cardinalità degli insiemi A e B, cioè ║A × B║ = ║A║ · ║B║; l'insieme delle funzioni f: A → B ha una cardinalità esponenziale data da ║B║║A║; l'insieme di tutti i sottoinsiemi di A ha cardinalità 2║A║.

1.2.3 Logica dei predicati

La logica dei predicati consente di aggirare alcuni limiti di quella proposizionale (soprattutto a livello di astrazione).

La logica dei predicati è costituita da: simboli individuali (i nomi degli oggetti coinvolti nel ragionamento, chiamati istanze); variabili (tipo x, y e z), che assumono valori dall'insieme dei simboli individuali; simboli di funzione, utilizzati per costruire nuove istanze; simboli di predicato, utilizzati per costruire proposizioni su particolari istanze. I termini sono gli argomenti di un predicato nella logica dei predicati, ovvero delle entità sulle quali è possibile costruire affermazioni. Possono essere: simboli individuali; variabili; se f è una funzione n-aria e t1, ... , tn sono termini, anche f(t1, ... , tn) è un termine.

Attraverso l'utilizzo dei termini sarà possibile scrivere formule in cui ciascuna variabile può essere sostituita da una qualsiasi delle istanze. Usando dei quantificatori è possibile specificare se le variabili di una data proposizione si riferiscono a tutte le loro istanze o solo ad un numero più ristretto. Esistono due tipi di quantificatori, quello esistenziale ∃ (“esiste”) e quello universale ∀ (“per ogni”), applicabili alle sole variabili libere di una formula.

http://doppioclic.altervista.org/wiki/local/tetty/tabelle_verita.jpg

http://doppioclic.altervista.org/wiki/local/TettyImage/tabelleVerità.JPG

1.2.1 Logica Proposizionale

Per proposizione si intende una frase di senso compiuto che può essere vera o falsa. Generalmente ad ogni proposizione viene associato un simbolo per comodità di manipolazione (ad esempio, P: “è notte”).

Le proposizioni possono essere atomiche (semplici) o composte, queste ultime ottenute collegando una o più atomiche con i connettivi logici non (), e (), o (), implica (), se e solo se (≡). Le proposizioni atomiche e quelle composte prendono anche il nome di formule ben formate o fbf.

Il valore di verità di una fbf ci dice se questa è vera o falsa, e dipende dai valori di verità delle proposizioni che la compongono. Questi ultimi cambiano a seconda del contesto in cui li caliamo, ovvero dalla loro interpretazione (riprendendo l'esempio di prima, P è vero alle 2:00 am ma è falso alle 4:00 pm). Per interpretazione si intende un assegnamento di valori di verità ad ogni proposizione atomica.

Le tabelle di verità sono delle tabelle che indicano il valore di verità di una fbf a seconda del valore di verità delle sue “sotto-fbf”. Se una fbf è combinazione di n atomiche, la sua tabella di verità sarà formata da 2n righe. Le tabelle di verità dei connettivi logici sono:

(:title Tetty Cap 1:)

Concetti di base

Indice

1 Concetti di base

2 Elementi di matematica e logica per la programmazione

3 La nozione di “algoritmo” 4 I linguaggi di programmazione

5 Fasi della programmazione

6 Strumenti di modellazione della programmazione

7 Documentazione

1.1 Che cos'è la programmazione degli elaboratori

Per poter comprendere il concetto di programmazione degli elaboratori elettronici, è prima necessario chiarire cos'è un elaboratore elettronico, e quindi cosa significa programmarlo.

Gli elaboratori elettronici sono delle macchine per elaborare informazioni, dove per macchine si intendono dispositivi - anche molto complessi - il cui scopo è sostituire o facilitare il lavoro umano nello svolgimento di compiti ripetitivi, difficili o faticosi. Una macchina in grado di compiere più compiti è meglio di una che ne sa svolgere uno solo, dal momento che con un unico dispositivo (e quindi un'unica spesa, trasporto, manuale) otterremo qualcosa che normalmente richiederebbe l'impiego di più strumenti diversi. È questo concetto di versatilità che sta alla base della programmazione.

Gli elaboratori elettronici sono quindi programmabili per motivi economici e per versatilità.

Torna su

1.2 Elementi di matematica e logica per la programmazione

1.2.1 Logica Proposizionale

La logica proposizionale si occupa della verità o falsità di proposizioni, a loro volta composte sulla base della verità o falsità delle sotto-proposizioni che le compongono.

Per proposizione si intende una frase di senso compiuto che può essere vera o falsa. Generalmente ad ogni proposizione viene associato un simbolo per comodità di manipolazione (ad esempio, P: “è notte”).

Le proposizioni possono essere atomiche (semplici) o composte, queste ultime ottenute collegando una o più atomiche con i connettivi logici non (), e (), o (), implica (), se e solo se (≡). Le proposizioni atomiche e quelle composte prendono anche il nome di formule ben formate o fbf.

Il valore di verità di una fbf ci dice se questa è vera o falsa, e dipende dai valori di verità delle proposizioni che la compongono. Questi ultimi cambiano a seconda del contesto in cui li caliamo, ovvero dalla loro interpretazione (riprendendo l'esempio di prima, P è vero alle 2:00 am ma è falso alle 4:00 pm). Per interpretazione si intende un assegnamento di valori di verità ad ogni proposizione atomica.

Le tabelle di verità sono delle tabelle che indicano il valore di verità di una fbf a seconda del valore di verità delle sue “sotto-fbf”. Se una fbf è combinazione di n atomiche, la sua tabella di verità sarà formata da 2n righe. Le tabelle di verità dei connettivi logici sono: