Dispense VERIFICATO
Lezioni Dati e Algoritmi 1 (slide)
75 visualizzazioni
5 download
Nessun voto ancora
Stai vedendo l'anteprima delle prime pagine. Il file completo è gratis: registrati per leggerlo tutto.
Di cosa parla
- I problemi computazionali sono definiti come insiemie coppie tra istanze di input e soluzioni valide, dove per ogni istanza deve esistere almeno una soluzione corrispondente.
- Un algoritmo è specificato tramite pseudocodice che opera su un modello di calcolo RAM eseguendo passi elementari quali assegnamenti, operazioni logiche aritmetiche ed indicizzazione degli array.
- L'analisi della complessità temporale si concentra sul caso pessimo e sull'asintotica per stimare il numero massimo di passi elementari in funzione della taglia dell'istanza n ignorando le costanti moltiplicative.
- Le strutture dati sono definite come collezioni di oggetti corredate da metodi, caratterizzate a livello logico dall'Abstract Data Type e a livello fisico dalla loro implementazione concreta.
- L'esempio dell'algoritmo arrayMax illustra il conteggio delle operazioni per determinare i limiti superiori e inferiori della complessità lineare O(n) senza necessariamente identificare l'istanza peggiore specifica.
Questo appunto è gratis. Registrati in 30 secondi per leggere tutte le pagine e scaricarlo.