Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Valeria Vittorini » 11.Programmazione , Programmazione Strutturata, Istruzioni Strutturate


Sommario

  • Strutture di controllo
  • Programmazione strutturata
  • Sequenza di istruzioni
  • Strutture di selezione
    • If-then
    • If-then-else
    • Selezione a più vie (case)
  • Strutture iterative
    • A condizione finale
    • A condizione iniziale
    • Ciclo a conteggio

Strutture di controllo

  • In un algoritmo sono normalmente presenti passi decisionali che servono a controllare la particolare sequenza dinamica che deve essere eseguita dall’esecutore per risolvere uno specifico caso di ingresso.
  • Si può dimostrare che per descrivere qualunque algoritmo sono sufficienti solo due tipologie di passi decisionali a cui corrispondono nel linguaggio di programmazione due tipi di istruzioni: l’istruzione di selezione e l’istruzione iterativa.

Tassonomia delle istruzioni

  • Istruzioni semplici
    • Rappresentano azioni elementari del programma.
  • Istruzioni strutturate
    • Sono composte da azioni organizzate in strutture.
    • Le azioni componenti possono essere istruzioni semplici o istruzioni a loro volta strutturate.

Blocco di istruzioni

NOTE

  • Dopo un blocco non occorre il punto e virgola (esso termina le istruzioni semplici, non separa istruzioni).
  • Il campo d’azione delle che compaiono entro il blocco è il blocco stesso.
  • I blocchi possono essere innestati.

Programmazione strutturata

Si parla di programmazione strutturata se si utilizzano solo le seguenti strutture per alterare il flusso di controllo [Dijkstra, 1969]:

  • Sequenza
  • Selezione
  • Iterazione

In questo modo è possibile scrivere un programma come una sequenza di istruzioni o blocchi di istruzioni più o meno complesse, in modo che ciascun blocco di istruzioni preveda un solo ingresso e una sola uscita.

Risorse in rete:

Archivio sulla vita e le opere di Edsger Wybe Dijkstra sul sito dell’Università di Austin, Texas

Letture:

Il testo “Structured Programming” del 1979! (In Inglese)

Equivalenza funzionale di programmi

Due programmi si dicono funzionalmente equivalenti se, sottoposti ad un qualsiasi insieme di dati d’ingresso, entrambi terminano producendo gli stessi dati d’uscita o entrambi non terminano.

Insiemi funzionalmente completi

Un insieme S di istruzioni strutturate è funzionalmente completo se, per ogni programma P in un linguaggio L, ne esiste uno funzionalmente equivalente che usa solo le istruzioni strutturate di S.

Teorema di Böhm -Jacopini

L’insieme S costituito dalle strutture

  • Sequenza (composizione)
  • Selezione
  • Iterazione

È un insieme funzionalmente completo.

In altre parole:

L’uso delle strutture di controllo ci consente di

  • Scrivere programmi strutturati, facilmente leggibili e modificabili.
  • Evitare l’uso della programmazione a salti (go to).

Risorse in rete:

La Homepage di Corrado Böhm

Diagramma di flusso

Il comportamento delle istruzioni per il controllo della sequenza dinamica può essere descritto graficamente attraverso un diagramma di flusso:

  • Le condizioni sono rappresentate da rombi.
  • Le istruzioni sono rappresentate da rettangoli.
  • Le linee orientate collegano gli elementi grafici per indicare l’ordine seguito dall’esecutore.

Sequenza di istruzioni

  • Permette di eseguire le istruzioni secondo l’ordine sequenziale in cui sono scritte.
  • È composta da istruzioni semplici e/o strutturate.
  • È individuata da un delimitatore di inizio e da uno di fine sequenza (blocco).
  • Le istruzioni componenti vengono eseguite come se si trattasse di un’istruzione unica.

Esempio:

{
a=3;
a=a+b;
}

Struttura di selezione: if-then-else

Q, S1, S2 rappresentano sequenze di istruzioni, R rappresenta una condizione logica da valutare.

L’esecuzione di un’istruzione di selezione di tipo if-then-else produce nell’ordine:

  • La valutazione della condizione.
  • L’esecuzione della parte-then se il valore logico della condizione è “vero” oppure l’esecuzione della parte-else se il valore logico della condizione è “falso”.

Struttura di selezione: if-then

Q e S rappresentano sequenze di istruzioni. R rappresenta una condizione logica da valutare.

In questo caso la parte “else” è vuota.

Istruzione vuota: non produce alcun effetto.


if-then-else annidati

La parte-then e la parte-else possono a loro volta contenere istruzioni di selezione dando luogo a scelte in cascata che permettono di descrivere algoritmi che devono operare una scelta tra più di due alternative.

Una volta che una condizione risulta verificata, le rimanenti istruzioni sono saltate.

Indentazioni profonde non sono molto usate in pratica.


Struttura di selezione: case

case e
val1: S1;
val2: S2;
…;
valn: Sn
end

L’esecuzione di un’istruzione di tipo case produce nell’ordine:

  • La valutazione della espressione.
  • L’esecuzione della sequenza di istruzioni etichettata mediante il valore assunto dall’espressione.


Osservazione

Nella struttura case l’espressione che viene valutata deve assumere valori in un insieme discreto.

Una selezione multipla si può implementare anche mediante più costrutti if-then in sequenza o con più costrutti if-then-else innestati (ma le tre figure non sono equivalenti).

Struttura di iterazione: ciclo a condizione iniziale

S è detta “corpo” dell’istruzione iterativa

  • L’esecuzione di un’istruzione di iterativa a condizione iniziale di tipo while-do produce nell’ordine:
    • La valutazione della condizione.
    • Il termine dell’istruzione se il valore logico calcolato è “falso” oppure l’esecuzione del corpo e la ripetizione del punto 1 se il valore logico calcolato è “vero”.


Struttura di iterazione: ciclo a condizione finale

  • L’esecuzione di un’istruzione di iterativa a condizione finale di tipo repeat –until produce nell’ordine:
    • L’esecuzione del corpo.
    • La valutazione della condizione.
    • Il termine dell’istruzione se il valore logico calcolato è vero oppure la ripetizione dei punti 1 e 2 se il valore logico calcolato è falso.


Struttura di iterazione: ciclo a conteggio

  • c è una variabile che rappresenta il “contatore”ed assume valori in un intervallo discreto.
    • vi è il suo valore iniziale;
    • vf il suo valore finale;
    • succ(c) è una funzione che fornisce il valore.

  • Successivo di c in funzione del passo k.
  • Il passo k può anche essere negativo.

E’ necessario specificare:

  • L’inizinializzazione del contatore.
  • L’incremento del contatore.
  • Il controllo di fine ciclo.

Prossima lezione

Esempi

  • Semplici programmi con l’utilizzo di:
    • Istruzioni semplici.
    • Istruzioni strutturate.

I materiali di supporto della lezione

C. Boehm and G. Jacopini. Flow diagrams, turing machines and languages with only two formation rules. Communications of the ACM, pages 366–371, May 1966

Fadini, C. Savy, Fondamenti di Informatica I, Napoli, Liguori Ed., 1997, Parte 2, cap. V.

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion