Elementi di Informatica e Programmazione C

Martina Contestabile Ingegneria Informatica Comune A-L, A.A. 2020/21

ELEMENTI DI INFORMATICA E PROGRAMMAZIONE

cultura informatica

Fornire fondamenti della

Cos’è un algoritmo e cos’è un calcolatore

La codi ca delle informazioni

Architettura del calcolatore

Il sistema operativo

Le rete

È una prima introduzione alla programmazione mediante l'utilizzo del linguaggio C. Vengono

approfondite le nozioni fondamentali relative alla struttura e al progetto di programmi.

Lunedì 14 Settembre 2020

Introduzione

Programmare: creare procedure per risolvere problemi.

Si interagisce con una macchina che risolverà problemi. Per questo, bisogna trovare il

procedimento.

Oggigiorno è importante, siamo nella quarta rivoluzione industriale:

I. Meccanica

II. Elettronica

III. Microelettronica

IV. Informatica (big data, internet of things…)

C è il linguaggio di programmazione più di uso al mondo, a seguire Java e Phyton. C ha circa

cinquant’anni, venne inventato negli anni Settanta del Novecento (1972). Per le sue

caratteristiche, è particolarmente adatto:

E cacia (utili per operazioni veloci come i Kernel)

Portabilità (per ogni nuova piattaforma bisogna scrivere un compilatore, il

linguaggio C si di onde più facilmente)

Potenza (con poche istruzioni si può fare tanto)

Semplicità (poche parole chiave; come l’inglese, poche parole per più signi cati)

Flessibilità (il programmatore ha molte libertà)

Tuttavia, vi sono anche dei contro: ⇒

• Incline agli errori (parola nel punto sbagliato programma in crash)

• Di cile da capire/modi care

I problemi e la loro soluzione

L’uomo aveva l’ambizione di cerare una macchina che risolvesse per lui i problemi.

Il problema può essere visto come una classe di domande omogenee.

L’istanza è una domanda. ⇒

Variabili d’ingresso: descrivono il caso in esame (il problema da risolvere) dati (valori assunti)

⇒

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

Pagina 1

ffi ffi fi ff fi ff fi

Martina Contestabile Ingegneria Informatica Comune A-L, A.A. 2020/21

⇒

P1: Quanto vale la radice quadrata intera Y di 49 ISTANZA

P2: Quanto vale la radice N-esima intera Y di…

P3: Quanto vale la radice quadrata intera Y di un positivo X

La risoluzione dei problemi

Risoluzione di un problema: procedimento.

La soluzione P3 non è un numero, ma un Il problema può essere risolto in cinque

fasi, che sono: Identi cazione, parte dalle esigenze del cliente (ingegneria del software)

Analisi, trovare la soluzione

1

Descrizione, esprimere in termini chiari per il soggetto 2 (linguaggio formale =

linguaggio di programmazione)

Interpretazione descrizione

Attuazione soluzione

In tutto ciò possono entrare in gioco due soggetti. Il soggetto 1 è colui che idea la soluzione del

problema (che è l’algoritmo), il soggetto 2 è colui che attua la risoluzione del problema (nel nostro

caso, il calcolatore).

Trovata la soluzione, deve essere comprensibile anche al soggetto 2. L’algoritmo può essere

de nito come una procedura che speci ca come produrre una soluzione per ogni possibile

istanza del problema.

noi ci concentriamo sul secondo e terzo punto

1 Pagina 2

fi fi fi

Martina Contestabile Ingegneria Informatica Comune A-L, A.A. 2020/21

Risoluzione del problema

Creiamo un algoritmo: Radice quadrata intera Y (v. uscita) di un intero X (v. ingresso)? Posto X=49,

allora:

1. Assegno a Y il valore 1

2

Y ≤ X condizionato)

2. Se allora vai al passo 3; altrimenti al passo 5 (salto

3. Incremento Y di 1 unità

incondizionato)

