Matematica algoritmi

I riassunti, le citazioni e i testi contenuti in questa pagina sono utilizzati per sole finalità illustrative didattiche e scientifiche e vengono forniti gratuitamente agli utenti.

Definizione di Algoritmo:

Algoritmo deriva dal nome del matematico arabo Al Khuwarizmi, vissuto nel IX secolo d.C.; esempi di algoritmo sono stati ritrovati in Mesopotamia su tavolette babilonesi risalenti al 1800-1600 a.C.
Un algoritmo è una successione di istruzioni o passi che definiscono le operazioni da eseguire sui dati per ottenere i risultati; un algoritmo fornisce la soluzione ad una classe di problemi
Lo schema di esecuzione di un algoritmo specifica che i passi devono essere eseguiti in sequenza, salvo diversa indicazione
Ogni algoritmo è concepito per interagire con l’ambiente esterno per acquisire dati e comunicare messaggi o risultati; i dati su cui opera un’istruzione sono forniti dall’esterno o sono frutto di istruzioni eseguite in precedenza

Si definisce un algoritmo una procedura Passo passo per la risoluzione di un problema o lo svolgimento di un compito. Se ben pensato l’algoritmo può essere svolto da una macchina (tramite la programmazione.

Proprietà degli algoritmi:

Affinché una “ricetta”, un elenco di istruzioni, possa essere considerato un algoritmo, devono essere soddisfatti i seguenti requisiti:

Finitezza: ogni algoritmo deve essere finito, cioè ogni singola istruzione deve poter essere eseguita in tempo finito ed un numero finito di volte
Generalità: ogni algoritmo deve fornire la soluzione per una classe di problemi; deve pertanto essere applicabile a qualsiasi insieme di dati appartenenti all’insieme di definizione o dominio dell’algoritmo e deve produrre risultati che appartengano all’insieme di arrivo o codominio
Non ambiguità: devono essere definiti in modo univoco i passi successivi da eseguire; devono essere evitati paradossi, contraddizioni ed ambiguità; il significato di ogni istruzione deve essere univoco per chiunque esegua l’algoritmo

Un algoritmo deve poter essere eseguito da chiunque, senza che l’esecutore sia stato necessariamente coinvolto nell’analisi del problema o nella descrizione dell’algoritmo

Gli algoritmi devono essere formalizzati per mezzo di appositi linguaggi, dotati di strutture linguistiche che garantiscano precisione e sintesi

I linguaggi naturali non soddisfano questi requisiti, infatti...

…sono ambigui: la stessa parola può assumere significati diversi in contesti differenti (pesca è un frutto o un’attività sportiva)
…sono ridondanti: lo stesso concetto può essere espresso in molti modi diversi, ad esempio “somma 2 a 3”, “calcola 2+3”, “esegui l’addizione tra 2 e 3”

I dati su cui opera un algoritmo sono costanti e variabili

Un dato è costante quando il suo valore non può essere aggiornato durante l’esecuzione dell’algoritmo
Una variabile è una coppia <nome, valore>: può essere immaginata come una scatola sulla quale è scritto un nome e che può contenere un valore

Risolvere un problema significa individuare un
procedimento che permetta di arrivare al
risultato partendo dai dati
• Il procedimento (chiamato algoritmo) è
composto da passi elementari
• Il modo di esprimere la sequenza dei passi
elementari deve essere standardizzato

Proprietà degli algoritmi

• L'algoritmo è caratterizzato da:
– finitezza: composto da un numero finito di passi elementari; le operazioni sono
eseguite un numero finito di volte
– non ambiguità: i risultati non variano in funzione della macchina/persona che
esegue l'algoritmo (deterministico)
– realizzabilità: deve essere eseguibile con le risorse a disposizione
vedi altre due proprietà sotto

Algoritmo
• Per definire un algoritmo è necessario:
– condurre un'attenta analisi del problema
– individuare i possibili ingressi
– precisare le uscite
– definire completamente e dettagliatamente la
sequenza dei passi che portano alla soluzione
è conveniente suddividere il problema in piccoli sottoproblemi

Rappresentazione degli algoritmi

• Si fa riferimento ai diagrammi di flusso
(flow chart)
• Sono rappresentazioni grafiche dei passi elementari; visione globale del problema
• Strumento efficace per descrivere un algoritmo
(più della descrizione a parole, troppo generica
o appesantita da troppi dettagli)
• Le operazioni base sono 4
Operazioni base
• Le operazioni primarie sono:
– Trasferimento di informazioni
lettura dati, scrittura risultati, visualizzazione dati intermedi
– Esecuzione di calcoli
– Assunzione di decisioni
– Esecuzione di iterazioni
ripetizione di sequenze di operazioni
• Sono rappresentate da forme geometriche diverse

Tecniche di programmazione
• Programmazione top-down:
– scomposizione iterativa del problema in sottoproblemi
– i sottoproblemi devono essere indipendenti ed avere interfacce ben definite
– visibilità dei dettagli di ogni sottoproblema

• Teoria nata nel 1965

• Basata su eliminazione dei salti incondizionati e -più generalmente- sulla definizione di restrizioni
• Rendono la scrittura dei programmi e la loro manutenzione più semplici
• Migliorano la leggibilità dei programmi

Teorema di Jacopini-Bohm

• Per costruire un programma sono necessari 3 soli blocchi:

1. blocco di elaborazione
è assimilabile ad una sola istruzione o un solo blocco con un ingresso e una uscita
2. meccanismo di ripetizione (o loop)
3. meccanismo di decisione binaria
I
Strutture per il controllo di flusso

• While-Do

• Repeat-Until

• If-Then-Else

• All'interno di ogni blocco si nasconde un ciclo o una biforcazione
• Il programma risulta quindi composto da una sequenza di blocchi, senza
controlli di flusso
• Simile alla programmazione top-down dove, però, i blocchi non devono essere
indipendenti e omogenei

Scelta dell'algoritmo
• Non esistono strutture (dati e di controllo) preferite: la loro scelta dipende dal tipo di linguaggio in cui si codifica l'algoritmo

• La scelta dell'algoritmo ottimo dipende dal linguaggio a disposizione: occorre
conoscere bene il linguaggio e le primitive che esso offre

Ordine logico della trasformazione di un algoritmo in linguaggio di programmazione:

Introduzione: Le proprietà di complessità e correttezza degli algoritmi

Prendiamo il problema della somma dei primi 100 numeri interi positivi, cioè la somma 1+2+3+...+ 99+100 e pensiamo di risolverlo usando una calcolatrice.

Posso: 1.azzerare il visore, 2.battere e registrare 1, 3.sommare, 4.battere 2, 5.sommare, ..., 198.battere 99, 199.sommare, 200.battere 100, 201.sommare. A questo punto il visore mostra la somma voluta 5050.

Oppure posso conoscere il risultato di Gauss secondo il quale 1+2+3+...+ 99+100 = 50 * 101, e quindi usare la calcolatrice come segue: 1.azzerare il visore, 2.battere e registrare 50, 3. battere 101, 4.fare il prodotto. A questo punto il visore mostra 5050.

I due diversi procedimenti per ottenere la somma voluta sono due strategie o algoritmi differenti di uso della calcolatrice per risolvere lo stesso problema.

Se poi voglio sommare i primi 200 numeri interi le due precedenti strategie adattate al nuovo caso diventano:

- 1.azzerare il visore, 2.battere e registrare 1, 3.sommare, 4.battere 2, 5.sommare, ..., 398.battere 199, 399.sommare, 400.battere 200, 401.sommare. A questo punto il visore mostra la somma voluta 20100.
- 1.azzerare il visore, 2.battere e registrare 100, 3. battere 201, 4.fare il prodotto. A questo punto il visore mostra 20100 cioè 100 * 201.

Ci rendiamo subito conto che la prima strategia richiede più operazioni sulla calcolatrice. Nell’ipotesi che le operazioni richiedano lo stesso tempo, ipotesi molto semplificativa ma che fa al caso nostro, la prima strategia richiede 201 operazioni nel primo caso e 401 nel secondo: all’incirca il doppio come doppio è il numero di addendi della somma voluta nei due casi.
La seconda strategia richiede 4 operazioni in ogni caso, un numero di operazioni costante indipendentemente dal numero di addendi nella somma voluta.

Diremo che la prima strategia ha costo cioè richiede un numero di operazioni proporzionale al numero di addendi da sommare, la seconda strategia ha invece costo costante perché il numero di operazioni è sempre lo stesso a prescindere dal numero di addendi da sommare.
La proprietà di complessità di un algoritmo è nel nostro corso intesa come il costo dell’ algoritmo, come diremo, nel caso peggiore.

A fronte di due o piú differenti strategie è lecito domandarsi se realmente risolvano lo stesso problema: è questa la proprietà di correttezza di un algoritmo di cui diremo precisamente dopo:

· avere illustrato vari esempi di algoritmi specificati in un linguaggio formale particolare (nel nostro caso il Pascal)
· avere imparato a commentare tali algoritmi usando le asserzioni. Per vedere cosa siano i commenti e le asserzioni rimandiamo rispettivamente al punto X.Y e ai capitoli che seguono.

Algoritmo diretto (compio tutti i passi un'unica volta per risolvere un problema)(for i)
Esempio:
mi lavo i capelli:
1)Apro l’acqua
2)m’insapono (se m’insapono più volte è iterativo)
3)mi sciacquo(se mi sciacquo più volte è iterativo)
2)Chiudo l’acqua(se uso stessa tecnica per aprire l’acqua è ricorsiva)
4)Asciugo i capelli

