Algoritmi E Strutture Dati In Java Pdf

[Shari Alvine]

Questolibro, giunto alla sesta edizione inglese e considerato un autorevole punto di riferimento a livello internazionale, stato progettato per essere di ausilio in un corso introduttivo di Algoritmi e strutture dati.

I grafi sono strutture dati molto utili che possono essere usate per modellare diversi problemi. Questi algoritmi hanno applicazione diretta nei siti di Social Network, nella modellazione di Macchine a Stati e molto altro.

L'algoritmo di Bellman Ford l'algoritmo per trovare il percorso pi breve per grafi che possono avere pesi negativi. Questo algoritmo anche valido per rilevare cicli di pesi negativi visto che l'algoritmo converge verso una soluzione ottimale in O(V*E) passaggi. Se quanto risultato non ottimale, allora il grafo contiene un ciclo di peso negativo.

uno dei pi semplici algoritmi di grafo. Attraversa il grafo prima verificando il nodo corrente, poi spostandosi verso uno dei suoi successori e ripetendo il processo. Se il nodo corrente non ha successori da verificare, torna indietro al suo predecessore e il processo continua (spostandosi verso un altro successore). Se viene trovata la soluzione la ricerca si arresta.

Complessit temporale per il caso peggiore O(n). Depth First Search completo su una serie di nodi finita. Funziona meglio su alberi shallow (vale a dire alberi che hanno una piccola altezza o profondit, cio un limitato numero di livelli o strati - n.d.t.).

un ottimo algoritmo per trovare la distanza pi breve tra tutti i vertici in un grafo. un algoritmo molto conciso e una complessit temporale di O(V^3) (dove V il numero dei vertici). Pu essere usato con pesi negativi, anche se i cicli di pesi negativi non devono essere presenti nei grafi.

uno degli algoritmi di grafo pi semplici. Attraversa il grafo prima verificando il nodo corrente, quindi espandendosi aggiungendo i suoi successori al livello successivo. Questo processo viene ripetuto per tutti i nodi nel livello corrente prima di spostarsi a quello successivo. Se la soluzione viene trovata, la ricerca si arresta.

Creiamo 2 array: visited e distance, che registrano rispettivamente se un vertice visitato e qual la distanza minima dal vertice sorgente. Inizialmente l'array visited viene assegnato con valori false e distance come infinito.

Partiamo dal vertice sorgente, che sar u, e i suoi vertici adiacenti v. Ora per ogni v che adiacente a u, la distanza aggiornata se non stato visitato prima e la distanza da u minore della distanza corrente. Poi selezioniamo il vertice successivo con la distanza minore e che non sia stato ancora visitato.

Questo algoritmo risolve il problema del massimo flusso del grafo. Trova la migliore soluzione di flusso tramite le connessioni (edge) dei grafi in modo da ottenere il massimo flusso in uscita dall'altra parte. La sorgente ha una specifica velocit di input e ciascuna connessione ha un peso associato a essa che la quantit massima che pu passare attraverso quella connessione.

Funziona creando percorsi di aumento, ovvero percorsi dalla sorgente all'uscita che hanno un flusso non zero. Facciamo passare il flusso attraverso i percorsi e aggiorniamo i limiti. Ci pu portare a situazioni in cui non abbiamo pi mosse disponibili. Ecco dove la capacit di "annullamento" di questo algoritmo gioca un ruolo importante. In caso di blocco, diminuiamo il flusso e apriamo la connessione per far passare la nostra sostanza corrente.

Durante l'anno accademico verranno assegnati tre progetti: uno perla sessione estiva, uno per quella autunnale, e uno per quellainvernale. I progetti andranno consegnati indicativamente circa 10giorni prima del primo appello d'esame di quella sessione (verrannocomunicate le date precise di volta in volta). Le specifiche deiprogetti saranno rese disponibili circa un mese prima delle scadenzeper la consegna.

I progetti sufficienti consentono di sostenere l'orale in uno degliappelli nella sessione d'esami per la quale sono stati consegnati. Cisaranno tre appelli orali nella sessione estiva (giugno/luglio 2021),uno in quella autunnale (settembre 2021) e due per quella invernale(gennaio/febbraio 2022). Nel caso di progetti insufficienti,sar necessario attendere la sessione d'esami successiva econsegnare le soluzioni dei nuovi progetti che verranno proposti.

L'orale consiste nella discussione dei progetti e in una serie didomande su tutto il programma, in particolar modo gliargomenti di teoria visti a lezione. Potranno essere posti anche deisemplici esercizi sulla complessit o sulle strutture dati dasvolgere sul momento. Il voto finale dipender in modopreponderante dal risultato della prova orale.

I docenti gestiranno con la massima intransigenza ogniirregolarit. L'esame un momento ufficialeche va affrontato con la massima seriet. Il voto finale NON negoziabile (pu solo essere rifiutato).

Nota: I lucidi non sostituiscono n il libro ditesto n la frequenza alle lezioni. In particolare,studiare su un libro permette di chiarire dettagli che potrebberoessere solo accennati (o mancare del tutto) nei lucidi. I lucidi sonosoggetti a modifiche frequenti.