4. Vai al passo 2 (salto

5. Decremento Y di 1 unità

6. Fine

I salti sono funzioni di controllo: salto condizionato se una condizione è vera o meno, i salti

incondizionati si veri cano se le funzioni non si veri cano nell’ordine in cui sono scritte.

Calcolare il quadro Z di un intero Y

1. Assegna Z a 0

2. Assegna a W valore 1

W ≤ Y

3. Se allora vai a passo 4, altrimenti passo 7

4. Incrementa W di 1 unità

5. Incrementa Z di 3 unità

6. Vai al passo 3

7. Fine

Supponiamo che Y sia 3, allora Z=0 e W=1; la disequazione del passo 3 è veri cata, vado al

passo 4 e W=2 e Z=3; al passo 3 la disequazione è veri cata, allora W=3 e Z=6; torno al passo 3

e ho ancora la disequazione valida, quindi W=4 e Z=9; quindi si arriva al punto in cui la

disequazione al passo tre non è più veri cata e si arriva al passo 7.

Non è detto che ogni problema sia risolvibile da una macchina, ma la maggior parte sì.

Hilbert 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, losofo, 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 sé stesse. Pagina 3

fi fi fi fi fi fi

Martina Contestabile Ingegneria Informatica Comune A-L, A.A. 2020/21

Alan Turing volle rispondere al teorema di Hilbert, quindi creò una macchina teorica che “sparlava

di sé stessa”, la macchina di Turing. Ovvero, quando un problema è risolto meccanicamente e si

vuole determinare se un programma termina, e ciò lo può fare solo il programma stesso. Se un

programma termina, esistono un’in nità di algoritmi che lo risolvono. Giovedì 17 Settembre 2020

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

due dal calcolatore.

L’interpretazione traduce l’informazione dal linguaggio di programmazione al linguaggio consono

al calcolatore (costituiti dai simboli 0 e 1).

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

calcolatore umano:

Velocità: essenziale per ottenere risultati in tempi brevi (esempio = regolatore del

reattore nucleare)

A dabilità: 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 Pagina 4

ffi fi

Martina Contestabile Ingegneria Informatica Comune A-L, A.A. 2020/21

A nché i programmi siano precisi, bisogna seguire elementi linguistici.

Il linguaggio fa una caratterizzazione sintattica (de nisce ciò che la macchina comprende, regola

la scrittura), le azioni una caratterizzazione pragmatica (numero nito, ben de nite ed elementari),

le regole, in ne, una caratterizzazione semantica (regola le istruzioni e le azioni dell’esecutore).

errore funzionale.

Se gli errori avvengono nella fase di identi cazione, si parla di

errori logici primari

Se avviene nella fase di analisi, si parla di (errata soluzione del problema).

errori logici secondari

Se avviene nella descrizione, si parla di (algoritmo e soluzione non

coincidono), ci sono errori sintattici o semantici. Per risolvere, bisogna ispezionare il codice, come

se avessimo una scheda e dovessimo rispondere alle domande, o fare testing, ovvero far girare il

codice e vedere in che punto è l’errore.

Più l’errore è a valle, più costa correggerlo.

Un processo può essere costituito da passi di computazione in niti, portando a non ottenere mai

il risultato desiderato. Ad ogni passo di computazione è necessaria una quantità di memoria nita,

ma la memoria deve essere su ciente per eseguire l’algoritmo. Pagina 5

ffi fi ffi fi fi fi fi fi fi

Martina Contestabile Ingegneria Informatica Comune A-L, A.A. 2020/21

Gli algoritmi possiedono una serie di proprietà:

I. Finitezza: un numero nito di istruzioni

II. Univocità: essere univocamente interpretabile

Δt

III. E ettività: eseguire le istruzioni in un nito

IV. Determinismo: per ogni dato in ingresso, ad ogni passo della computazione, esiste

al più un passo successivo (una conseguenza è che la sequenza di computazione

è unica)

V. Correttezza: calcola correttamente la funzione che esso rappresenta

VI. E cenza: arriva alla soluzione con una determinata quantità di risorse siche

(calcoli e memoria); meno calcoli e memoria eseguiti comportano ad una maggiore

e cenza

VII. Terminazione: numero nito di passi di computazione

L’algoritmo possiede variabili ed istruzioni.

Le variabili hanno un nome per ogni linguaggio di programmazione, ognuna ha un nome per

essere indicata univocamente. Hanno una locazione di memoria, per conservare il dato che la

variabile memorizza. Può avere un valore. Si possono trovare in istruzioni di assegnamento ed

espressioni. Possono essere classi cate in base alla visibilità all’utente (visibili o invisibili),

variabilità (costanti o variabili), struttura (elementari o strutturate, che memorizzano dati composti),

visibilità nel codice (visibile in una porzione di codice -locale - o nell’intero programma - globale -),

visibile nel usso di esecuzione (memorizzate staticamente = sempre presenti, memorizzate

dinamicamente/dinamiche = in una porzione). Le variabili possono essere originarie o nuove,

create dal programmatore.

Le istruzioni sono di vari tipi:

• Assegnamento

Le 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 modi care i contenuti di locazioni

di memoria assoluta. La variabile può apparire

nelle istruzioni o nell’espressione. Sono

x ← left

indicate con (x è la variabile, della

value), ciò che si trova a destra della freccia è una costante/espressione (right

value). Ci sono tre tipi di espressioni: Pagina 6

ffi

ff

ffi fl fi fi fi fi fi fi

Martina Contestabile Ingegneria Informatica Comune A-L, A.A. 2020/21

- Aritmetiche: formate da operandi (variabili, costanti, espressioni

aritmetiche) e operatori (addizione, sottrazione, resto - mod -…),

Prima di usare il valore di una variabile, bisogna

semantica (aritmetica).

assegnarlo (tramite istruzioni di assegnamento..).

- Relazionali: operandi (variabili, costanti, espressioni aritmetiche),

operatori (operatori relazionali di uguaglianza ==, diversità !=, minoranza

<, maggioranza >), semantica (disequazioni).

- Logiche e predicati logici: operandi (variabili, costanti, espressioni

relazionali), operatori (operatori logici, come congiunzione - AND -,

disgiunzione - OR -, e negazione - NOT -), semantica (algebra di Boole,

logica proposizionale).

• Elaborazione

• Controllo

• Ingresso o uscita

• Controllo del usso di esecuzione

Il processo è una serie di passi di computazione! Non possono avvenire due o più operazioni in

simultanea!

Compaiono nelle

istruzioni di

controllo Proprietà degli operatori:

Proprietà AND (X) OR (+)

Identità A x 1= A A + 0 = A

Elemento nullo A x 0 = 0 A + 1 = 1 (a prescindere dal

valore di A) Pagina 7

fl

Martina Contestabile Ingegneria Informatica Comune A-L, A.A. 2020/21

Proprietà AND (X) OR (+)

A × −A = 0 A + −A = 1

Inverso

Idempotenza A x A = A A + A = A

Commutativa A x B = B x A A + B = B + A

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

Associativa A + (B × C ) = (A + B) × (A + C )

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

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

Assorbimento −(A × B) = (−A) + (−B) −(A + B) = (−A) × (−B)

De Morgan A + (A × B) = (A × A) + (A × B)

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

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

= A + (A × B) = A

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

(A × B) × (−A + −B) = 0

1.

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

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

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

2.

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

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

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

Come ideare un algoritmo

Un algoritmo può essere rappresentato in forma gra ca attraverso gli schemi a blocchi (detti

anche diagrammi di usso o owchart). Pagina 8

fl fl fi

Martina Contestabile Ingegneria Informatica Comune A-L, A.A. 2020/21

x ← ← x

I blocchi di input ( ) e output ( ) hanno

forme trapezoidali, per l’input si dà un valore alla

x

variabile , per l’output si visualizza il valore della

x

variabile .

L’elaborazione ha forma rettangolare, all’interno va

l’istruzione di assegnamento.

Le istruzioni di controllo hanno forma di rombo con

due archi uscenti, al suo interno vi è il predicato,

detta anche espressione condizionale, che è

composta dagli operatori relazionali/logico-

relazionali. Le freccette hanno scritto Sì/No o Vero/

Falso.

Sottoprogramma è un rettangolo sbarrato, è

un’operazione non elementare, indica un altro algoritmo.

La funzione restituisce un valore, la procedura no!

max

La funzione deve essere spiegata al calcolatore, strutturata e dotata di struttura a blocchi.

Y = Y

Se allora la sequenza è un ciclo.

1 n

Esempio: x

1. Acquisisci y

2. Acquisisci max

3. Assegna a il valore di x

Y > max

4. Se vai a 5. altrimenti a 6.

max

5. Assegna a il valore di y

max

6. Visualizza

7. Fine Venerdì 18 Settembre 2020

Visualizzare il massimo tra n interi acquisti da tastiera. Se ho un grosso problema, posso dividerlo

in sottoproblemi, dandoli per assodati. Prima creo un’algoritmo per il problema grosso e quando,

vado a risolvere le varie parti, creo i sottoproblemi. Questa tecnica di progettazione dell’algoritmo

top-down. bottom-up.

si chiama Se seguo l’ordine dal sottoproblema al problema si chiama

inizio

←

1. Acquisisci n n

x ←

2. Acquisisci intero x max ← x

3. Assegna a max il valore di x

i i ← 1

4. Assegna ad il valore di 1

i < n i < n

5. Se vai a 6. altrimenti a 10. V

x ←

6. Acquisisci x max ← max(max , x)

7. Assegna a max il massimo tra max ed x

i i ← i +1

8. Incrementa di una unità

9. Vai a 5. ←

10. Visualizza max max

11. ne

Termina Pagina 9

fi

Martina Contestabile Ingegneria Informatica Comune A-L, A.A. 2020/21

Uno schema a blocchi si dice strutturato se ha schema di inizio, ne e un blocco strutturato

composto, che può essere una struttura di controllo (quindi selezione, controllo, ripetizione), un

blocco funzionale semplice o un blocco nullo.

Il blocco strutturato composto (BSC) è una de nizione ricorsiva.

Struttura di controllo:

• Sequenza (comandi uno di seguito all’altro, operazioni a cascata).

• Selezione a due vie (due operazioni da svolgere in alternativa).

• Ciclo a condizione iniziale (si resta nel ciclo nché la condizione rimane vera). Il

ciclo a condizione iniziale deve necessariamente etichettato con V, quando si esce

È LA CONDIZIONE DI TERMINAZIONE);

