Appunti di elementi di informatica e programmazione, Programmazione C

Lezione introduttiva: algoritmi

Cos'è un problema?

Il problema è una classe di domande omogenee. Per risolverlo è possibile suddividerlo in sotto-problemi più piccoli, o istruzioni elementari.

Cos'è un'istanza?

È una particolare domanda.

Cos'è una soluzione?

È la risposta ad una particolare domanda.

Come si compone il procedimento risolutivo?

Il procedimento risolutivo consta di 5 fasi:

• Individuazione —> si individua il problema da risolvere.
• Analisi —> si idea la risoluzione del problema.
• Descrizione —> si descrive la soluzione ideata.
• Interpretazione della descrizione —> traduzione della soluzione ideata in un linguaggio comprensibile all'operatore umano in un linguaggio comprensibile dal calcolatore. Tale linguaggio prende il nome di linguaggio-macchina ed è formato dai simboli 0 e 1.
• Attuazione soluzione —> esecuzione dell'algoritmo risolutivo del problema.

Quali operatori sono adibiti alle diverse fasi del procedimento risolutivo?

Le prime tre fasi sono a carico di un operatore umano, mentre le ultime due fasi sono a carico di un calcolatore. Questo perché esso è più veloce, affidabile e meno costoso rispetto ad un operatore umano nell'eseguire tali fasi.

Cos'è un algoritmo?

Un algoritmo è il metodo che specifica come produrre la soluzione per ogni istanza tramite una sequenza di istruzioni.

L'algoritmo deve essere scritto mediante un linguaggio di programmazione affinché venga correttamente eseguito dal calcolatore. L'algoritmo così scritto prende il nome di programma.

Lezione introduttiva: Algoritmi 1

"Qual è la radice quadrata intera Y di 9?"

Individuazione: trovare la radice quadrata di 9;

Analisi + Descrizione:

• 1. Assegna ad Y il valore 1;
• 2. Se Y² <== X allora vai al passo 3; altrimenti vai al passo 5;
• 3. Incrementa Y di 1 unità;
• 4. Vai al passo 2;
• 5. Decrementa Y di 1 unità;
• 6. Fine.

Interpretazione: l'algoritmo assegna ad Y il valore di 1. Siccome il quadrato di 1 rispetta la condizione Y² <== X, allora si va al passo 3 con un salto condizionato e si incrementa di 1 il valore di Y, ottenendo Y = 2. A questo punto con un salto incondizionato si torna al passo 2 e si procede di nuovo con la verifica della condizione. Siccome la verifica, allora si incrementa ancora di 1 Y, quindi Y = 3. Si torna al passo 2. Anche in questo caso la condizione è verificata perché abbiamo 9 = 9, si procede come prima aumentando di 1, quindi Y = 4. Questa volta 16 > 9, quindi la condizione non è verificata. Decrementiamo allora di 1 il valore di Y come suggeritoci dal salto condizionato al passo 2. Otterremmo quindi che Y = 3 e questa è anche la soluzione.

Lezione 1: il calcolatore come esecutore

Lezione introduttiva: Algoritmi 2

Cos'è il calcolatore come esecutore?

Un calcolatore è un sistema che, ricevendo in ingresso la descrizione, in un opportuno linguaggio, di un algoritmo risolvente A[X,Y] per un certo problema P[X,Y] e un dato X, produce come risultato la soluzione Y dell’istanza P[X,Y].

Il calcolatore è un esecutore di programmi, non risolve il problema!

Perché il calcolatore è detto anche esecutore universale di algoritmi?

Perché dovrebbe poter operare su qualsiasi tipologia di algoritmo e per un qualsiasi dato iniziale consono a tale algoritmo.

Quali sono gli elementi linguistici dell'esecutore?

• Linguaggio —> è necessario utilizzare un linguaggio che il calcolatore è in grado di comprendere.
• Azioni —> è necessario conoscere le azioni che l'esecutore è in grado di compiere.
• Regole —> è necessario rispettare che linguaggio e azioni rispettino determinate regole.

Che tipo di caratterizzazione è il linguaggio?

Sintattica —> la sintassi è l'insieme delle istruzioni che regolano la scrittura.

Che tipo di caratterizzazione sono le azioni?

Pragmatica.

Che tipo di caratterizzazione sono le regole?

Semantica —> insieme di istruzioni che regolano il significato della scrittura.

Quali tipologie di errori nella risoluzione esistono?

Esistono 3 tipologie di errori:

• Errori funzionali: riguardano l'errata identificazione del problema;
• Errori logici primari: riguardano l'errata identificazione della soluzione;
• Errori logici secondari: nella fase di descrizione il programma non corrisponde all'algoritmo ideato, ad esempio per uno scorretto utilizzo del linguaggio o nella sintassi o nella semantica.

