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

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

[[Torna alla pagina di Programmazione degli Elaboratori -> Uni.ProgrammazioneElaboratori]]
----
[[!UniCrema]]

[[Torna alla pagina di Tetty -> Tetty]] | [[Guarda le domande sul capitolo -> TettyDom1]]

[[Torna alla pagina di Tetty -> Tetty]] | [[Guarda le domande sul capitolo -> TettyDom1]]

!Concetti di base

[[Torna alla pagina di Tetty -> Tetty]] | [[Guarda le domande sul capitolo -> TettyDom1]]

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”). %red%Molto importante ricordare come i quantificatori possano essere applicati alle sole variabili libere di una formula.%%

%red%L'algoritmo è una procedura passo per passo grazie alla quale un'operazione può essere svolta [[senza alcun esercizio di intelligenza->rasputin]] 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. %red%Un esempio legittimo di algoritmo potrebbe essere perfino una [[ricetta di cucina->pinguino]].

* %red%''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);

%red%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:

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), %red%l'analisi degli algoritmi si concentra sul caso peggiore (maggior impiego di tempo e di spazio possibile) per tre buoni motivi:

%red%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.

Dati ''n'' insiemi ''U'_1_', U'_2_', ... U'_n_''', il loro prodotto cartesiano ''U'_1_' X U'_2_' X ... X U'_n_''' è l'insieme di tutte le ''n''-uple ordinate (''u'_1_' X u'_2_' 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.

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.

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”. %red%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:

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

# P ∧ T = P , P ∨ ⊥ = P ;

(:title Tetty Cap 1:)
[[Torna alla pagina di Tetty -> Tetty]]
----

[[Torna alla pagina di Tetty -> Tetty]]

!!!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 %red%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->ronaldinho]] è 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”).

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 %red%''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à).

* %red%''inconsistente'' (o contraddizione), se è falsa per ogn 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

%red%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. %red%Perfino la formattazione di un programma (indentazione, distribuzione su più righe, ...) e le asserzioni sono una forma di documentazione interna.

%red%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

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.

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

%red%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.

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.

* %red%specifica;
* %red%progettazione;
* %red%modellazione;
* %red%codifica;
* %red%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 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.

%red%Una specifica formale è una quadrupla S = <X, Y, I, U>, dove:
* %red%X sono gli ingressi%%, ovvero i dati da fornire al programma;
* %red%Y sono le uscite%%, cioè i risultati che il programma deve produrre;
* %red%I sono le precondizioni%%, cioè le condizioni che gli ingressi devono rispettare;
* %red%U sono le postcondizioni%%, ovvero le proprietà che i risultati del programma devono soddisfare perché si possa dire che è corretto.

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

La progettazione consiste nell'analisi del problema da risolvere e nel concepimento in modo astratto dell'algoritmo. %red%Esistono due approcci antitetici alla progettazione:
* %red%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;
* %red%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.

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.

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.

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. %red%Si può dire che un programma è corretto solo quando soddisfa le sue specifiche.

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:

* i simboli non terminali sono rappresentati da stringhe alfanumeriche racchiuse tra parentesi angolari, come <espressione> ;

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

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.

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:
* %red%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 &#8745; &#931; = &#8709;;
* &#8721; è 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 &#8712; N) che indica un enunciato valido.

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

se A &#8804; B &#8804; C, allora A &#8804; C

&#8721; = {c,a}, &#8721;* = {&#1108;, c, a, ca, ac, acc, ..., acca, ..., cacca, ...}.

Una definizione più formale di linguaggio potrebbe essere: ''un linguaggio L è un sottoinsieme delle parole costruibili su un alfabeto &#8721;, L &#8804; &#61472;&#8721;*''. Ne consegue che, data una parola w &#8712; &#8721;* ci sono due possibilità:

Per rappresentare L è necessario definire una procedura in grado di generare tutte le sue parole. %red%Una grammatica è%% uno di questi sistemi generativi, %red%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 &#8745; &#931; = &#8709;;
* &#8721; è 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 &#945; &#8594; &#946;, dove &#945; &#8712; N* \ {&#1108;} e &#946; &#8712; (N &#8746; &#931;)*;
* S è il simbolo di partenza, un simbolo non terminale speciale (e quindi S &#8712; N) che denota 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 &#8721;, L &#61645;&#61472;&#8721;*. Ne consegue che, data una parola w &#8712; &#8721;* ci sono due possibilità:

* %red%''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);

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

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;

