1A.A. 2020/2021Docente: A. Saetti Elementi di Informatica e Programmazione – Università di Brescia
Elementi di Informatica e Programmazione- Dispensa I –ALGORITMI
Alessandro Saetti(email: [email protected])
Università degli Studi di BresciaA.A. 2020/2021
2A.A. 2020/2021Docente: A. Saetti Elementi di Informatica e Programmazione – Università di Brescia
Introduzione al modulo didattico“Elementi di Informatica e Programmazione”
• Docente: Alessandro Saetti ([email protected])• Esercitatori:
– Marco Sechi ([email protected],[email protected])– Andrea Bonisoli ([email protected])– Fabio Belleri ([email protected])
• Orario:– Lun: 14:30-16:30 in M1 (riserva MTA)– Gio: 11:30-13:30 in M1 (riserva MTB)– Ven: 13:30-15:30 in M1 (riserva MTA, MTB)
• Tutoraggio (via telematica)• Ricevimento:
– Mer: 16:30-17:30 (via telematica)– Assistenza tramite email: [email protected], [email protected]
• Sito web: http://chronus.ing.unibs.it/EIP/ oppurehttp://didattica-saetti.unibs.it/didattica/EIP/
3A.A. 2020/2021
Introduzione al modulo didattico
Obiettivi del corso
• Il corso, di natura introduttiva, ha lo scopo di fornire agli allievi i fondamenti della cultura informatica.
• Il corso offre una prima introduzione alla programmazione mediante l'utilizzo del linguaggio C. Vengono approfondite le nozioni fondamentali relative alla struttura e al progetto di programmi.
Docente: A. Saetti Elementi di Informatica e Programmazione – Università di Brescia
4A.A. 2020/2021
L’importanza di saper
programmare
Docente: A. Saetti Elementi di Informatica e Programmazione – Università di Brescia
5A.A. 2020/2021
L’importanza di sapere
programmare in questo secolo!
Docente: A. Saetti Elementi di Informatica e Programmazione – Università di Brescia
6A.A. 2020/2021
Linguaggi più popolari
Docente: A. Saetti Elementi di Informatica e Programmazione – Università di Brescia
7A.A. 2020/2021
Introduzione al modulo didattico:
Il materiale didattico
• D. Sciuto, G. Buonanno, L. Mari Introduzione ai Sistemi Informativi (quinta edizione), McGraw-Hill, 2014
• G. Guida, M. Giacomin Fondamenti di Informatica, FrancoAngeli, 2013
• Kim N. King Programmazione in C, Apogeo, 2009
Oppure
• A. Kelley, Ira Pohl C Didattica e Programmazione, Pearson, 2004
Docente: A. Saetti Elementi di Informatica e Programmazione – Università di Brescia
8A.A. 2020/2021
Introduzione al modulo didattico:
L'esame
• L'esame consiste in
1. Prova scritta su cultura informatica2. Prova scritta su programmazione
• La prova 2 è corretta solo se la prova 1 è superata
• La prova 2 può essere sostenuta anche successivamente
alla prova 1
• Il voto della prova 1 è annullato se lo studente fallisce
due volte la prova 2
• OPPURE prova in itinere
Docente: A. Saetti Elementi di Informatica e Programmazione – Università di Brescia
9A.A. 2020/2021Docente: A. Saetti Elementi di Informatica e Programmazione – Università di Brescia
I Problemi e la loro Soluzione
Quanto vale la radice quadrata intera Y di un intero positivo X ?
ProblemaVariabile di ingresso
Variabile di uscita
IstanzaQuanto vale la radice quadrata intera Y di 49?
Dati = N (numeri naturali)Risultati = R (numeri reali)
Soluzione dell'istanza = 7
Classe di domande omogenee
10A.A. 2020/2021Docente: A. Saetti Elementi di Informatica e Programmazione – Università di Brescia
Risoluzione di un Problema
Soggetto 2
�oppure
Soggetto 1
�Problema
AnalisiSoluzione: ALGORITMO
Soluzione descrittaDescrizione
Interpretazione descrizione
Attuazione soluzione
Descrizione interpretata
Soluzione
Identificazione
Esigenze
11A.A. 2020/2021
Il Concetto di Algoritmo
• Metodo, procedura o ricetta generale che specifica
come produrre una soluzione per ogni possibile
istanza del problema
• Specificato mediante una sequenza di istruzioni
elementari
• Risolvere un problema corrisponde a risolvere
un'opportuna successione di problemi più semplici
è SCOMPOSIZIONE IN SOTTO-PROBLEMI
Docente: A. Saetti Elementi di Informatica e Programmazione – Università di Brescia
12A.A. 2020/2021Docente: A. Saetti Elementi di Informatica e Programmazione – Università di Brescia
Il Calcolatore come Esecutore
(una prima definizione)
CALCOLATORE
Soluzione di un problema (programma - descrizione di un algoritmo -)
Dati iniziali(assegnati avariabili di input)
Risultati dell'esecuzione in corrispondenza dei dati iniziali(assegnati a variabili di output)
13A.A. 2020/2021Docente: A. Saetti Elementi di Informatica e Programmazione – Università di Brescia
Elementi Linguistici dell’Esecutore
1. Il linguaggio che è in grado di interpretare
2. L'insieme delle azioni che è in grado di compiere
3. L'insieme delle regole che a ogni frase del linguaggio
associano le relative azioni da compiere
14A.A. 2020/2021Docente: A. Saetti Elementi di Informatica e Programmazione – Università di Brescia
Computazione: definizioni• 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 istruzioniAlgoritmo = concetto statico Processo= concetto dinamico
15A.A. 2020/2021
Esempio
1. assegna a Y il valore 12. se Y^2 <= X allora vai al passo 3 altrimenti vai al passo 53. incrementa Y di 1 4. vai al passo 25. decrementa Y di 16. fine
Ø Le istruzioni di un algoritmo sono eseguite nello stesso ordine in cui sono scritte a meno di istruzioni di controllo
Docente: A. Saetti Elementi di Informatica e Programmazione – Università di Brescia
16A.A. 2020/2021Docente: A. Saetti Elementi di Informatica e Programmazione – Università di Brescia
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• Determinismo: per qualunque dato di ingresso, a ogni passo
della computazione, esiste al più un passo successivo.• Correttezza: calcola correttamente la funzione rappresentata• Efficienza: perviene alla soluzione del compito impiegando una
certa quantità di risorse fisiche• Terminazione: l'esecuzione termina in un numero finito di
passi di computazione
17A.A. 2020/2021Docente: A. Saetti Elementi di Informatica e Programmazione – Università di Brescia
Algoritmo = Variabili + Istruzioni
Dati iniziali Dati finali (soluzione)
ALGORITMO
variabili Istruzioni che operano sulle variabili
18A.A. 2020/2021Docente: A. Saetti Elementi di Informatica e Programmazione – Università di Brescia
Variabili
• Hanno un nome per identificare univocamente la variabile
• Hanno una locazione di memoria per conservare il dato che la variabile memorizza
• Gli può essere assegnato un valore
• Possono comparire in istruzioni di assegnamento ed espressioni
• Classificate in base a visibilità da parte dell’utente, variabilità, struttura, origine, visibilità nel codice, visibilità nel flusso di esecuzione
19A.A. 2020/2021
Istruzioni di Assegnamento
Docente: A. Saetti Elementi di Informatica e Programmazione – Università di Brescia
y ¬ x;
x ¬ y;
7 9
x y
7 9
9 9
9 9
9 9
… … …
… … …
x y tempo
t1
t0
t3
t2
t4
y ¬ tmp;
x ¬ y;
7 9
x y
7 9
9 9
9 9
9 7
… … …
… … …
x y
??
tmp
7
7
7
7
tmp
tmp ¬ x; 7 9
7 9
7
7
tempo
t1
t0
t3
t2
t4
t6
t5
20A.A. 2020/2021Docente: A. Saetti Elementi di Informatica e Programmazione – Università di Brescia
Istruzioni Aritmetico-LogicheEspressioni aritmetiche
… sono formate da:
• Operandi: variabili, costanti, espressioni aritmetiche
• Operatori: somma (+), addizione (-), moltiplicazione (*), divisione intera (/), resto (mod)
• Semantica: quella usuale dell’aritmetica
21A.A. 2020/2021Docente: A. Saetti Elementi di Informatica e Programmazione – Università di Brescia
Istruzioni Aritmetico-LogicheEspressioni relazionali
… sono formate da:
• Operandi: variabili, costanti, espressioni aritmetiche
• Operatori: operatori relazionali di uguaglianza (==), diversità (!=), minoranza (<) e maggioranza (>) fra numeri
• Semantica: quella delle disequazioni fra numeri
22A.A. 2020/2021Docente: A. Saetti Elementi di Informatica e Programmazione – Università di Brescia
Istruzioni Aritmetico-LogicheEspressioni logiche e predicati logici
… sono formate 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)
23A.A. 2020/2021
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
Docente: A. Saetti Elementi di Informatica e Programmazione – Università di Brescia
24A.A. 2020/2021
Algebra di Boole
Operatori
Docente: A. Saetti Elementi di Informatica e Programmazione – Università di Brescia
A not A
0 1
1 0
A B A or B
0 0 0
0 1 1
1 0 1
1 1 1
A B A xor B
0 0 0
0 1 1
1 0 1
1 1 0
A B A ↔ B
0 0 1
0 1 0
1 0 0
1 1 1
A B A nor B
0 0 1
0 1 0
1 0 0
1 1 0
A B A nand B
0 0 1
0 1 1
1 0 1
1 1 0
A B A and B
0 0 0
0 1 0
1 0 0
1 1 1
A B A → B
0 0 1
0 1 1
1 0 0
1 1 1
25A.A. 2020/2021Docente: A. Saetti Elementi di Informatica e Programmazione – Università di Brescia
Schemi a BlocchiLa simbologia comunemente utilizzata
inizio I/O fine
elaborazione selezione a 2 vie
condsì no
sottoprogramma
26A.A. 2020/2021Docente: A. Saetti Elementi di Informatica e Programmazione – Università di Brescia
Schemi a Blocchi Strutturati
• Esistono dei vincoli da rispettare per progettare buoni programmi
BSC
Inizio
Fine
BSC – Blocco Strutturato Composto
27A.A. 2020/2021Docente: A. Saetti Elementi di Informatica e Programmazione – Università di Brescia
BSC – Blocco Strutturato CompostoSequenza e Selezione
sequenza
Selezione a 2 vie
condV F
BSC
BSCBSC BSC
28A.A. 2020/2021Docente: A. Saetti Elementi di Informatica e Programmazione – Università di Brescia
BSC – Blocco Strutturato CompostoSelezione Semplice
condF
condV
F VBSC BSC
Si usa un blocco funzionale nullo
29A.A. 2020/2021Docente: A. Saetti Elementi di Informatica e Programmazione – Università di Brescia
BSC – Blocco Strutturato CompostoCiclo a condizione iniziale
condF
V
Si resta nel ciclo finchè la condizione rimane vera
BSCCORPO del
CICLO
30A.A. 2020/2021Docente: A. Saetti Elementi di Informatica e Programmazione – Università di Brescia
BSC – Blocco Strutturato Composto
Blocco funzionale semplice
……… ………………
31A.A. 2020/2021Docente: A. Saetti Elementi di Informatica e Programmazione – Università di Brescia
SB generici e SBS
• 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
Ø Dal punto di vista funzionale SBS è potente quanto SB!
• SBS non permette di rappresentare ogni possibile
algoritmo
Ø Dal punto di vista algoritmico SBS è meno potente di SB!
32A.A. 2020/2021Docente: A. Saetti Elementi di Informatica e Programmazione – Università di Brescia
Altre Strutture di Controllo Tipiche Ciclo a condizione finale
condV
F
BSC
BSC
cond
BSC
V
F
33A.A. 2020/2021Docente: A. Saetti Elementi di Informatica e Programmazione – Università di Brescia
Altre Strutture di Controllo Tipiche Struttura Condizionale Multipla
V
BSC1
exp==v1
V
BSC2
exp==v2
V
BSC3
exp==v3
F
F
F
BSC4
v1BSC1
exp?
v2
v3
BSC2
BSC3
Altr.BSC4
34A.A. 2020/2021
Altre Strutture di Controllo Tipiche Ciclo controllato da contatore
Docente: A. Saetti Elementi di Informatica e Programmazione – Università di Brescia
F
V
p1
BSC
B
A
CORPO delCICLO
Assegnamentodi una variabile
contatore
Modificadi una variabile
contatore
Top Related