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

Cos'è un'istanza?

E' una particolare domanda

Cos'è una soluzione?

E' la risposta ad una particolare domanda

Come si compone il procedimento risolutivo?

Il procedimento risolutivo consta di 5 fasi:

Individuazione —> si individuano 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

Lezione introduttiva: Algoritmi 1

prende il nome di programma.

"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^2 <== 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^2 <==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

✔

Lezione 1: Il calcolatore come

esecutore

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

gardo di comprendere

Azioni —> è necessario consocere 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 dle problema;

Lezione 1: Il calcolatore come esecutore 1

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.

Quali sono le strategie per individuare un errore nel codice?

Ispezionare il codice: leggere il codice

Testing: eseguire il codice

Cos'è la computazione?

E' 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?

E' una sequenza di passi elementari

Cos'è il flusso di esecuzione?

E' l'ordine di esecuzione delle istruzioni dell'algoritmo. In genere si procede

secondo l'ordine di scrittura, ma esistono anche istruzione 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?

E' un contenitore di dati.

Quali sono le caratteristiche delle variabili?

Lezione 1: Il calcolatore come esecutore 2

Hanno un nome;

Memorizzano un valore;

Hanno una locazione di memoria, per conservare il dato memorizzato dalla

variabile;

Compaiono in istruzioni o espressioni

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?

E' 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

Lezione 1: Il calcolatore come esecutore 3

possono essere inserite le variabili, mentre nell' R value possono essere inserite

variabili, costanti o espressioni.

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 condizione 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 di 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?

E' 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?

E' 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 si a 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?

E' 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