L’insieme dei segni convenzionali (simboli o token) grazie ai quali è possibile costruire gli enunciati di un linguaggio è chiamato indifferentemente alfabeto o vocabolario. %red%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 &#1108;. Se &#8721; è un alfabeto, &#8721;* indica l’insieme di tutte le parole composte da elementi di &#8721;, &#1108; compresa. Per esempio se &#8721; = {0,1}, &#8721;* = {&#1108;, 0, 1, 00, 01, 10, 11, …}.

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 x1 &#61625; x2 implica f (x1) &#61625; f (x2).

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'' &#8707; (“esiste”) e quello ''universale'' &#8704; (“per ogni”). %red%Molto importante ricordare come i quantificatori possano essere applicati alle sole variabili libere di una formula.%%

%red%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. %red%Un esempio legittimo di algoritmo potrebbe essere una ricetta di cucina.

* %red%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?'').

%red%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:

%red%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). %red%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), %red%l'analisi degli algoritmi si concentra sul caso peggiore (maggior impiego di tempo e di spazio possibile) perché:
* %red%stabilisce un limite superiore alle risorse che l'esecuzione dell'algoritmo potrebbe richiedere;

* %red%accade molto spesso che il caso medio è molto simile a quello peggiore.

%red%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.

* %red%''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.

Un ''insieme'' è una qualsiasi collezione di elementi.
Un elemento x che appartiene ad un insieme A si indica con la notazione x &#8712; 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 &#8745; 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 &#61638;.
Il complemento di un insieme A è l'insieme di tutti gli elementi che non appartengono ad A.

A U &#61638; = A --- A &#8745; U = A --- A &#8745; Ø = Ø --- A U U = U

se A &#61645; B &#61645; C, allora A &#61645; C

A U &#61638; = A --- A &#8745; U = A --- A &#8745; &#61638; = &#61638; --- A U U = U

