Appunti VERIFICATO
Strutture dati (fino alberi)
102 visualizzazioni
Nessun voto ancora
Di cosa parla
Riassunto AI · si legge in un minuto
Complessità algoritmica misura l'efficienza, con l'importanza della dimensione del problema. Si analizzano il caso pessimo e medio. Ricerche: sequenziale C(n) = n, binaria C(n) = log2(n). Stack (LIFO): push, pop, isEmpty. Coda (FIFO): put, get, isEmpty. Pila e coda con priorità e heap usano vettori per implementazione. Array è struttura a accesso diretto. Catene e anelli sono strutture concatenate. Strutture astratte lineari come liste lineari hanno operazioni locali e globali. Complessità in spazio misura la memoria utilizzata, con notazione O grande per valutare il tempo di esecuzione. Classificazione problemi: decidibili, trattabili (polinomiale), i
Leggi il riassunto completo
- Complessità: si valuta l'efficienza rispetto alla facilità di implementazione, considerando la dimensione del problema e della quantità di dati. L'algoritmo C(n) misura la complessità in tempo.
- Ricerca binaria vs ricerca sequenziale: la ricerca binaria ha una complessità logaritmica (C(n) = log2(n)), mentre la ricerca sequenziale lineare (C(n) = n). La complessità può degenerare a C(n^2) o più nel caso peggiore.
- Strutture dati: stack e coda, con operazioni e implementazione tramite vettore. Priorità queue e heap, con metodi di inserimento, rimozione e modifica. Array e matrici caratterizzati da indirizzo base, numero massimo di elementi e tipo di elementi.
Riassunto generato con l'intelligenza artificiale a partire dagli appunti. Come lo facciamo
Stai vedendo l'anteprima delle prime pagine. Il file completo è gratis: registrati per leggerlo tutto.
Studia questi appunti con l'AI
Riassunto e domande d'esame sono gratis: chiedili e ti mandiamo un'email quando sono pronti.
In preparazione: di solito è pronto in giornata.
Questo appunto è gratis. Registrati in 30 secondi per leggere tutte le pagine e scaricarlo.
Simula l'esame con domande costruite su questi appunti.
Di cosa parla l'insegnamento
ALGORITMI E STRUTTURE DATI · 2° anno · 9 CFU · INFO-01/A
Al termine dell’insegnamento lo studente: • conosce le strutture dati fondamentali (liste, alberi e grafi), ne ha compreso l’utilizzo, le possibili implementazioni e le operazioni fondamentali ed è in grado di valutare la complessità computazionale di tali operazioni; • conosce gli algoritmi di ricerca su memoria…