Python: operazioni preliminari, IDLE e shell, interpreteFrontale22Python: commenti, valutazione espressioni, operazioni aritmetiche, variabili e operatori, funzioni predefinite, tipi di dato, stile di programmazioneFrontale33Python: sequenze e flow chart, controllo e selezione, blocchi di codice e indentazione, operatori logiciFrontale34Python: moduli, funzioni e numeri casuali, gestione variabili locali e globali, ambiente grafico turtle e relativi metodi, cicliFrontale35Python: stringhe, liste, tuple, insiemi e dizionariFrontale36Python: errori, test e debugging, file, dati e statisticaFrontale37Analisi asintotica di algoritmiFrontale38Analisi ed implementazione delle strutture dati con programmazione orientata agli oggetti mediante il linguaggio Python: pile, code e code doppie, liste concatenate, alberi, code prioritarie, mappe, tabelle di hash, alberi di ricercaFrontale16 Risultati di apprendimento (descrittori di Dublino)I risultati di apprendimento attesi sono definiti secondo i parametri europei descritti dai cinque descrittori di Dublino.

La base di conoscenza esposta in Algoritmi e strutture dati in Java, di Adam Drozdek, quella, ormai classica, delle strutture dati viste e introdotte prima come tipi di dati astratti, definite mediante la loro interfaccia, per poi passare alla loro realizzazione concreta in un linguaggio di programmazione e ad alcuni esempi significativi di un loro utilizzo in ambito progettuale, scientifico e ingegneristico.

Il linguaggio Java si rivela, leggendo il testo, particolarmente adatto alla didattica delle strutture dati, in quanto la definizione dei tipi di dati astratti si traduce in modo naturale nella definizione di una interfaccia in Java, e la realizzazione di una struttura dati concreta si traduce nella definizione di una classe che realizzi tale interfaccia.

Con il termine algoritmo si intende un metodo per la soluzione di un problema adatto a essere implementato sotto forma di programma.

Il termine deriva dal nome del matematico persiano Muhammad ibn Mūsa 'l-Khwārizmī.Un algoritmo un procedimento di azioni specificate per mezzo di regole precise e non ambigue, tali che possibile eseguire l'algoritmo "automaticamente", cio applicando le regole senza pensare al significato, oppure direttamente da una macchina.

Vi sono molti modi per descrivere un algoritmo (da quelli pi astratti a quelli pi particolareggiati).Un problema algoritmico , invece, costituito da:

L'enunciazione di un problema algoritmico non specifica come ottenere l'output dall'input, ma soltanto come verificare se la risposta corretta.

Come ottenere l'output dall'input costituisce la soluzione del problema: cio l'algoritmo.Dunque l'algoritmo una soluzione di un problema algoritmico.Lo stesso problema pu essere risolto da algoritmi diversi, ognuno di questi algoritmi ha una propria efficienza, data in termini di spazio e tempo occupati (vedi lezioni successive). importante notare che per risolvere un problema indispensabile conoscere le strutture (o i tipi) di dati che sono presenti, dunque lo studio degli algoritmi inseparabile dallo studio delle strutture-dati.

In particolare vale alla fine dell'intero ciclo.

Solitamente per ottenere un'invariante (che pu anche essere considerato una dettagliata descrizione della memoria) si pu indebolire la postcondizione del ciclo.

Ad esempio in un algoritmo per trovare il minimo la postcondizione : "Il risultato il minimo dell'intera sequenza". Un modo per ottenere l'invariante, indebolendo la postcondizione, riformulare la frase in questo modo: "La variabile min il minimo della sequenza, fino all'indice i escluso". Ovviamente, questo un esempio banale, ma l'invariante fondamentale in algoritmi pi complicati.

utile, quindi, prima di realizzare un ciclo (o una procedura), cercare l'invariante che faciliti il pi possibile la scrittura del codice. poco sensato (e spesso difficile) cercare un invariante dopo aver scritto il codice.

La ricerca binaria un algoritmo che risolve il problema della ricerca di un elemento all'interno di una lista ordinata.

Quindi rifacendoci allo schema precedente il problema si pu riassumere cos:

Questo problema potrebbe risolversi con una banale ricerca sequenziale: si controlla dal primo elemento in poi verificando che uguale o meno all'elemento d che si sta ricercando.Ma tale procedimento mediamente molto pi lento della ricerca binaria (vedi lezione successiva).

Per dare un'idea possiamo pensare di avere un dizionario della lingua italiana (che immaginiamo sia di circa 120000 lemmi) e voler cercare la parola "dicotomia". Seguendo la ricerca sequenziale dovremmo sfogliare circa 30000 lemmi prima di trovare quello giusto, mentre seguendo la ricerca binaria al massimo ne controlleremmo 17.

Quando cerchiamo una parola all'interno del vocabolario, solitamente utilizziamo una ricerca leggermente pi efficiente: basandoci sul fatto che le parole sono distribuite (approssimativamente) in modo omogeneo all'interno del vocabolario, se cerchiamo "Verit", apriamo il vocabolario verso la fine e non a met!

3a8082e126