Il teorema di Böhm-Jacopini

Di: R. C.
Tramite: O2O 19/01/2018
Difficoltà:media
17

Introduzione

I sistemi di programmazione sono numerosi e, oltre ad aggiornarsi mese per mese, cambiano e spesso è necessario imparare a dialogare con più software, molto diversi fra loro. All'inizio dell'era informatica, però, questo campo era una landa libera dove vari "esploratori" hanno costruito le basi di tutto ciò che conosciamo oggi. Tra i pionieri della ricerca informatica ricordiamo due matematici italiani: Corrado Böhm e Giuseppe Jacopini. Essi spesero gran parte della loro vita nello studio della macchina di Turing e dell'architettura di Von Neumann arrivando ad enunciare, nel 1966, il famoso Teorema di Böhm-Jacopini, base dei moderni linguaggi di programmazione strutturati.

27

Occorrente

  • Conoscenze di base di fondamenti di informatica
37

Concetto di algoritmo

Prima di enunciare il suddetto teorema andiamo ad effettuare un breve excursus sul concetto di algoritmo: è detto algoritmo una sequenza di istruzioni (o passi) chiare per il simulatore, tali che, se espresse e codificate in ordine preciso, portano alla soluzione istantanea di un dato problema. Un algoritmo può essere espresso, a seconda del campo in cui ci si muove, con un linguaggio testuale (codice o linguaggio di programmazione) o con un linguaggio grafico (schemi di flusso o flow-chart). Ora che abbiamo compreso il tema che stiamo trattando procediamo con il teorema in se.

47

Enunciato

Il teorema di Böhm-Jacopini afferma che qualsiasi algoritmo, in qualsiasi linguaggio, può essere implementato in codice di programmazione utilizzando tre sole strutture di controllo: sequenza, selezione e iterazione del ciclo. Per sequenza si intende la normale scrittura dell'elenco di informazioni e ordini, così come è stata pensata ed espressa dal programmatore. È fondamentale a garantirne il corretto utilizzo che le informazioni siano nell'ordine corretto. La selezione è, invece, una condizione che dividerà il flusso in due direzioni a seconda di un data risposta ad una domanda. La suddetta condizione è molto spesso una variabile booleana e si caratterizza, nella maggior parte dei casi, di comandi del tipo "if" (se) o "or" (oppure). Nei sistemi più moderni può essere molto più complicata e permette la scelta fra tre o più vie. L'ultima struttura di controllo di cui necessita un algoritmo per funzionare e l'iterazione, la ripetizione di una certa operazione fino a quando una delle condizioni non cambia di stato. Un tipico comando che sfrutta l'iterazione è "while" (mentre) o "until" (fino a).

Continua la lettura
57

Vantaggi

La nascita di questo enunciato portò, alla fine degli anni '60 e all'inizio dei '70, un notevole cambiamento rispetto al comportamento che si seguiva riguardo alla programmazione. L'uso sconsiderato di alcuni comandi come "go to" fu fermato, mentre furono garantiti tre benefici fondamentali per il successo dell'industria informatica:

- La leggibilità, che permetteva a tutti i calcolatori, una volta implementato il codice, di capire univocamente gli ordini;

- La modificabilità, ovvero la possibilità di entrare all'interno del codice e modificarlo in ogni momento, secondo necessità;

- La semplicità di codifica, ovvero la facilità di sapere quali informazioni usare e quando, senza dubbi.

67

Guarda il video

77

Consigli

Potrebbe interessarti anche

Naviga con la tastiera

Segnala contenuti non appropriati

Tipo di contenuto
Devi scegliere almeno una delle opzioni
Descrivi il problema
Devi inserire una descrizione del problema
Si è verificato un errore nel sistema. Riprova più tardi.
Segnala il video che ritieni inappropriato
Devi selezionare il video che desideri segnalare
Verifica la tua identità
Devi verificare la tua identità
chiudi
Grazie per averci aiutato a migliorare la qualità dei nostri contenuti

Guide simili

Università e Master

Come applicare il teorema di Norton

Il teorema di Norton afferma che è possibile semplificare qualsiasi circuito lineare, a prescindere da quanto esso sia complesso, ricavando un circuito equivalente con un solo generatore di corrente e resistenza collegati in parallelo ad un carico. Come...
Università e Master

Teorema dei valori intermedi: dimostrazione

Il teorema dei valori intermedi è uno dei più importanti in matematica: esso serve infatti per arrivare, attraverso dei ragionamenti successivi, a definire il famoso e importante teorema di Weierstrass. Con i passaggi che seguono andremo a vedere nello...
Università e Master

Come e quando applicare il teorema di Bayes in probabilità

Per poter fare il calcolo delle probabilità, generalmente ci si avvale di varie tecniche, come ad esempio il famoso Teorema di Bayes. Questo specifico teorema deriva esattamente da due importantissimi teoremi: il teorema della probabilità composta e...
Università e Master

Come dimostrare il Teorema di Bernstein

Prima di iniziare col discorrere del Teorema di Bernstein, è d'obbligo un piccolo chiarimento al fine di evitare ogni dubbio o fraintendimento nel lettore. Ed è bene aggiungere che i vari Bernstein non sono la stessa persona: si tratta di un curioso caso...
Università e Master

Teorema di Eulero (aritmetica modulare): dimostrazione

Questa guida dal titolo "Teorema di Eulero (aritmetica modulare): dimostrazione" si prefigge di dimostrare cos'è. Il Teorema di Eulero può essere considerato in alcuni casi la conseguenza del teorema di Lagrange, che spiegherò in modo dettagliato nei...
Università e Master

Come dimostrare il teorema di unicità del limite

Il teorema di unicità del limite è senza alcuna ombra di dubbio uno dei teoremi fondamentali dell'analisi matematica, perché infatti su di esso si basa tutto il lavori dei calcolo dei limiti, che sono certamente indispensabili per questa tipologia di...
Università e Master

Teorema di Eulero: dimostrazione

Il Teorema di Eulero (chiamato anche Teorema di Fermat-Eulero) dimostra che se è un intero positivo e un coprimo (interi che non hanno nessun divisore a eccezione di 1 e -1, se il loro massimo comune divisore è 1) rispetto a. In questo modo φ() ≡ 1(mod...
Università e Master

Come risolvere un circuito elettrico con il teorema di Millman

Questo teorema deve il nome al suo ideatore Jacob Millman, fra l'altro autore di uno dei più importanti testi sulla materia ed è un teorema che è tecnicamente derivato da quello di Thévenin è dalle leggi di Ohm e Kirchhoff. Grazie a questo teorema è...