Il teorema di Böhm-Jacopini

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

Potrebbe interessarti anche

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

Teorema di Bolzano: dimostrazione

Il "Teorema di Bolzano" (o "teorema degli zeri per le funzioni continue") prende il nome dal matematico e filosofo boemo Bernard Bolzano, vissuto tra il XVIII ed il XIV secolo. Tale teorema (da non confondere con il "teorema di Bolzano-Weierstrass" sulle...
Università e Master

Teorema di Stokes: dimostrazione

Nella geometria differenziale, ossia lo studio di oggetti geometrici come curve e superfici, il Teorema di Stokes è un enunciato riguardante l'integrazione delle forme differenziali. In particolare è volto a generalizzare i teoremi di calcolo vettoriale...
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 della bisettrice: dimostrazione

La matematica è una materia ricca di formule, è vero, ma non richiede soltanto un impegno di tipo mnemonico. In questa disciplina è molto importante il ragionamento, che va sfruttato per applicare le formule ai diversi problemi. Lo studio della geometria,...
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

Teorema di Caccioppoli: dimostrazione

Il Teorema di Caccioppoli è uno dei teoremi più importanti nell'ambito dei cosiddetti studi metrici. È noto anche come Teorema delle contrazioni o Teorema del punto fisso, anche se è ancora più giusto chiamarlo Teorema di Barnach-Caccioppoli, dai...
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 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...