Se eseguo tutti i passi un’unica volta (senza iteratività ne ricorsione) l’algoritmo di soluzione è diretto

Algoritmo iterativo (compio più passi per risolvere un problema) (while..do)
Si ha a che fare con un algoritmo iterativo quando una o più passi vengono eseguiti un numero finito di volte per la determinazione di un risultato o la soluzione di un problema (iterativo…ripetitivo)

Algoritmo ricorsivo (ripeto lo stesso passo più volte per risolvere un problema) (function in programmazione)

Un algoritmo si dice riricorsivo quando è definito in termini di se stesso, cioè quando una sua istruzione richiede una nuova esecuzione dell’algoritmo stesso

QUANDO DURANTE LA SCOMPOSIZIONE DI UN PROBLEMA IN SOTTO-PROBLEMI,
I SOTTO-PROBLEMI RISULTANO FORMALMENTE SIMILI AL PROBLEMA DI PARTENZA IL PROBLEMA SI DICE RISOLTO
RICORSIVAMENTE

IL CONCETTO DI RICORSIONE

UN OGGETTO SI DICE RICORSIVO SE E’ DEFINITO IN TERMINI DI SE STESSO.
Esempi
· I NUMERI NATURALI
a) 1 è un numero naturale
b) il successore di un numero
naturale è un numero naturale.
· I GRAFI DI FLUSSO STRUTTURATI
· LE STRUTTURE AD ALBERO

ESEMPIO
LA FUNZIONE FATTORIALE :
N! = N * (N-1) * (N-2) *… *2 * 1
OPPURE RICORSIVAMENTE:
1 se N =1
N! =
N * (N-1)! Se N > 1

UNA DEFINIZIONE RICORSIVA DEFINISCE UNA ENTITA’ IN TERMINI DI VERSIONI PIU’ SEMPLICI DELLA STESSA ENTITA’ CHE SI STA DEFINENDO.

· UN PROBLEMA DI ORDINE N E’ DEFINITO IN TERMINI DEL MEDESIMO PROBLEMA DI ORDINE INFERIORE

· E’ INDISPENSABILE CHE NELLA DEFINIZIONE CI SIA IL LIVELLO
ASSIOMATICO: E’ GRAZIE AD ESSO CHE POSSONO RICOSTRUIRSI I LIVELLI SUCCESSIVI

ESEMPI
· IL PRODOTTO DI DUE NUMERI x ED y:
X se Y = 1
X * Y =
X + X * (Y –1) se Y > 1
· INVERSIONE DI UNA STRINGA:
AMOR-R(AMO)-RO(AM)-ROM(A)-ROMA

IMPORTANTE
· UN ALGORITMO ESPRESSO RICORSIVAMENTE TERMINA SEMPRE.

· UNA FUNZIONE (O UN PROBLEMA) ESPRIMIBILE RICORSIVAMENTE PUO’ RISOLVERSI
ITERATIVAMENTE.

· UNA FUNZIONE ESPRIMIBILE RICORSIVAMENTE E’ COMPUTABILE (ESISTE UN
METODO SOLUTIVO TIPO ALGORITMO)

· OGNI FUNZIONE COMPUTABILE PER MEZZO DI UN PROGRAMMA E’ RICORSIVA

Formalizzazione del concetto di algoritmo.

Un algoritmo deve poter essere eseguito da chiunque, senza che l’esecutore sia stato necessariamente coinvolto nell’analisi del problema o nella descrizione dell’algoritmo

Gli algoritmi devono essere formalizzati per mezzo di appositi linguaggi, dotati di strutture linguistiche che garantiscano precisione e sintesi

I linguaggi naturali non soddisfano questi requisiti, infatti...

…sono ambigui: la stessa parola può assumere significati diversi in contesti differenti (pesca è un frutto o un’attività sportiva)
…sono ridondanti: lo stesso concetto può essere espresso in molti modi diversi, ad esempio “somma 2 a 3”, “calcola 2+3”, “esegui l’addizione tra 2 e 3”

Istruzioni operative, che producono risultati
Istruzioni di controllo, che controllano il verificarsi di condizioni specificate e, in base al risultato del controllo, determinano il flusso di istruzioni da eseguire
Istruzioni di salto, che alterano il normale flusso di esecuzione sequenziale delle istruzioni di un algoritmo, specificando quale sia la successiva istruzione da eseguire

nelle istruzioni di salto condizionato, l’effettiva esecuzione del salto è condizionata al verificarsi di una condizione specificata
l’istruzione di salto incondizionato produce sempre un salto

Istruzioni di ingresso/uscita, che specificano come debba essere effettuata una trasmissione di dati o messaggi fra l’algoritmo e l’ambiente esterno
Istruzioni di inizio/fine esecuzione, che indicano l’inizio/la fine dell’algoritmo

Il linguaggio dei diagrammi a blocchi è un possibile formalismo per la descrizione di algoritmi

Il diagramma a blocchi, o flowchart, è una rappresentazione grafica dell’algoritmo

Un diagramma a blocchi descrive il flusso delle operazioni da eseguire per realizzare la trasformazione, definita nell’algoritmo, dai dati iniziali ai risultati

Ogni istruzione dell’algoritmo è rappresentata all’interno di un blocco elementare, la cui forma grafica è determinata dal tipo di istruzione

I blocchi sono collegati tra loro da linee di flusso, munite di frecce, che indicano il susseguirsi di azioni elementari

Un diagramma a blocchi è un insieme di blocchi elementari composto da:

un blocco iniziale
un blocco finale
un numero finito n (n³1) di blocchi di azione e/o di blocchi di lettura/scrittura
un numero finito m (m ³ 0) di blocchi di controllo

L’analisi strutturata favorisce la descrizione di algoritmi facilmente documentabili e comprensibili

I blocchi di un diagramma a blocchi strutturato sono collegati secondo i seguenti schemi di flusso:

Schema di sequenza – più schemi di flusso sono eseguiti in sequenza
Schema di selezione – un blocco di controllo subordina l’esecuzione di due possibili schemi di flusso al verificarsi di una condizione
Schema di iterazione – si itera l’esecuzione di un dato schema di flusso