Lezione 1: Il calcolatore come esecutore 1

Quali sono le strategie per individuare un errore nel codice?

• Ispezionare il codice: leggere il codice.
• Testing: eseguire il codice.

Cos'è la computazione?

È l'esecuzione di un algoritmo in corrispondenza di certi dati iniziali. Le fasi della computazione prendono il nome di passi di computazione.

Cos'è un processo?

È una sequenza di passi elementari.

Cos'è il flusso di esecuzione?

È l'ordine di esecuzione delle istruzioni dell'algoritmo. In genere si procede secondo l'ordine di scrittura, ma esistono anche istruzioni che variano l'ordine. Es. le istruzioni di controllo producono dei salti condizionati.

Quali sono le proprietà di un algoritmo? (7)

• Finitezza: è composto da un numero finito di istruzioni;
• Univocità: ogni istruzione deve essere univocamente interpretata;
• Effettività: deve esistere un esecutore in grado di eseguire le istruzioni dell'algoritmo in un tempo finito;
• Determinismo: dato un dato di ingresso, ad ogni passo computazionale deve esistere al più un passo successivo;
• Correttezza: l'algoritmo calcola correttamente la funzione che rappresenta;
• Efficienza: utilizza una data quantità di risorse fisiche, tempo e memoria, per arrivare alla soluzione;
• Terminazione: termina in un numero finito di istruzioni.

Cos'è una variabile?

È un contenitore di dati.

Quali sono le caratteristiche delle variabili?

• Hanno un nome;
• Memorizzano un valore;
• Hanno una locazione di memoria, per conservare il dato memorizzato dalla variabile;
• Compaiono in istruzioni o espressioni.

Lezione 1: Il calcolatore come esecutore 2

Come possono essere classificate le variabili?

A seconda:

