IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che...
-
Upload
gasparo-bartolini -
Category
Documents
-
view
226 -
download
2
Transcript of IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che...
![Page 1: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/1.jpg)
IL PROBLEMA DEL PROGETTO
![Page 2: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/2.jpg)
IL PROBLEMA DEL PROGETTO
Quali metodologie e tecniche usare?
Come arrivare a intuire l’algoritmo che ci serve?
Come si costruisce la soluzione a un problema?
![Page 3: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/3.jpg)
IL PROBLEMA DEL PROGETTO
Due dimensioni progettuali: Programmazione in piccolo
(in-the-small) Programmazione in grande
(in-the-large)
Principi cardine: procedere per livelli di astrazione garantire al programma strutturazione e
modularità
![Page 4: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/4.jpg)
IL PROBLEMA DEL PROGETTO
La descrizione del problema, in genere, non indica direttamente il modo per ottenere il risultato voluto
Occorrono metodologie per affrontare il problema del
progetto in modo sistematico per superare la “sindrome del foglio
bianco”
![Page 5: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/5.jpg)
METODOLOGIE
![Page 6: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/6.jpg)
METODOLOGIE
Procede per decomposizione del problema in sotto-problemi, per passi di raffinamento successivi
![Page 7: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/7.jpg)
METODOLOGIE
Procede per composizione di componenti e funziona-lità elementari, fino alla sintesi dell’intero algoritmo (“dal dettaglio all’astratto”)
![Page 8: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/8.jpg)
METODOLOGIA TOP-DOWN
• Si parte dal problema e dalle proprietà note sul dominio dei dati
• Si disgrega il problema in sottoproblemi• Si affronta ciascun sottoproblema (con la
stessa metodologia) fino a raggiungere problemi risolubili con le mosse elementari
![Page 9: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/9.jpg)
IL PROBLEMA DEL PROGETTO
Dunque, dato un problema...
iniziare subito a scrivere il programma..?
NO !• così si scrivono a fatica programmi di dieci
righe• spesso sono errati, e non si sa perché• nessuno capisce cosa è stato fatto
(dopo un po’, nemmeno l’autore...)
![Page 10: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/10.jpg)
IL PROBLEMA DEL PROGETTO
Dato un problema...
iniziare subito a scrivere il programma..?
NO !• nessuno sa se questa soluzione sia la
migliore o se ce ne fossero altre• se domani occorre modificare qualcosa,
non si sa dove mettere le mani• se si deve cambiare linguaggio…
meglio non pensarci!
![Page 11: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/11.jpg)
IL PROBLEMA DEL PROGETTO
Quando rischia di accadere tutto ciò?
• quando la specifica della soluzione coincide con la fase di codifica
• che invece sono, concettualmente, due momenti distinti
• e tali devono restare anche in pratica!
![Page 12: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/12.jpg)
UN ESEMPIO
Problema:
“Data una temperatura espressa in gradi Celsius, calcolare il corrispondente valore espresso in gradi Fahrenheit”
Approccio:• si parte dal problema e dalle proprietà
note sul dominio dei dati
![Page 13: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/13.jpg)
UN ESEMPIO
Problema:
“Data una temperatura espressa in gradi Celsius, calcolare il corrispondente valore espresso in gradi Fahrenheit”
Specifica della soluzione:
Relazioni tra grandezze esistenti nello specifico dominio applicativo:
c * 9/5 = f - 32
c = (f - 32) * 5/9 oppure f = 32 + c * 9/5
![Page 14: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/14.jpg)
UN ESEMPIO
L’Algoritmo corrispondente:• Dato c• calcolare f sfruttando la relazione
f = 32 + c * 9/5
SOLO A QUESTO PUNTO• si sceglie un linguaggio• si codifica l’algoritmo in tale linguaggio
![Page 15: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/15.jpg)
LINGUAGGI DI PROGRAMMAZIONE
• Un linguaggio di programmazione ha due componenti ortogonali
• il linguaggio di Computazione • il linguaggio di Coordinazione
Linguaggi di computazione
Linguaggi di
coordinazione
Un particolare linguaggio di programmazione
![Page 16: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/16.jpg)
LINGUAGGI DI COMPUTAZIONE
Il “potere espressivo” di un linguaggio ècaratterizzato da:
quali tipi di dati consente di rappresentare (direttamente o tramite definizione dell’utente)
quali istruzioni di controllo mette a disposizione (quali operazioni e in quale ordine di esecuzione)
PROGRAMMA = DATI + CONTROLLO
![Page 17: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/17.jpg)
IL LINGUAGGIO C
Il “Linguaggio di Programmazione” C è costituito da• un linguaggio di computazione (il C vero e proprio)
• un linguaggio di coordinazione fornito come “allegato”, sotto forma di librerie standard
![Page 18: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/18.jpg)
IL LINGUAGGIO C
UN PO’ DI STORIA
definito nel 1972 (AT&T Bell Labs) per sostituire l’assembler
prima definizione precisa: Kernigham & Ritchie (1978)
prima definizione ufficiale: ANSI (1983)
![Page 19: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/19.jpg)
IL LINGUAGGIO C
CARATTERISTICHE
linguaggio sequenziale, imperativo, strutturato a blocchi
usabile anche come linguaggio di sistema adatto a software di base, sistemi operativi,
compilatori, ecc.
portabile, efficiente, sintetico ma a volte poco leggibile...
![Page 20: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/20.jpg)
IL LINGUAGGIO C
Basato su pochi concetti elementari
dati (tipi primitivi, tipi di dato)
espressioni
dichiarazioni / definizioni
funzioni
istruzioni / blocchi
![Page 21: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/21.jpg)
DATI• Un elaboratore è un manipolatore di
simboli (segni)
• L'architettura fisica di ogni elaboratore è intrinsecamente capace di trattare vari domini di dati, detti tipi primitivi– dominio dei numeri naturali e interi– dominio dei numeri reali
(con qualche approssimazione)– dominio dei caratteri– dominio delle stringhe di caratteri
![Page 22: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/22.jpg)
TIPI DI DATO
Il concetto di tipo di dato viene introdottoper raggiungere due obiettivi:
• esprimere in modo sintetico – un insieme di valori– la loro rappresentazione in memoria, e– un insieme di operazioni ammissibili
• permettere di effettuare controlli statici (al momento della compilazione) sulla correttezza del programma.
![Page 23: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/23.jpg)
TIPI DI DATO PRIMITIVI IN C
• caratteri– char caratteri ASCII
• interi con segno– short (int) -32768 ... 32767– int ???????– long (int) -2147483648 .... 2147483647
• naturali (interi senza segno)– unsigned short (int) 0 ...
65535– unsigned (int) ???????– unsigned long (int) 0 ...
4294967295
![Page 24: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/24.jpg)
• caratteri– char caratteri ASCII
• interi con segno– short (int) -32768 ... 32767– int ???????– long (int) -2147483648 .... 2147483647
• naturali (interi senza segno)– unsigned short (int) 0 ...
65535– unsigned (int) ???????– unsigned long (int) 0 ...
4294967295
TIPI DI DATO PRIMITIVI IN C
ATTENZIONE: la dimensione di int non è fissa,
dipende dal compilatore considerato. Unica certezza: short < int < long
![Page 25: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/25.jpg)
• caratteri– char caratteri ASCII
• interi con segno– short (int) -32768 ... 32767– int ???????– long (int) -2147483648 .... 2147483647
• naturali (interi senza segno)– unsigned short (int) 0 ...
65535– unsigned (int) ???????– unsigned long (int) 0 ...
4294967295
TIPI DI DATO PRIMITIVI IN C
… e lo stesso vale per l’unsigned int
![Page 26: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/26.jpg)
TIPI DI DATO PRIMITIVI IN C
• reali– float singola precisione (32 bit)– double doppia precisione (64
bit)
• boolean– non esistono in C come tipo a sé stante– si usano gli interi:
• zero indica FALSO• ogni altro valore indica VERO
– convenzione: suggerito utilizzare uno per VERO
![Page 27: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/27.jpg)
COSTANTI DI TIPI PRIMITIVI• interi (in varie basi di rappresentazione)
• reali– in doppia precisione
24.0 2.4E1 240.0E-1 – in singola precisione
24.0F 2.4E1F 240.0E-1F
base 2 byte 4 byte
decimale 12 70000, 12Lottale 014 0210560esadecimale 0xFF 0x11170
![Page 28: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/28.jpg)
COSTANTI DI TIPI PRIMITIVI
• caratteri– singolo carattere racchiuso fra apici
'A' 'C' '6'– caratteri speciali:
'\n' '\t' '\'' '\\' '\"'– caratteri indicati tramite la loro codifica ASCII:
'\nnn', '\0xhhh'
dove nnn = numero ottale, hhh = numero esadecimale
'\041' '\0' '\0x31'
![Page 29: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/29.jpg)
STRINGHE
• Una stringa è una collezione di caratteri delimitata da virgolette
"ciao" "Hello\n"
• In C le stringhe sono semplici sequenze di caratteri di cui l’ultimo, sempre presente in modo implicito, è '\0'
"ciao" = {'c', 'i', 'a', 'o', '\0'}
![Page 30: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/30.jpg)
ESPRESSIONI
Il C è un linguaggio basato su espressioni
Una espressione è una notazione che denota un valore mediante un processo di valutazione
Una espressione può essere sempli-ce o composta (tramite aggregazio-ne di altre espressioni)
![Page 31: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/31.jpg)
ESPRESSIONI SEMPLICI
Quali espressioni elementari?
costanti– ‘A’ 23.4 -3 “ciao” ....
simboli di variabile– x pippo pigreco ….
simboli di funzione– f(x)– concat(“alfa”,”beta”)– ...
![Page 32: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/32.jpg)
OPERATORI ED ESPRESSIONI COMPOSTE
• Ogni linguaggio introduce un insieme di operatori
• che permettono di aggregare altre espressioni (operandi)
• per formare espressioni composte
• con riferimento a diversi domini / tipi di dato (numeri, testi, ecc.)
![Page 33: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/33.jpg)
ESPRESSIONI COMPOSTE
Esempi2 + f(x)
4 * 8 - 3 % 2 + arcsin(0.5)
strlen(concat(“alfa”,”beta”))
a && (b || c)
...
![Page 34: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/34.jpg)
CLASSIFICAZIONE DEGLI OPERATORI
• Due criteri di classificazione:– in base al tipo degli operandi– in base al numero degli operandi
in base al tipo degli operandi in base al numero di operandi aritmetici relazionali logici condizionali ...
unari binari ternari ...
![Page 35: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/35.jpg)
ESPRESSIONI E OPERATORI ARITMETICI
operazione operatore Cinversione di segno unario -somma binario +differenza binario -moltiplicazione binario *divisione fra interi binario /divisione fra reali binario /modulo (fra interi) binario %
NB: la divisione a/b è fra interi se sia a che b sono interi,è fra reali in tutti gli altri casi
![Page 36: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/36.jpg)
ESPRESSIONI E OPERATORI RELAZIONALI
relazione Cuguaglianza ==diversità !=maggiore di >minore di <maggiore o uguale a >=minore o uguale a <=
Sono tutti operatori binari:
![Page 37: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/37.jpg)
ESPRESSIONI E OPERATORI RELAZIONALI
Attenzione:
non esistendo il tipo boolean,in C le espressioni relazionali denotano un valore intero– 0 denota falso
(condizione non verificata)– 1 denota vero
(condizione verificata)
![Page 38: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/38.jpg)
ESPRESSIONI E OPERATORI RELAZIONALI
Quindi,– sono possibili, in astratto,
espressioni miste come:
(n != 0) = = n/* Vero se n vale 1 o 0 */
– orrende e da evitare!
![Page 39: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/39.jpg)
ESPRESSIONI E OPERATORI LOGICI
– Anche le espressioni logiche denotano un valore intero
– da interpretare come vero (1) o falso (0)
connettivo logico operatore Cnot (negazione) unario !and binario &&or binario ||
![Page 40: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/40.jpg)
ESPRESSIONI E OPERATORI LOGICI
• Anche qui sono possibili espres-sioni miste, utili in casi specifici
5 && 7 0 || 33 !5• Valutazione in corto-circuito
– la valutazione dell’espressione cessa appena si è in grado di determinare il risultato
– il secondo operando è valutato solo se necessario
![Page 41: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/41.jpg)
VALUTAZIONE IN CORTO CIRCUITO - ESEMPI
– 22 || xgià vera in partenza perché 22 è vero
– 0 && xgià falsa in partenza perché 0 è falso
– a && b && cse a&&b è falso, il secondo && non viene neanche valutato
– a || b || cse a||b è vero, il secondo || non viene neanche valutato
![Page 42: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/42.jpg)
ESPRESSIONI CONDIZIONALI
Una espressione condizionale èintrodotta dall’operatore ternario
condiz ? espr1 : espr2
L’espressione denota:– o il valore denotato da espr1– o quello denotato da espr2– in base al valore della espressione condiz
![Page 43: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/43.jpg)
ESPRESSIONI CONDIZIONALI
condiz ? espr1 : espr2
• se condiz è vera, l’espressione nel suo complesso denota il valore denotato da espr1
• se condiz è falsa, l’espressio-ne nel suo complesso denota il valore denotato da espr2
![Page 44: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/44.jpg)
ESPRESSIONI CONDIZIONALI - ESEMPI
– 3 ? 10 : 20denota sempre 10 (3 è sempre vera)
– x ? 10 : 20denota 10 se x è vera (diversa da 0), oppure 20 se x è falsa (uguale a 0)
– (x>y) ? x : ydenota il maggiore fra x e y
![Page 45: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/45.jpg)
ESPRESSIONI CONCATENATE
Una espressione concatenata èintrodotta dall’operatore diconcatenazione
espr1, espr2, …, esprN• tutte le espressioni vengono
valutate (da sinistra a destra)
• l’espressione esprime il valore denotato da esprN
![Page 46: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/46.jpg)
ESPRESSIONI CONCATENATE - ESEMPI
• Supponiamo che– i valga 5 – k valga 7
• Allora l’espressione:
i + 1, k - 4
denota il valore denotato da k-4,cioè 3.
![Page 47: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/47.jpg)
OPERATORI INFISSI, PREFISSI, e POSTFISSI
• Le espressioni composte sono strutture formate da operatori applicati a uno o più operandi
• Ma.. dove posizionare l’operatore rispetto ai suoi operandi?
![Page 48: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/48.jpg)
OPERATORI INFISSI, PREFISSI, e POSTFISSI
• Tre possibili scelte: prima notazione prefissa
Esempio: + 3 4 in mezzo notazione infissa
Esempio: 3 + 4 dopo notazione postfissa
Esempio: 3 4 +
![Page 49: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/49.jpg)
OPERATORI INFISSI, PREFISSI, e POSTFISSI
• Le notazioni prefissa e postfissanon hanno problemi di priorità e/o associatività degli operatori– non c’è mai dubbio su quale operatore
vada applicato a quali operandi
• La notazione infissa richiede regole di priorità e associatività – per identificare univocamente quale
operatore sia applicato a quali operandi
![Page 50: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/50.jpg)
ESEMPI
• Notazione prefissa:
* + 4 5 6– si legge come (4 + 5) * 6– denota quindi 54
• Notazione postfissa:
4 5 6 + * – si legge come 4 * (5 + 6)– denota quindi 44
![Page 51: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/51.jpg)
PRIORITÀ DEGLI OPERATORI
• PRIORITÀ: specifica l’ordine di valutazione degli operatori quando in una espressione compaiono operatori (infissi) diversi
• Esempio: 3 + 10 * 20– si legge come 3 + (10 * 20) perché
l’operatore * è più prioritario di +
• NB: operatori diversi possono comunque avere egual priorità
![Page 52: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/52.jpg)
ASSOCIATIVITÀ DEGLI OPERATORI
• ASSOCIATIVITÀ: specifica l’ordine di valutazione degli operatori quan-do in una espressione compaiono operatori (infissi) di egual priorità
• Un operatore può quindi essere associativo a sinistra oassociativo a destra
![Page 53: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/53.jpg)
ASSOCIATIVITÀ DEGLI OPERATORI
• ASSOCIATIVITÀ: specifica l’ordine di valutazione degli operatori quan-do in una espressione compaiono operatori (infissi) di egual priorità
• Esempio: 3 - 10 + 8– si legge come (3 - 10) + 8 perché gli
operatori - e + sono equiprioritari e associativi a sinistra
![Page 54: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/54.jpg)
PRIORITÀ E ASSOCIATIVITÀ
• Priorità e associatività predefinite possono essere alterate mediante l’uso di parentesi
• Esempio: (3 + 10) * 20– denota 260 (anziché 203)
• Esempio: 30 - (10 + 8)– denota 12 (anziché 28)
![Page 55: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/55.jpg)
ORDINE DI VALUTAZIONE DEGLI OPERANDI
• Priorità e associatività
– dicono in che ordine saranno valutate le operazioni
– NON in che ordine procurarsi gli operandi!
![Page 56: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/56.jpg)
ORDINE DI VALUTAZIONE DEGLI OPERANDI
• Esempio: le due espressioni– (3 + f(x)) + g(y)– 3 + (f(x) + g(y))
• possono essere entrambe valutate – o calcolando prima f(x) e poi g(y)– o viceversa
![Page 57: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/57.jpg)
ORDINE DI VALUTAZIONE DEGLI OPERANDI
• L’ordine di valutazione degli operandi è una regola semantica:
• Il C non la precisa ambiguità!
– non c’è modo di saperlo!– le parentesi non servono a nulla (è una
regola semantica, non sintattica!)– compilatori diversi potrebbero fare scelte
diverse
![Page 58: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/58.jpg)
ORDINE DI VALUTAZIONE DEGLI OPERANDI
• Per imporre un ordine specifico, bisogna serializzare le operazioni
• Esempio: anziché– (3 + f(x)) + g(y)
scrivere1) z1 = f(x)
2) z2 = g(y)3) (3 + z1) + z2
![Page 59: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/59.jpg)
RIASSUNTO OPERATORI DEL C (1/2)
Priorità Operatore Simbolo Associatività1 (max) chiamate a
funzioneselezioni
()[] -> .
a sinistra
2 operatori unari: op. negazione op. aritmetici unari op. incr. / decr. op. indir. e deref. op. sizeof
! ~+ -++ --
& *
sizeof
a destra
3 op. moltiplicativi * / % a sinistra4 op. additivi + - a sinistra
![Page 60: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/60.jpg)
RIASSUNTO OPERATORI DEL C (2/2)
Priorità Operatore Simbolo Associatività5 op. di shift >> << a sinistra6 op. relazionali < <= > >= a sinistra7 op. uguaglianza == != a sinistra8 op. di AND bit a bit & a sinistra9 op. di XOR bit a bit ^ a sinistra
10 op. di OR bit a bit | a sinistra11 op. di AND logico && a sinistra12 op. di OR logico || a sinistra13 op. condizionale ?...: a destra14 op. assegnamento
e sue varianti
=+= -= *=/=%= &= ^=|= <<= >>=
a destra
15 (min) op. concatenazione , a sinistra
![Page 61: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/61.jpg)
GRAMMATICA DELLE ESPRESSIONI
• Associatività e priorità degli operatori sono determinate dalle regole sintat-tiche definite dalla grammatica delle espressioni.
• Regole diverse possono comportare– diversa priorità fra gli operatori– diversa associatività fra operatori
equiprioritari
![Page 62: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/62.jpg)
GRAMMATICA DELLE ESPRESSIONI
Alcune delle produzioni principali:
<espressione> ::= <termine> |<espressione> + <termine> |<espressione> - <termine>
<termine> ::= <fattore> |<termine> * <fattore> |<termine> / <fattore><termine> % <fattore>
<fattore> ::= [ - | + ] <numero> | ( <espressione> )
![Page 63: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/63.jpg)
GRAMMATICA DELLE ESPRESSIONI
La scelta di riscrivere
• <espressione> come somma algebrica di <termine>
• <termine> come prodotto o rapporto di <fattore>
impone una gerarchia fra gli operatoricorrispondenti, e dunque definisce lapriorità degli operatori (*, / più prioritari)
![Page 64: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/64.jpg)
GRAMMATICA DELLE ESPRESSIONI
Esempio
<espressione> ::= <termine> |<espressione> + <termine> |<espressione> - <termine>
<termine> ::= <fattore> |<termine> * <fattore> |<termine> / <fattore><termine> % <fattore>
<fattore> ::= [ - | + ] <numero> | ( <espressione> )
![Page 65: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/65.jpg)
GRAMMATICA DELLE ESPRESSIONI
La scelta di scrivere una grammaticaricorsiva a sinistra
rende gli operatori aritmeticiassociativi a sinistra, e dunquedefinisce la loro associatività
In questo modo otteniamo operatori che “si comportano” come quelli della aritmetica a cui siamo abituati.
![Page 66: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/66.jpg)
ALBERO SINTATTICO DELL’ESPRESSIONE 2 – 3 + 4 * (6 % ( 2 + 3 ))
+
-
2 3
*
4 %
6 +
2 3
![Page 67: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/67.jpg)
GRAMMATICHE : UN CONTROESEMPIO
Attenzione: una grammatica ricorsiva a destra
– sarebbe lecita in astratto…– ma darebbe luogo a una matematica
alquanto “inusuale”!
![Page 68: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/68.jpg)
GRAMMATICHE: UN CONTROESEMPIO
Ad esempio, qui 2 - 5 + 6 verrebbevalutata come 2 - (5 + 6)…. !!!
<espressione> ::= <termine> |<termine> + <espressione> |<termine> - <espressione>
<termine> ::= <fattore> |<fattore> * <termine> |<fattore> / <termine> |<fattore> % <termine>
<fattore> ::= [ - | + ] <numero> | ( <espressione> )
![Page 69: IL PROBLEMA DEL PROGETTO. Quali metodologie e tecniche usare? Come arrivare a intuire lalgoritmo che ci serve? Come si costruisce la soluzione a un problema?](https://reader035.fdocumenti.com/reader035/viewer/2022062701/5542eb5a497959361e8c67be/html5/thumbnails/69.jpg)
UN ULTERIORE CONTROESEMPIO
• Con regole non ricorsive, non esiste associatività• In effetti, espressioni come 3+4+5 non sono
possibili: occorrono sempre le parentesi!
<espressione> ::= <termine> |<termine> + <termine> |<termine> - <termine>
<termine> ::= <fattore> |<fattore> * <fattore> |<fattore> / <fattore><fattore> % <fattore>
<fattore> ::= [ - | + ] <numero> | ( <espressione> )