Tesi di Church. (http://it.wikipedia.org/wiki/Teorema_di_Church)

Il Teorema di Church, dimostrato dal matematico Alonzo Church, nel 1936, afferma che la logica predicativa è indecidibile. In realtà, è quasi un corollario della soluzione di Alan Turing al problema della fermata, uno dei 23 problemi di Hilbert.
Enunciato: Non esiste nessuna macchina di Turing in grado di determinare se una formula della logica predicativa è valida oppure no.
Dimostrazione: Procediamo per assurdo. Se una tale macchina esistesse, potrebbe dimostrare che
«esistono C ed r tali che C è il calcolo del risultato r a partire dai dati d e dal programma p»
Il tutto perché possiamo esprimere dati e programmi in logica predicativa. Più precisamente

l' n-esima cifra binaria di un dato viene codificata come il valore di verità dell'n-esima lettera proposizionale di una lista associata al dato in questione;
un'istruzione si codifica in un'implicazione relativa alle lettere che codificano le cifre dei dati;
un programma è una congiunzione di istruzioni;
una configurazione è una congiunzione di dati; e
un calcolo è una congiunzione di configurazioni, di cui la prima è l'input del programma, e ciascuna delle altre è ottenuta dalla precedente mediante l'applicazione di un'istruzione e l'ultima è l'output del programma, ossia r

Avremmo dunque una macchina che nega il teorema di Turing, e quindi un assurdo. Dunque la logica predicativa è indecidibile.
Per inciso, la logica predicativa monadica, che comprende anche i sillogismi, è decidibile, come ha dimostrato Löwenhweim nel 1915. Inoltre, si può vedere facilmente che la logica predicativa, in generale, è semidecidibile: è sempre possibile dimostrare la validità di una formula valida, perché l'albero semantico contiene tutti i rami contradditori ed è finito. Per una formula non valida, invece, qualche ramo non contradditorio può essere infinito. Possiamo dunque determinare tutte le risposte positive, ma non tutte quelle negative.
Davide chiede:
Vorrei qualche spiegazione sulla cosiddetta "tesi di Church" per quanto riguarda algoritmi ed informatica e perché è importante.
(risponde Valerio Cecere)

La domanda potrebbe richiedere una risposta molto lunga, viste le molte interpretazioni e applicazioni di questa teoria. Ma per fortuna a noi interessa la sua applicazioni solo in informatica, per cui si può iniziare col dire che la tesi di Church in realtà viene quasi sempre nascosta dietro un'altra tesi, quella di Turing che chiunque si occupi di informatica conosce o dovrebbe conoscere, anche solo per sentito dire, se non la tesi almeno il test di Turing.
La prima versione di questa tesi potrebbe sembrare banale:
"I problemi matematici possono essere risolti solo da operazioni matematiche"
In effetti è chiaro che un problema matematico non possa essere risolto con nozioni di medicina, o speculazioni filosofiche (anche se... :-) ). A parte questo commento poco costruttivo, possiamo analizzare la tesi in modo più attento, e giungere ad una conclusione ben più interessante. Infatti se tutti i problemi matematici possono essere risolti con operazioni matematiche, e se avessimo a disposizione una macchina in grado di risolvere problemi matematici, le cose cambiano.
Prima dell'avvento di questa macchina (e anche dopo :-) ), gli stessi problemi venivano risolti da esseri umani, che inevitabilmente eseguivano operazioni matematiche, per cui almeno in parte la macchina e l'uomo svolgevano le stesse operazioni. A questo punto interviene Turing che riprendendo questa semplice tesi, aggiunge (Tesi di Church-Turing):
Ciò che può essere calcolato da un essere umano può essere calcolato anche da una macchina
A cui si possono unire le seguenti affermazioni collegate alla prima:
Ciò che può essere calcolato da una macchina è calcolabile cicli di operazioni e/o con funzioni ricorsive o parzialmente ricorsive.
Ciò che puo' essere calcolato da un essere umano è calcolabile con cicli e/o funzioni ricorsive oparzialmente ricorsive.
E' importante sottolineare che la tesi di Church-Turing non è dimostrabile come un teorema matematico, è semplicemente un'ipotesi sui procedimenti usati dal cervello umano per risolvere i problemi.
Come ultima citazione (lo prometto) riporto la versione di Hardy che trovo abbastanza divertente:
In fondo tutti i matematici sono isomorfi (nel senso che compiono più o meno le stesse operazioni)
Da cui deriva la tesi Church-Turing versione isomorfismo:
Supponiamo che esista un metodo che un essere senziente possa seguire per risolvere un problema e che permetta di ottenere un risultato in ogni caso e in un tempo finito. Allora esiste un qualche programma che da esattamente le stesse risposte del metodo dell'essere senziente.
e non si ferma quì:
Inoltre il processo mentale ed il programma sono isomorfi, nel senso che a un qualche livello, vi è una corrispondenza tra i passi che vengono compiuti nella macchina e nel cervello.
Credo che a questo punto sia chiara l'importanza di questa tesi. Tanto per iniziare ci suggerisce che se riusciamo a risolvere un problema (noi esseri senzienti), esisterà un programma elaborato da una macchina, che lo potrebbe risolvere al posto nostro. Ma soprattuto fa sorgere il dubbio se sia possibile estendere il ragionamento non solo ai problemi matematici, ma anche a tutti gli altri e quindi se sia possibile realizzare una macchina pensante.
Vorrei sottolineare che non ho messo la parola pensante tra virgolette, perché in effetti una macchina pensante già esiste e siamo noi stessi. Probabilmente mi si potrebbe accusare di avere una visione meccanicista della vita, in cui non trova posto il sovrannaturale (in cui molti credono), o la religione con tutti i suoi annessi e connessi (l'anima, gli angeli, Dio, ...), ma questo è un discorso che esula dall'argomento.
Prima di terminare non posso evitare una breve citazione del più famoso test di Turing, pensato per poter stabilire se ci si trova davanti una reale macchina pensante e quindi se si è giunti alla realizzazione del sogno di una delle branche più affascinanti della scienza dell'informazione.
Nel test si devono avere tre stanze comunicanti tra loro solamente con un dispositivo che permetta uno scambio verbale senza vedere l'interlocutore o ascoltare la sua voce, insomma senza sapere nulla dell'altro se non il contenuto dei suoi messaggi. In una delle stanze ci sarà una sorta di giudice e nelle altre due (isolate tra di loro) un essere umano e l'ipotetica macchina pensante.
Se dopo un certo numero di scambi di messaggi il giudice, non riesca a decidere o peggio si sbagli nel dire quale sia la macchina e quale l'uomo, ci si troverà difronte alla prima macchina intelligente.
Forse non sarà un test sicuro al cento per cento, anche considerando che in passato ci si è andati vicino con un programma passato alla storia con il nome di Eliza, e che a differenza di quello che pensava Turing non poteva certamente definirsi intelligente. Comunque la ricerca continua e probabilmente non si riusciranno a vedere risultati interessanti per molti anni.
L'ultima cosa che vorrei aggiungere è che questo tipo di approccio, in realtà non è l'unico, e forse il più promettente si stà rivelando quello delle reti neurali che sostituiscono la sequenza di operazioni previste dalla macchina di Turing, con una rete neurale artificiale, in cui la vera elaborazione non si trova un una singola entità computante, ma nella cooperazione di piccole e semplici macchine (neuroni), che in numero molto elevato lavorano contemporaneamente svolgendo solo una piccolissima frazione del tutto. Alcuni risultati di questo approccio sono le memorie associative di Hebb, e il Perceptron con cui si riescono a riconoscere delle forme e quindi una sorta di senso della vista artificiale

Funzioni non calcolabili.
Computabilit`a e Complessit`a Computazionale
M. Benini
1 Introduzione Il concetto di computabilit`a riguarda la definizione di che cosa `e calcolabile, mentre il concetto di complessit`a computazionale riguarda quanto un program- ma `e "diAEcile", nel senso di quanto costa espletare le computazioni che esso pu`o svolgere.
2 Tesi di Church Abbiamo gi`a mostrato che esistono funzioni non calcolabili, ed abbiamo fatto vedere un esempio di problema computazionalmente diAEcile.
Esistono due asserzioni ritenute generalmente valide:
ffl Tesi di Church: Ogni "cosa" calcolabile, lo `e da una macchina di Turing. ffl Tesi di Church estesa: Ogni "cosa" calcolabile in modo eAEciente, `e
calcolabile da una macchina di Turing in tempo polinomiale rispetto alla dimensione dell'input.
La nostra prova di esistenza di funzioni non calcolabili era basata su un argomento di conteggio: l'insieme delle funzioni dai naturali ai booleani `e pi`u grande, ovvero ha una cardinalit`a maggiore, dell'insieme dei programmi che `e possibile scrivere con un qualsiasi linguaggio di programmazione.
E' possibile definire esplicitamente esempi di funzioni non calcolabili. In particolare `e possibile costruire problemi di decisione che non ammettono alcun algoritmo di decisione che termini per ogni possibile input.
Un esempio di questo tipo `e il cosiddetto halting problem:
fOE(x) j OE(x) termina, dove x `e l'input e OE `e un programmag : Un altro esempio `e dato dal problema che richiede di decidere se un pro- gramma computa la stessa funzione di un programma OE dato:
f j per ogni x; (x) = OE(x)g : In entrambi i casi, la matematica necessaria per dimostrare che questi proble- mi non ammettono come risultato una funzione calcolabile che termini sempre, `e troppo complessa per essere illustrata in questo corso.

Problemi non decidibili

Esempi:
1) Calcolare il cambio euro/dollaro al 31/12/2020
2) Valutare se f(x) è una funzione costante
Attenzione:
Esistono problemi che pur rientrando nel mondo del decidibile non sono comunque risolvibili perché richiedono un costo temporale insostenibile (esempio di un calcolo che impiega migliaia di anni per essere eseguito !)

Problemi decidibili

Dati due numeri calcolarne la somma
Dato un elenco di numeri calcolarne il minimo

Fonte: http://www.alessandrobonini.it/download/matematica/Algoritmi%20e%20loro%20propriet%E0.doc

Autore: non identificabile dal documento (se conoscete l'autore inviateci un messaggio e-mail)

Matematica algoritmi