• Visibilità da parte dell'utente: visibili (se di I/O) / trasparenti (se atte a memorizzare);
• Variabilità: variabili / costanti;
• Struttura: elementari (memorizzare un valore unico, elementare) / strutturate (per memorizzare dati composti come tabelle, sequenze di caratteri = stringa, data);
• Visibilità nel codice: locale (se visibile in una porzione di codice) / globale (se visibile nell'intero programma);
• Visibilità nel flusso di esecuzione: memorizzate dinamicamente (se visibili solo per un pezzo di flusso) / memorizzate staticamente (se visibili sempre);
• Origine: da chi idea il linguaggio di programmazione / dal programmatore.

Cos'è un'istruzione?

È il singolo comando che un programma trasmette ad un elaboratore per compiere una determinata operazione.

Quali tipologie di istruzioni esistono?

• Istruzioni di assegnamento o elaborazione: assegna un valore ad una variabile;
• Istruzioni di ingresso o uscita: per portare all'interno o all'esterno dati;
• Istruzioni di controllo: variano il flusso di esecuzione;
• Istruzioni aritmetico-logiche: riguardano espressioni.

Da cosa sono formate le istruzioni di assegnamento?

Sono formate da un L value, posto a sinistra di una freccia rivolta verso questo valore, e da un R value posto alla destra della freccia. es. x ← y. Nel L value possono essere inserite le variabili, mentre nell'R value possono essere inserite variabili, costanti o espressioni.

Lezione 1: Il calcolatore come esecutore 3

Esempio istruzione di assegnamento o elaborazione: "scambiare il valore di X con il valore di Y"

x = 7; y = 9. Obiettivo: x = 9; y = 7.

Si utilizza la variabile thp per conservare il valore di x a cui si sovrascriverà il valore di y, così da non perdere l'informazione "7".

Algoritmo:

• 1. Assegna ad x il valore 7;
• 2. Assegna ad y il valore 9;
• 3. Acquisisci thp;
• 4. Assegna a thp il valore 7;
• 5. Assegna ad x il valore 9;
• 6. Assegna ad y il valore 7;
• 7. Fine.

Quali tipologie di espressione fanno parte delle istruzioni aritmetico-logiche?

• Espressioni aritmetiche.
• Espressioni relazionali.
• Espressioni logiche.

Da cosa sono formate le espressioni aritmetiche?

• Operandi: variabili, costanti, espressioni;
• Operatori: somma (+), sottrazione (-), prodotto (*), divisione (/);
• Semantica: la stessa dell'aritmetica.

Da cosa sono formate le espressioni relazionali?

• Operandi: variabili, costanti, espressioni;
• Operatori: uguaglianza (= =), diversità (! =), disuguaglianza (minoranza <, maggioranza >), e gli stessi combinati (es. minore uguale <==);
• Semantica: la stessa delle disequazioni;
• Risultato: V o F (oppure T o F).

Lezione 1: Il calcolatore come esecutore 4

Da cosa sono formate le espressioni logiche?

• Operandi: variabili, costanti, espressioni;
• Operatori: AND, OR, NOT:
• – 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
• Semantica: Algebra di Boole: http://people.unipmn.it/bobbio/DIDATTICA/ARCH1_00/ALDISP_00/varbol00.pdf

Lezione 1: Il calcolatore come esecutore 5

Lezione 1: Il calcolatore come esecutore 6

Dove compaiono gli operatori dell'algebra di Boole?

Compaiono nelle condizioni delle istruzioni di controllo.

Quali sono le proprietà booleane? (9)

Lezione 1: Il calcolatore come esecutore 7

Dimostra proprietà assorbimento

A + (A x B) = (A x 1) + (A x B) = (A x A) x (1 + B) = A x 1 = A

A x (A + B) = (A x A) + (A x B) = A + (A x B) = A

Dimostra proprietà di De Morgan

Proprietà 1: (A x B) x (-A + -B) = 0 —> (A x B x (-A)) + (A x B x (-B)) = (A x (-A) x B) + (B x (-B) x A) = (0 x B) + (0 x A) = 0 + 0 = 0

Proprietà 2: (A x B) + (-A + -B) = 0 —> (A + (-A + -B)) x (B + (-A + -B)) = (1 + (-B)) x (1 + (-A)) = 1 x 1 = 1

Dimostrazione De Morgan: - (A x B) = ((- A) + (-B))

Dalla dimostrazione delle proprietà 1 e 2 si deduce che (A x B) = - ((-A) + (-B)), perché in AND se (A x B) = 1 → per avere come risultato 0 (-A + -B) deve essere 0, viceversa in OR se (A x B) = 0 → per avere come risultato 1 (-A + -B) deve essere 1.

Lezione 1: Il calcolatore come esecutore 8

Quindi: (A x B) = - ((-A) + (-B)) —> - (A x B) = - - ((-A) + (-B)) —> - (A x B) = ((-A) + (-B))

https://it.wikipedia.org/wiki/Teoremi_di_De_Morgan

Cos'è uno schema a blocchi?

Descrizione grafica di un algoritmo. Si dicono anche diagrammi di flusso o flow chart.

Quale simbologia viene utilizzata?

Cos'è un blocco di Input-Output?

Input: un dato esterno entra nella variabile X.

All'interno del parallelogramma si scrive: X ←

Output: un dato interno alla variabile X esce.

All'interno del parallelogramma si scrive: ← X

Cos'è un blocco di elaborazione?

Assegnazione di un dato n (variabile, costante, espressione) ad una variabile X.

All'interno del rettangolo si scrive: X ← n

Cos'è un blocco di controllo?

Lezione 1: Il calcolatore come esecutore 9

Condizione o predicato composta da operatori logico-relazionali o relazionali, la quale ha due rami di uscita che corrispondono a V, se la condizione è verificata, a F, se la condizione non è verificata.

All'interno del rombo si inserisce la condizione: ad esempio x < 10, oppure x < 10 AND x > 20

Cos'è un sottoprogramma?

È un blocco che mi consente di introdurre nello schema dell'algoritmo un altro algoritmo precedentemente svolto, senza complicarne la descrizione grafica.

All'interno del rettangolo con due linee ai lati si scrive: variabile ← risultato funzione. Ad esempio se voglio scrivere che alla variabile MAX deve essere assegnato il risultato della funzione MAX(x;y), che ha lo scopo di trovare il massimo tra i numeri x e y, scriverò: MAX ← MAX (x ; y)

Cos'è un cammino?

È una sequenza di blocchi (Y_1, Y_2, Y_3,....Y_n) tali che due blocchi consecutivi (Y_1, Y_1+1) siano collegati da un arco. Se in tale sequenza Y_1 = Y_n, allora la sequenza prende il nome di CICLO.

Qual è la differenza tra funzione e procedura?

La funzione dà un risultato, la procedura no.

"Calcola il massimo di 2 dati input"

• 1. Acquisisci X; (parallelogramma con X ←)
• 2. Acquisisci Y; (parallelogramma con Y ←)
• 3. Assegna a MAX il valore di X; (rettangolo con MAX ← X)
• 4. Se Y > MAX, allora vai al passo 5; altrimenti vai al passo 6; (rombo con condizione Y > MAX scritta all'interno e due rami uscenti di cui, quello vero collegato al blocco successivo, quello falso collegato al blocco 6)
• 5. Assegna a MAX il valore di Y; (rettangolo con MAX ← Y)
• 6. Visualizza MAX; (parallelogramma con ← MAX)
• 7. Fine. (Trapezio)

Precedente: Lezione introduttiva: Algoritmi

Successiva: Lezione 2: Tecniche di progettazione

Lezione 1: Il calcolatore come esecutore 10

Lezione 2: tecniche di progettazione

1. Quali sono le tecniche di progettazione?

La tecnica di progettazione detta TOP-DOWN fa sì che si risolva un problema dando per scontato che siano già stati risolti i suoi sotto-problemi.

La tecnica di progettazione BOTTOM-UP fa sì che si risolvano prima i vari sotto-problemi per poi dare soluzione al problema generale.

2. Esempio TOP-DOWN: "Visualizza il massimo tra n interi acquisiti a tastiera"

Flow chart

Lezione 2: Tecniche di progettazione 1

Lezione 2: Tecniche di progettazione 2

Algoritmo:

• 1. Acquisisci un intero n;
• 2. Acquisisci un intero x;
• 3. Assegna a MAX il valore di x;
• 4. Assegna a i il valore di 1;
• 5. Se i < n, allora vai al passo 6; altrimenti vai al passo 10;
• 6. Acquisisci un intero x;
• 7. Assegna a MAX il massimo tra max e x —> do per assunto che questo sotto-problema sia già stato risolto;
• 8. Incrementa i di 1 unità;
• 9. Vai al passo 5;
• 10. Visualizza MAX;
• 11. Fine.

3. Cos'è uno schema a blocchi strutturato (SBS)?

Lo schema a blocchi strutturato è un programma che viene descritto da un linguaggio sottoposto a vincoli da rispettare. Questo consente di superare alcuni problemi causati dagli schemi a blocchi non strutturati, come ad esempio la difficile lettura e modifica.

4. Cos'è un blocco strutturato composto (BSC)?

Lezione 2: Tecniche di progettazione 3

Il BSC è il corpo di un SBS. (Nel disegno BSC deve essere rappresentato con un rettangolo con cornice su tutti e 4 i lati)

5. Quali tipologie ci sono per i BSC?

• 1. Struttura di controllo (casi ricorsivi)
• 2. Blocco funzionale semplice (casi base)
• 3. Blocco nullo (caso ricorsivo)

6. Quali tipologie esistono per le strutture di controllo?

• 1. Sequenza: si eseguono più operazioni in cascata. Definizione ricorsiva: sequenza di 2 BSC.

Lezione 2: Tecniche di progettazione 4

• 2. Selezione a due vie: due operazioni da eseguire in alternativa. Qualora BSC sia nullo, si ha la selezione semplice.
• 3. Ciclo a condizione iniziale: la condizione è in ingresso nel ciclo, dunque prima si verifica la condizione e poi si esegue il BSC.

Lezione 2: Tecniche di progettazione 5

Vale anche la condizione di permanenza.

7. Cos'è la condizione di permanenza?

È la condizione per la quale si resta nel ciclo fintanto che la condizione è verificata. Viceversa, se la condizione non è verificata si esce dal ciclo.

8. Quali tipologie esistono per i blocchi funzionali semplici?

• 1. Blocco di elaborazione
• 2. Blocco di I/O
• 3. Blocco sottoprogramma

9. Esempio per condizione di terminazione e di permanenza

Condizione di terminazione: x ≤ 10 AND x ≥ 20;

—> applico De Morgan - (x ≥ 10 AND x ≤ 20)

Condizione di permanenza: x < 10 OR x > 20

12. Come passare da uno schema a blocchi non strutturato ad un SBS?

Lezione 2: Tecniche di progettazione 6

Dato lo schema iniziale costituito da blocchi "Inizio", "BSC" e "Fine" si sostituisce passo passo ad ogni "BSC" una delle strutture di controllo oppure un blocco funzionale fino a quando tutti i BSC sono stati eliminati. (vedi esempio con commento)

Lezione 2: Tecniche di progettazione 7

Lezione 2: Tecniche di progettazione 8

13. Il linguaggio SBS può rappresentare un algoritmo per qualsiasi problema solubile?

Potenza computazionale: SBS ammette almeno 1 algoritmo per ogni problema solubile;

Potenza espressiva: SBS ammette ogni algoritmo per ogni problema solubile.

14. Cos'è l'equivalenza debole?

Due schemi a blocchi (SB) si dicono debolmente equivalenti se producono gli stessi risultati per ogni input.

15. Cos'è l'equivalenza forte?

Due schemi a blocchi (SB) si dicono fortemente equivalenti se producono le stesse sequenze di computazione per ogni input.

Se X è fortemente equivalente ad Y, allora X è anche debolmente equivalente a Y.

16. Esempio di blocchi debolmente equivalenti

Le istruzioni (y ← y + 1) e (y ← y - 1) si annullano, dunque i due diagrammi sono debolmente equivalenti.

Lezione 2: Tecniche di progettazione 9

17. Teorema di Bohm - Jacopini

Lezione 2: Tecniche