%red%Le proposizioni possono essere atomiche (semplici) oppure composte. Le seconde sono ottenute combinando una o più atomiche con i connettivi logici ''non'' (¬), ''e'' (&#8743;), ''o'' (&#8743;), ''implica'' (&#61641;), ''se e solo se'' (&#8801;). Le proposizioni atomiche e quelle composte prendono anche il nome di ''formule ben formate'' o ''fbf''.

%red%Le proposizioni possono essere atomiche (semplici) oppure composte. Le seconde sono ottenute combinando una o più atomiche con i connettivi logici ''non'' (&#61656;), ''e'' (&#61657;), ''o'' (&#61658;), ''implica'' (&#61641;), ''se e solo se'' (&#8801;). Le proposizioni atomiche e quelle composte prendono anche il nome di ''formule ben formate'' o ''fbf''.

# P &#8743; > = P , P &#8744; &#8869; = P ;

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

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

%red%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;
* %red%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 %red%quantificatori%%, quello esistenziale &#8707; (“esiste”) e quello universale &#8704; (“per ogni”), %red%applicabili alle sole variabili libere di una formula.

Un insieme è una qualsiasi collezione di elementi.

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 &#8712; 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 &#8594; B, è una mappa che associa ad ogni elemento a &#8712; A un elemento b = f(a) &#8712; A.

Una funzione f si dice iniettiva se e solo se x1 &#61625; x2 implica f (x1) &#61625; 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 &#9553;A&#9553;. Dati due insiemi A e B:

* l'insieme delle funzioni f: A &#8594; B ha una cardinalità esponenziale data da &#9553;B&#9553;^&#9553;A&#9553;;
*%red%l'insieme di tutti i sottoinsiemi di A ha cardinalità 2^&#9553;A&#9553;.

%red%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.

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

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.

%red%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”).

%red%Le proposizioni possono essere atomiche (semplici) o composte, queste ultime ottenute collegando una o più atomiche con i connettivi logici non (&#61656;), e (&#61657;), o (&#61658;), implica (&#61641;), se e solo se (&#8801;). 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). %red%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”. %red%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:

* %red%valida (o tautologia), se è vera per qualsiasi interpretazione. Es. A &#61658; &#61656; A;
* %red%inconsistente (o contraddizione), se è falsa per ogn interpretazione. Es. A &#8743; &#61656; A;
* %red%soddisfacibile, se e solo se esiste almeno un'interpretazione per cui essa è vera, ovvero che la soddisfa.

!!!1.1 Che cos'è la programmazione degli elaboratori

!!!1.2 Elementi di matematica e logica per la programmazione

!!!!1.2.1 Logica Proposizionale

!!!!1.2.2 Insiemistica

!!!!1.2.3 Logica dei predicati

!!!1.3 La nozione di "algoritmo"

!!!1.4 I linguaggi di programmazione

!!!!1.4.1 Definizione formale di linguaggio

!!!!1.4.2 Grammatica

!!!!1.4.3 Grammatiche nel formato di Backus e Naur

!!!!1.4.4 Carte sintattiche

!!!!1.4.5 Linguaggi di alto e basso livello

!!!1.5 Fasi della programmazione

!!!!1.5.1 Specifica

!!!!1.5.2 Progettazione

!!!!1.5.3 Modellazione

!!!!1.5.4 Codifica

!!!!1.5.5 Verifica e correzione

!!!1.6 Strumenti di modellazione della programmazione

!!!!1.6.1 Diagrammi di flusso

!!!!1.6.2 Pseudocodice

!!!1.7 Documentazione

!!!!1.7.1 Documentazione interna

!!!!1.7.2 Documentazione esterna

1 [[#c11|Che cos'è la programmazione degli elaboratori]]

1 [[#c11|Concetti di base]]
-> 1.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:

3 [[#c13|La nozione di “algoritmo”]]

!!!La nozione di "algoritmo"

* semplici, quando sono risolvibili da algoritmi di ordine logaritmico o lineare;
* trattabili, quando hanno complessità polinomiale in tempo di calcolo;
* %red%difficili o intrattabili, quando richiedono una quantità esponenziale di tempo;
* %red%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.

2 [[#c11|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

* l'insieme delle funzioni f: A &#8594; B ha una cardinalità esponenziale data da &#9553;B&#9553;&#9553;A&#9553;;
*%red%l'insieme di tutti i sottoinsiemi di A ha cardinalità 2&#9553;A&#9553;.

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 &#8707; (“esiste”) e quello universale &#8704; (“per ogni”), applicabili alle sole variabili libere di una formula.

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

# Leggi di De Morgan:\\
A &#8745; B = A U B --- A U B = A &#8745; B

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 &#8707; (“esiste”) e quello universale &#8704; (“per ogni”), applicabili alle sole variabili libere di una formula.

3 La nozione di “algoritmo”

* valida (o tautologia), se è vera per qualsiasi interpretazione. Es. A &#61658; &#61656; A;
* inconsistente (o contraddizione), se è falsa per ogn interpretazione. Es. A &#8743; &#61656; A;
* soddisfacibile, se e solo se esiste almeno un'interpretazione per cui essa è vera, ovvero che la soddisfa.

##%alpha% ¬(P &#8743; Q) = ¬P &#8744; ¬Q,
## ¬(P &#8744; Q) = ¬P &#8743; ¬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 &#8835; 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 &#8745; B = B &#8745; A
2.Proprietà associativa: A U ( B U C) = (A U B) U C
A &#8745; ( B &#8745; C) = (A &#8745; B) &#8745; C
3.Proprietà distributiva: A U ( B &#8745; C) = (A U B) &#8745; (A U C)
A &#8745; ( B U C) = (A &#8745; B) U (A &#8745; C)
4.Idempotenza: A U A = A A &#8745; A = A
5.Identità: A U &#61638; = A A &#8745; U = A
A &#8745; &#61638; = &#61638; A U U = U
6.Proprietà transitiva dell'inclusione: se A &#61645; B &#61645; C, allora A &#61645; C
7.Involuzione: &#256; = A
8.Leggi di De Morgan: A &#8745; B = A U B A U B = A &#8745; B

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

%center%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 (&#61656;), e (&#61657;), o (&#61658;), implica (&#61641;), se e solo se (&#8801;). 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: