Questo sito utilizza cookies, anche di terze parti, per mostrare pubblicità e servizi in linea con il tuo account. Leggi l'informativa sui cookies.
Username: Password: oppure
Algoritmi - Domanda di informatica teorica.
Forum - Algoritmi - Domanda di informatica teorica.

Avatar
Bonnox (Member)
Pro


Messaggi: 82
Iscritto: 23/08/2014

Segnala al moderatore
Postato alle 23:25
Venerdì, 01/07/2016
Salve, sono sempre io, il rompiscatole :D  Mi scuso se non mi sono fatto vivo per un bel po' di tempo, ero occupato..


Da qualche tempo ho un quesito che mi frulla per la testa.
Avete presente il famoso teorema di jacopini bohm che dice che ogni algoritmo puo' essere rappresentato solo dall strutture sequenza, selezione e iterazione? Ebbene, io ho cercato su google la sua dimostrazione, ma non ho trovato niente. Trovo solo slide di fondamenti di informatica che dicono ''esiste''sta cosa" e poi si fermano li'...
Non la sto cercando perche' non mi fidi, anzi, mi pare una conclusione molto logica; la sto cercando per semplice curiosità ! Mi piacerebbe capire come agli albori dell'era informatica se ne siano venuti fuori con questo risultato dalla grande importanza!

ciao e grazie :)

buone ferie

EDIT: uffa, se metto accenti o virgolette o altro si trasformano in caratteri strani...

Edit (pierotofy): problema accenti dovrebbe essere risolto.

Ultima modifica effettuata da pierotofy il 03/07/2016 alle 16:55
PM Quote
Avatar
lumo (Member)
Expert


Messaggi: 413
Iscritto: 18/04/2010

Segnala al moderatore
Postato alle 1:27
Sabato, 02/07/2016
La questione non è così semplice perché prima devi definire cos'è un algoritmo.
In genere si definisce algoritmo una sequenza determinata (possibilmente finita) di passi elementari.
I passi elementari sono definiti dal modello computazionale, quindi a seconda delle fondamenta la dimostrazione cambia.
Ad esempio puoi scegliere di usare come modello computazionale quello random access machine, che in pratica è una macchina di Turing. Oppure puoi decidere di basarti sul lambda calcolo.
Rimane anche da vedere cosa vuol dire sequenza, iterazione e selezione nel contesto.

(in realtà, una volta dimostrato il teorema per ad es. macchine di Turing, la tesi di Church-Turing assicura l'equivalenza per gli altri modelli computazionali)

Di più non saprei dire perché non ho mai cercato la dimostrazione, e in realtà non ho nemmeno ancora fatto il corso di informatica teorica che però dovrei fare l'anno prossimo all'uni.

Ultima modifica effettuata da pierotofy il 03/07/2016 alle 16:56
PM Quote
Avatar
Bonnox (Member)
Pro


Messaggi: 82
Iscritto: 23/08/2014

Segnala al moderatore
Postato alle 9:26
Sabato, 02/07/2016
Testo quotato

Postato originariamente da lumo:

La  [...]




intanto ti ringrazio per la risposta. :k:

potresti fornirmi (se ne sei a conoscenza, ovvio) i titoli di qualche testo di informatica teorica, se non fosse troppo un disturbo?

grazie ancora

Ultima modifica effettuata da Bonnox il 02/07/2016 alle 9:26
PM Quote
Avatar
nessuno (Normal User)
Guru^2


Messaggi: 5475
Iscritto: 03/01/2010

Segnala al moderatore
Postato alle 10:28
Sabato, 02/07/2016
Qui

http://www.cs.unibo.it/~martini/PP/bohm-jac.pdf

il paper originale del 1966 di Bohm e Jacopini ... Buona lettura ...


Ricorda che nessuno è obbligato a risponderti e che nessuno è perfetto ...
PM Quote
Avatar
Bonnox (Member)
Pro


Messaggi: 82
Iscritto: 23/08/2014

Segnala al moderatore
Postato alle 11:42
Domenica, 03/07/2016
grazie mille, cordiali ed efficienti come al solito:k:

PM Quote