dal ciclo l’etichetta deve essere F (NON

se è sempre vera, il ciclo è in nito, perciò il corpo del ciclo deve fare in modo da

rendere ad un certo punto la condizione falsa. Il controllo per l’arresto

dell’iterazione si trova prima delle istruzioni da ripetere.

Blocco funzionale semplice (la circostanza determina la condizione):

• Blocco di elaborazione.

• Blocco I/O.

• Blocco sottoprogramma.

Blocco nullo.

Schema a blocchi non strutturato:

In questo caso è stato su ciente duplicare un’istruzione.

Il linguaggio degli schemi a blocchi è talmente espressivo da poter esprimere qualsiasi algoritmo.

Potenza computazionale: SBS ammette almeno un algoritmo per ogni problema solubile.

Potenza espressiva: SBS ammette, permette di rappresentare, ogni possibile algoritmo per ogni

problema solubile.

Due schemi a blocchi sono debolmente equivalenti se danno stessi risultati per ogni input

(=risolvono lo stesso problema). Pagina 10

ffi fi fi fi fi

Martina Contestabile Ingegneria Informatica Comune A-L, A.A. 2020/21

Due schemi a blocchi sono fortemente equivalenti se danno le stesse sequenze di computazione

per ogni input For te → Debole

Debole For te

non implica

Teorema di Boem-Jacopini: per ogni SB non strutturato esiste uno SBS debolmente equivalente

(ottenibile attraverso trasformazione funzionale)

SBS permette di risolvere ogni problema solubile (funzionalmente parlando, è potente tanto

quanto SB).

SBS non permette di rapprese ogni possibile

algoritmo (dal punto di vista algoritmico, SBS

è meno potente di SB).

In un caso il calcolatore svolgerà una

funzione logica, nel caso a destra una

disgiunzione logica!

Ci sono costrutti aggiuntivi per risolvere algoritmi in

maniera più sintetica e compatta:

• Ciclo a condizione nale: iterazione per

falso, se il controllo per l’arresto

dell’i