Università degli Studi di Brescia A.A. 2020/2021 · 2020. 9. 11. · A.A. 2020/2021 3 Introduzione...

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


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


5A.A. 2020/2021

L’importanza di sapere

programmare in questo secolo!


6A.A. 2020/2021

Linguaggi più popolari


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


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



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


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



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)


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


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



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


Algoritmo = Variabili + Istruzioni

Dati iniziali Dati finali (soluzione)

ALGORITMO

variabili Istruzioni che operano sulle variabili


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


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


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


Istruzioni Aritmetico-LogicheEspressioni relazionali


• Operandi: variabili, costanti, espressioni aritmetiche

• Operatori: operatori relazionali di uguaglianza (==), diversità (!=), minoranza (<) e maggioranza (>) fra numeri

• Semantica: quella delle disequazioni fra numeri


Istruzioni Aritmetico-LogicheEspressioni logiche e predicati logici


• 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


24A.A. 2020/2021

Algebra di Boole

Operatori


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


Schemi a BlocchiLa simbologia comunemente utilizzata

inizio I/O fine

elaborazione selezione a 2 vie

condsì no

sottoprogramma


Schemi a Blocchi Strutturati

• Esistono dei vincoli da rispettare per progettare buoni programmi

BSC

Inizio

Fine

BSC – Blocco Strutturato Composto


BSC – Blocco Strutturato CompostoSequenza e Selezione

sequenza

Selezione a 2 vie

condV F

BSC

BSCBSC BSC


BSC – Blocco Strutturato CompostoSelezione Semplice

condF

condV

F VBSC BSC

Si usa un blocco funzionale nullo


BSC – Blocco Strutturato CompostoCiclo a condizione iniziale

condF

V

Si resta nel ciclo finchè la condizione rimane vera

BSCCORPO del

CICLO


BSC – Blocco Strutturato Composto

Blocco funzionale semplice

……… ………………


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!


Altre Strutture di Controllo Tipiche Ciclo a condizione finale

condV

F

BSC

BSC

cond

BSC

V

F


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


F

V

p1

BSC

B

A

CORPO delCICLO

Assegnamentodi una variabile

contatore

Modificadi una variabile

contatore

Università degli Studi di Brescia A.A. 2020/2021 · 2020. 9. 11. · A.A. 2020/2021 3 Introduzione...

Documents

Transcript of Università degli Studi di Brescia A.A. 2020/2021 · 2020. 9. 11. · A.A. 2020/2021 3 Introduzione...