Dal problema alla risposta – Approfondimento

I problemi I problemi sono delle richieste che richiedono all’uomo un certo impegno fisico e/o intellettuale. Ma tra tutti i problemi, di quali si occupa l’informatica? Assurdi? Perché perdere tempo se la richiesta è assurda… Impossibili? Pur interessanti, è dimostrato che non ammettono soluzione, quindi… sono PROBLEMI NON COMPUTABILI Intrattabili? Le risorse hardware e/o il tempo … Leggi tutto

Dal problema alla risposta

Macchina dedicata Una macchina progettata per svolgere un compito specifico. La macchina riceve i dati e svolge le operazioni prestabilite per ottenere la risposta. La maggior parte degli elettrodomestici sono macchine dedicate: calcolatrice tascabile, ascensore, lavatrice, decoder, … Macchina onnipotente All’estremo opposto una macchina capace di rispondere a richieste di qualsiasi tipo, di risolvere qualsiasi … Leggi tutto

Complessità: asintotica

Dopo aver analizzato la complessità in tempo di alcuni algoritmi possiamo osservare che il caso ottimo di un algoritmo è quasi sempre costante e non sarebbe significativo per la bassa probabilità che si presenti il caso pessimo e il caso medio dipendono dalla dimensione dei dati è difficile calcolare con precisione le costanti moltiplicative per … Leggi tutto

Complessità: torre di Hanoi

Dopo aver analizzato il problema decidiamo che il tempo di esecuzione dell’algoritmo è proporzionale al numero di spostamenti dei dischi T(1)=1 T(2)=T(1)+T(1)+T(1)=3 T(3)=T(2)+T(1)+T(2)=7 T(4)=T(3)+T(1)+T(3)=15 … T(n)=T(n-1)+T(1)+T(n-1)=2*T(n-1)+1 … Numericamente si tratta della successione 1, 3, 7, 15, 31, 63, 127, … cioè 21-1, 22-1, 23-1, 24-1, 25-1, 26-1, 27-1, … quindi T(n) = 2n-1 I tempi … Leggi tutto

Complessità: numeri di Fibonacci

Dopo aver analizzato il problema e individuati i 3 algoritmi discutiamo la loro complessità in tempo. Algoritmo ricorsivo Il tempo di attesa può essere considerato proporzionale al numero di chiamate ricorsive T(1)=1 T(2)=1 T(3)=1+T(2)+T(1)=1+1+1=3 > 22-1 T(4)=1+T(3)+T(2)=1+3+1=5 > 22-1 T(5)=1+T(4)+T(3)=1+5+3=9 > 23-1 T(6)=1+T(5)+T(4)=1+9+5=15 > 23-1 T(7)=1+T(6)+T(5)=1+15+9=25 > 24-1 T(8)=1+T(7)+T(6)=1+25+15=41 > 24-1 … T(n) ≥ 2n/2-1. Il tempo di attesa è maggiore … Leggi tutto

Complessità: problemi difficili

L’argomento viene trattato in modo molto semplificato. Definiamo polinomiali quei problemi con T(n) <= nc, (c > 1) e esponenziali quelli con T(n) <= an, (a > 1). Esistono molti problemi che ammettono un algoritmo risolutivo esponenziale ma per i quali non si è certi che la loro complessità sia esponenziale e si spera che … Leggi tutto

Complessità: problemi

Complessità dei problemi Dato un problema P si possono individuare diversi algoritmi risolutivi A1, A2, … Aq ciascuno con la sua complessità C1, C2, …, Cq. Sia C* la complessità più bassa. Se si dimostra che per il problema P non può esistere un algoritmo con complessità minore di C* allora si può affermare che il problema … Leggi tutto

Complessità: ricerca binaria

Analizziamo il codice int ricercaBinaria(double v[], double k) {    int risp=-1,        inf=0,        sup=v.length-1,        medio;    while(inf

Complessità delle ricerche

Per semplificare i calcoli e per rendere più evidente il confronto tra i due algoritmi ipotizziamo che i coefficienti numerici delle funzioni di complessità in tempo siano molto sfavorevoli per la ricerca binaria, per esempio Tseq(n)=5+5*n Tbin(n)=100+100*log2n calcoliamo i tempi di attesa al variare di n n Tseq(n) Tbin(n) 16 5+5*16=85 100+100*4 = 500 256 … Leggi tutto

Complessità: criteri

Vogliamo individuare dei criteri oggettivi da usare per scegliere tra due algoritmi, risolutivi dello stesso problema, quello che offre prestazioni migliori. Alcuni criteri per valutare un algoritmo e il software corrispondente potrebbero essere correttezza dell’algoritmo qualità dell’interfaccia utente comprensibilità ed espandibilità del codice piattaforma e strumenti di sviluppo velocità dimensione. Correttezza Un algoritmo risolve un problema … Leggi tutto