Elementi di informatica e programmazione

Elementi di informatica e programmazione

Introduzione

Cosa si intende per programmazione? La creazione di procedure per risolvere problemi. Si interagisce con una macchina che risolverà questi problemi. Per questo, bisogna trovare il procedimento, delle fasi, quali:

• Sviluppo
• Identificazione
• Progetto (definizione e architettura del software)
• Implementazione (codifica)
• Collaudo
• Manutenzione

Oggigiorno la programmazione è importante, in quanto siamo nella quarta rivoluzione industriale:

• Meccanica
• Elettronica
• Microelettronica
• Informatica (big data, artificial intelligence, internet of things...)

C è il secondo linguaggio di programmazione più diffuso al mondo, sotto Python e a seguire Java. C ha circa cinquant'anni, venne inventato negli anni Settanta del Novecento (1972), agli inizi dell’informatica. Questo linguaggio ha molti pregi:

• Efficacia: utile per operazioni veloci come i Kernel e per scrivere programmi efficienti che girano utilizzando poche risorse (come la memoria);
• Portabilità: funziona su molteplici piattaforme e per ogni piattaforma esistono compilatori C per cui un programma in C può essere portato da una piattaforma all’altra con poco sforzo. Anche grazie a questo il linguaggio C si diffonde più facilmente;
• Potenza: con poche istruzioni si può fare tanto;
• Semplicità: è un linguaggio piccolo, con poche parole chiave e istruzioni (come l'inglese, poche parole per più significati);
• Flessibilità: il programmatore ha molte libertà e si può utilizzare per applicazioni di varia natura.

Tuttavia, vi sono anche dei difetti:

• Incline agli errori: piccoli errori possono compromettere l'intero programma (es. una parola nel punto sbagliato comporta un crash del programma);
• Difficile da modificare.

I problemi e la loro soluzione

L'uomo aveva l'ambizione di creare una macchina che risolvesse per lui i problemi, che possono essere visti come una classe di domande omogenee a cui rispondere con una procedura uniforme. Troviamo vari elementi all’interno di un problema:

• L’istanza è la domanda;
• La soluzione dell’istanza;
• Le variabili d'ingresso: descrivono il caso in esame (il problema da risolvere) → dati (valori assunti);
• Le variabili d'uscita: rappresentano la soluzione del problema → risultati (valori assunti);
• Elaborazione: avviene quando si manipolano i dati in ingresso per ottenere le variabili d'uscita.

Esempi di problemi:

• P₁: Quanto vale la radice quadrata intera Y di un numero intero positivo X?
• P₂: Quanto vale la radice N-esima intera Y di un numero intero positivo X?
• P₃: Quanto vale la radice quadrata intera Y di un numero positivo X?

Abbiamo delle differenze sostanziali: Il problema P₂ include più variabili di P₁ (N, X, Y) mentre il problema P₃ ha le stesse variabili di P₁ ma ha un dominio più esteso (dom(P₃) → tutti i numeri &Reals;, dom(P₁) → tutti i numeri ℤ).

Risoluzione di un problema

La soluzione P₃ non è un numero, ma un procedimento. Il problema può essere risolto in cinque fasi, che sono:

• Identificazione: parte dalle esigenze del cliente (ingegneria del software)
• Analisi: trovare la soluzione
• Descrizione: esprimere in termini chiari per il soggetto2 (linguaggio formale = linguaggio di programmazione)
• Interpretazione descrizione
• Attuazione soluzione

In tutto ciò entrano in gioco due soggetti:

• Il soggetto 1 (persona) è colui che idea la soluzione del problema (cioè l'algoritmo)
• Il soggetto 2 (calcolatore) è colui che attua la risoluzione del problema

Trovata la soluzione, deve essere comprensibile anche al soggetto 2. L'algoritmo può essere definito come una procedura che specifica come produrre una soluzione per ogni possibile istanza del problema.

Non è detto che ogni problema sia risolvibile da una macchina, ma la maggior parte sì. Hilbert si pose questo quesito: è possibile descrivere una procedura puramente meccanica per dire se un problema è matematicamente vero o meno? Ciò porta alla discussione sui fondamenti della matematica. Nel XIX secolo si sono accorti che la matematica si basa su assiomi assodati, i postulati di Euclide. Nasce la crisi dei fondamenti della matematica, per portarla ad una base logica. Russell, filosofo, si accorse che mediante la logica si possono scrivere postulati che non hanno logica, come "il barbiere rade tutti coloro che non si radono da soli". Gadel, ispirandosi a Russell, ideò formule logiche che contraddicevano se stesse.

Alan Turing vuole rispondere al teorema di Hilbert, quindi creò una macchina teorica che "parla di se stessa", la macchina di Turing. Ovvero, quando un problema è risolto meccanicamente e si vuole determinare se un programma termina, ciò lo può fare solo il programma stesso. Se un programma termina, esistono un'infinità di algoritmi che lo risolvono.

Le prime tre fasi sono svolte da un calcolatore umano, poiché serve consapevolezza. Le ultime due sono svolte dal calcolatore.

Algoritmi

Il concetto di Algoritmo

L’algoritmo è un metodo, procedura o ricetta generale che specifica come produrre una soluzione per ogni possibile istanza del problema. Ciò viene specificato mediante una sequenza di istruzioni elementari. Risolvere un problema corrisponde a risolvere un'opportuna successione di problemi più semplici → scomposizione in sotto-problemi.

Problema: Quanto vale la radice quadrata intera Y di un numero intero positivo X?

Algoritmo:

• Assegna alla variabile Y il valore 1
• Se Y ≤ X allora vai al passo 3; altrimenti al passo 5 (salto condizionato)
• Incrementa Y di 1
• Vai al passo 2 (salto incondizionato)
• Decremento Y di 1
• Fine

I salti sono funzioni di controllo:

• Salto condizionato: si verificano se una condizione è vera o meno
• Salto incondizionato: si verificano sempre e non dipende dal verificarsi o meno di una certa condizione

Problema: Quanto vale il quadrato Z di un intero positivo Y?

Algoritmo:

• Assegna a Z il valore 0
• Assegna a X il valore 1
• Se X ≤ Y allora vai a passo 4; altrimenti vai al passo 7
• Incrementa Z di Y unità
• Incrementa X di 1 unità
• Vai al passo 3
• Fine

Supponiamo che Y sia 3, allora Z=0 e X=1; la disequazione del passo 3 è verificata → Z=3 e X=2; si torna al passo 3 dove la disequazione è verificata → Z = 6 e X = 3; torno al passo 3 e ho ancora la disequazione valida, quindi X=4 e Z=9; quindi si arriva al punto in cui la disequazione al passo tre non è più verificata e si arriva al passo 7. Si ha per soluzione che il quadrato di Y(3) è Z(9).

Il calcolatore come esecutore

Il calcolatore è un esecutore universale di algoritmi e possiede alcune qualità superiori al calcolatore umano:

• Velocità: essenziale per ottenere risultati in tempi brevi (es. regolatore del reattore nucleare);
• Affidabilità: seppur l'uomo bravo, può anche sbagliare, quindi i risultati ottenuti non sono corretti;
• Costo: i costi dell'operatore umano tendono a salire, quello dei calcolatori a scendere.

Affinché i programmi siano precisi, bisogna usare precisi elementi linguistici dell’esecutore:

• Il linguaggio che è in grado di interpretare. Ha una caratterizzazione sintattica, cioè definisce le regole di scrittura, ciò che la macchina comprende, quindi il linguaggio che l’esecutore è in grado di interpretare deve essere definito in modo completo e non ambiguo;
• L'insieme delle azioni che è in grado di compiere. Ha una caratterizzazione pragmatica, cioè l’insieme delle azioni che l’esecutore è in grado di compiere deve essere definito e finito, e tali azioni devono essere elementari per l’esecutore;
• L'insieme delle regole che a ogni frase del linguaggio associano le relative azioni da compiere. Ha una caratterizzazione semantica, cioè definisce le regole di significato, quindi l’insieme delle regole di associazione tra costrutti del linguaggio e azioni deve essere definito in modo completo e non ambiguo.

Si può inoltre andare incontro a degli errori che possono essere di vario tipo:

• Errori funzionali: se gli errori avvengono nella prima fase di identificazione, si sbaglia ad identificare il problema e questi sono difficili da risolvere;
• Errori logici:
• Primari → errore nella fase di analisi e cioè nella formulazione dell’algoritmo, che non risolve il problema e quindi si ha un’errata soluzione;
• Secondari → quando il programma non risolve il problema (algoritmo e soluzione non coincidono), in quanto si ha un errore nella fase di descrizione dell’algoritmo del programma.
• Si hanno anche errori nell’uso scorretto del linguaggio:
• Errori sintattici: quindi si ha sbagliato a scrivere la forma del programma:
• Forma dei singoli termini (parole chiave, stringhe, variabili, ...)
• Regole di composizione delle espressioni (operatori-operandi,...)
• Errori semantici: si ha sbagliato a scrivere il significato del programma:
• Operazioni con risultato indeterminato
• Operazioni con risultato diverso da quello desiderato

Scoperti attraverso l’ispezione del codice da parte del programma oppure facendo testing, quindi testando il programma con differenti input (disciplina del testing). Più l’errore è agli inizi e più costa correggerlo. Per quanto riguarda gli errori si ha una differenza sostanziale tra i due operatori → l’affidabilità. La macchina ha una percentuale molto bassa di errori che quasi sempre sono del primo operatore (la persona).

Computazione: definizioni

Quando si esegue un programma si parla di:

• Computazione: esecuzione di un algoritmo in corrispondenza di certi dati iniziali;
• Passo di computazione: ogni singolo passo elementare che l’esecutore compie durante una computazione;
• Processo: sequenza di passi elementari che l’esecutore compie in corrispondenza di certi dati iniziali durante l'esecuzione di un algoritmo;
• Flusso di esecuzione: ordine di esecuzione delle istruzioni.

Algoritmo = concetto statico
Processo = concetto dinamico → matura nel corso dell’esecuzione. Un processo può essere costituito da passi di computazione infiniti, portando a non ottenere mai il risultato desiderato. Ad ogni passo di computazione è necessaria una quantità di memoria finita, che deve comunque essere sufficiente per eseguire l'algoritmo.

Esempio:

1. Assegna a Y il valore 1
2. Se Y ≤ X allora vai al passo 3 altrimenti vai al passo 5
3. Incrementa Y di 1
4. Vai al passo 2
5. Decrementa Y di 1
6. Fine

Le istruzioni di un algoritmo sono eseguite nello stesso ordine in cui sono scritte a meno di istruzioni di controllo.

Proprietà di un Algoritmo

• Finitezza: costituito da un numero finito di istruzioni
• Univocità: ogni istruzione è univocamente interpretabile
• Effettività: esiste un esecutore capace di eseguire ogni istruzione in un tempo finito. Affinché ciò avvenga vengono richieste risorse finite (risorse di calcolo e memoria). Il calcolatore deve quindi avere questa disponibilità di risorse.
• Determinismo: per qualunque dato di ingresso, a ogni passo della computazione, esiste al più un passo successivo. Ci possono essere salti condizionati.
• Correttezza: calcola correttamente la funzione rappresentata
• Efficienza: arriva alla soluzione del compito impiegando una certa quantità di risorse fisiche. Se è efficiente in materia computazionale significa che è veloce. Meno risorse impiega, più efficiente l’algoritmo è.
• Terminazione: l'esecuzione termina in un numero finito di passi di computazione.

Algoritmo = variabili + istruzioni. L’algoritmo è per natura parametrico.

Variabili

Caratteristiche delle variabili:

• Hanno un nome per identificare univocamente la variabile
• Sono tipizzate, cioè è specificato un tipo di dato che possono contenere
• Hanno una locazione di memoria per conservare il dato che la variabile memorizza
• Gli può essere assegnato un solo valore
• Possono comparire in istruzioni di assegnamento ed espressioni

Classificate in base a:

• Visibilità da parte dell’utente: visibili o invisibili;
• Variabilità: costanti o variabili;
• Struttura: elementari o strutturate;
• Origine: definite/nuove (dal programmatore) o predefinite/originarie (dal linguaggio di programmazione);
• Visibilità nel codice: globale (visibile nell’intero codice/programma) o locale (visibile solo in una porzione del codice)
• Visibilità nel flusso di esecuzione: statica (sempre presenti per tutto il processo) o dinamica (solo in una porzione del processo)

Prima di poter usare il valore di una variabile è necessario assegnarlo (→ istruzione di assegnamento).

Istruzioni

Le istruzioni possono essere di: assegnamento, elaborazione, controllo, ingresso o uscita, controllo del flusso di esecuzione.

Istruzioni di Assegnamento

Sono usate per assegnare un valore, usualmente quello di un’espressione, ad una variabile o ad un elemento di vettore. Possono anche essere utilizzate per modificare i contenuti di locazione di memoria assoluta. La variabile può apparire nelle istruzioni o nell’espressione. Sono indicate con “x ←” dove x è la variabile (left value) e alla destra della freccia vi è una costante/variabile/espressione (right value).

ID ← costante variabile espressione

x ← 0 y y+1

Esistono tre tipi di espressioni:

• Espressioni aritmetiche, formate da:
• Operandi: variabili, costanti, espressioni aritmetiche
• Operatori: somma (+), sottrazione (-), moltiplicazione (*), divisione intera (/), resto (mod)
• Semantica: quella usuale dell’aritmetica
• Espressioni relazionali, formate da:
• Operandi: variabili, costanti, espressioni aritmetiche
• Operatori: operatori relazionali di uguaglianza (==), diversità (!=), minoranza (<) e maggioranza (>) fra numeri
• Semantica: quella delle disequazioni fra numeri
• Espressioni logiche e predicati logici, formati da:
• Operandi: variabili, costanti, espressioni relazionali
• Operatori: operatori logici, tra cui congiunzione (AND), disgiunzione (OR) e negazione (NOT)
• Semantica: quella dell'Algebra di Boole (logica proposizionale)

Algebra di Boole - Operatori

• Negazione not A ¬A –A
• Congiunzione A and B A B A×B∧
• Disgiunzione A or B A B A+B∨
• Disgiunzione esclusiva A xor B A^ B A B⊕
• Implicazione se…allora A→B A B⇒
• Doppia implicazione se e solo se A↔B A B⇔

Queste compaiono nelle istruzioni di controllo.

Proprietà degli operatori

Teorema di assorbimento - dimostrazione

A × (A + B) = (A × A) + (A × B) = A + (A × B) = A

A + (A × B) = (A × 1) + (A × B) = A × (1 + B) = A × 1 = A

Teorema di De Morgan - dimostrazione

¬(A + B) = ¬A × ¬B

Dimostrazione Proprietà utilizzata

(A + B) + ¬A × ¬B = → Distributiva += ((A + B) + ¬A) × ((A + B) + ¬B) = → Associativa += ((A + ¬A) + B) × ((B + ¬B) + A) = → Inverso += ((1) + B) × ((1) + A) = → Elemento nullo +=1+1=1

(A + B) × (¬A × ¬B) = → Distributiva ×= A × (¬A × ¬B) + B × (¬A × ¬B) = → Associativa ×= ¬B × (A × ¬A) + ¬A × (B × ¬B) = → Inverso ×= ¬B × (0) + ¬A × (0) = → Elemento nullo ×=0+0=0

Schemi a blocchi

Come ideare un algoritmo (SB) Un algoritmo può essere rappresentato in forma grafica attraverso gli schemi a blocchi (detti anche diagrammi di flusso).