[algoritmi] Software calcolo complessità

[vlr]

Salve gente!

Qualcuno di voi conosce o almeno sa se esite un software per il calcolo o l'analisi della complessità degli algoritmi?

Altrimenti cosa aspettate ad inventarne uno?

[Gondor]

Spostato su Programmazione

[Thor82]

premetto: non conosco programmi che facciano cio' nè algoritmi per calcolarlo ma..


credo che in base al compilatore e alle opzioni utilizzate un teorico controllo sulla complessità potrebbe essere non oggettivo, perchè molti compilatori ottimizzano automaticamente pezzi di codice, e ne tralasciano altri, col risultato che se tu fai delle istruzioni che lui è in grado di ottimizzare, le ottimizza cambiando il codice macchina e mettendo quello che lui sa essere migliore...

pero' è solo una supposizione

[unomichisiada]

Esiste un'intera branca dell'informatica che si occupa di analisi della complessità di un algoritmo,ovviamente i metodi si basano sull'analisi del codice in maniera svincolata dal particolare elaboratore su cui si fa girare l'algoritmo.I risultati che fornisce questa analisi non sono ovviamente delle stime precise ma semplicemente danno un'idea delle prestazioni dell'alogritmo al crescere di un certo(o di certi) parametri di input,si parla di complessità asintotica(se sei interessato esiste un libro molto ben fatto a riguardo di cui non ricordo il titolo ma i cui autori dovrebbero essere CORMEN e LEISERSON).Ad esempio si dice che la ricerca in una lista concateata ha una complessità lineare rispetto a n dove n è il numero di elementi della lista,cioè il suo tempo di esecuzione cresce in maniera direttamente proporzionale a n.Ci sono casi in cui la crescità è proporzionale a n^2,n*log(n) etc..comunque è possibile effettuare anche unanalisi machine dependent ma molto precisa sui tempi di esecuzione o il numero di istruzioni eseguite da un certo programma in un certo calcolatore,questo si fa inserendo nei punti giusti del codice degli appositi timer e contatori di istruzioni.Per quanto riguarda l'analisi della complessità di un programma già pronto (di cui non si ha il codice)è un'altro paio di maniche e sinceramente non sono molto informato sull'argomento.Comunque se cipensi non è difficile scrivere un programma che valuti i tempi di esecuzione di un altro sotto diverse condizioi e poi effettui una tabulazione dei risultati al fine di costruire ad esempio un grafico.

[vlr]

A livello di teoria diciamo che ne so abbastanza (ottimisticamente parlando ).
Il mio interesse è più legato alla verifica della teoria, soprattutto per algoritmi ricorsivi. A breve ho l'esame!

Esiste un programma per qualunque tipo di necessità, tranne per questo! Curioso...

[Shores]

Equivale a chiedere se esiste un software per il calcolo simbolico...

Che io sappia devi rivolgerti a Mathematica o simili, ma devi certamente ricodificare in algebra il tuo algoritmo, altrimenti non riuscirai ad analizzarlo.

[vlr]

Originariamente inviato da Shores
Equivale a chiedere se esiste un software per il calcolo simbolico...

Se lo dici tu...

[i]Che io sappia devi rivolgerti a Mathematica o simili, ma devi certamente ricodificare in algebra il tuo algoritmo, altrimenti non riuscirai ad analizzarlo. [/B]

Non lo conosco... è simile a Derive? a MathLab?

Tuttavia non so cosa potrei tirarne fuori, algoritmi di ordinamento o cammino minimo di un grafo non sono facilissimi da ricodificare... dal mio cervellino...

Comunque grazie!

[Shores]

Originariamente inviato da vlr
Se lo dici tu...



Non lo conosco... è simile a Derive? a MathLab?

Tuttavia non so cosa potrei tirarne fuori, algoritmi di ordinamento o cammino minimo di un grafo non sono facilissimi da ricodificare... dal mio cervellino...

Comunque grazie!

Ma scusa, se usi algoritmi classici esiste già una letteratura completa che analizza la loro complessità, perchè mai dovresti rimetterti a ricavarla...

Non capisco: stai usando algoritmi nuovi da te inventati o algoritmi classici?

[vlr]

Originariamente inviato da Shores
Ma scusa, se usi algoritmi classici esiste già una letteratura completa che analizza la loro complessità, perchè mai dovresti rimetterti a ricavarla...

Non capisco: stai usando algoritmi nuovi da te inventati o algoritmi classici?

Il motivo è che di alcuni non conosco la complessità perché la letteratura di cui dispongo non la fornisce quindi diciamo che ci sono arrivato da solo, ma vorrei qualcosa di sicuro.

Ti risulta ci sia qualche pagina su Internet con un'analisi della complessità dei principali algoritmi ricorsivi su alberi, grafi e ordinamenti?

In ogni caso grazie!

[anx721]

Originariamente inviato da vlr
Il motivo è che di alcuni non conosco la complessità perché la letteratura di cui dispongo non la fornisce quindi diciamo che ci sono arrivato da solo, ma vorrei qualcosa di sicuro.

Ma non puoi acquisire certezze sulla complessita da te calcolata misurando il tempo di esecuzione di un programma, ne ricaveresti solo dubbi, perke ci sono molti paramentri in gioco, e ovviamante non essite un software che ti calcola la formula della complessita di un algoritmo, perche non è un procedimento algorimtico esso stesso. Se vai sui siti di algoritmi in genere la complessita viene indicata sempre.