Analisi delle strutture dati e degli algoritmi con Python (edizione 2)

📚 Riepilogo del contenuto

Questo libro è un classico testo sull'implementazione di strutture dati e algoritmi in Python. Copre il ripasso delle basi di Python, l'analisi degli algoritmi (notazione O grande), le strutture dati fondamentali (stack, code, liste), la ricorsione, la ricerca e il ordinamento, gli algoritmi sugli alberi e sui grafi. Attraverso elenchi di codice pratici, aiuta i lettori a comprendere come implementare in modo efficiente diverse astrazioni di tipi di dati tramite Python.

Solo chi padroneggia profondamente strutture dati ed algoritmi può veramente dominare Python.

Autore: Bradley Miller (Professore Emerito di Scienze dell'Informazione all'Università di Luther, USA), David Ranum (Ingegnere di software cognitivo presso IBM Watson)

Ringraziamenti: Grazie ai colleghi Steve Hubbard per i numerosi feedback forniti per la prima edizione e per i nuovi materiali aggiunti nella nuova versione, nonché a tutti coloro che hanno segnalato errori e offerto suggerimenti via email. Ringraziamo anche Mary, Bob e altri dipendenti del caffè Java John's a Decora City, che ci hanno permesso di diventare "autori residenti" durante le nostre vacanze. Inoltre, grazie a tutti i membri di Franklin, Beedle & Associates (in particolare Jim Leisy e Tom Sumner) per la piacevole collaborazione. Infine, ringraziamo specialmente le nostre mogli, Jane Miller e Brenda Ranum, per il loro amore e sostegno che hanno reso possibile la realizzazione di questo libro.

🎯 Obiettivi di apprendimento

1. Comprendere il rapporto tra scienza dell'informazione, algoritmi e programmazione, e padroneggiare i concetti di tipo di dato astratto (ADT) e nascosta informazione.
2. Utilizzare con sicurezza i tipi di dati integrati di Python (liste, tuple, insiemi, dizionari) e le strutture di controllo (cicli, condizioni, gestione eccezioni).
3. Padronanza dei concetti fondamentali della programmazione orientata agli oggetti in Python: definizione di classi, metodi costruttori, sovraccarico di operatori (ad esempio addizione di frazioni), applicazione dell'algoritmo euclideo e distinzione tra uguaglianza profonda e superficiale.
4. Confronto tra diverse soluzioni algoritmiche: essere in grado di spiegare quattro approcci per rilevare parole anagrammatiche (conteggio, ordinamento, forza bruta, conteggio caratteri) e i rispettivi tempi di complessità.
5. Misurazione della performance dei container in Python: conoscere l'efficienza asintotica (O grande) delle operazioni principali su liste e dizionari in Python, e distinguere le differenze prestazionali tra pop() e pop(i).
6. Capacità di validare le prestazioni: saper utilizzare il modulo timeit per progettare esperimenti che verifichino la coerenza tra complessità teorica e tempo di esecuzione reale.
7. Comprendere e distinguere le caratteristiche logiche delle strutture dati lineari (stack, code, deque, liste).
8. Essere in grado di implementare stack, code e deque personalizzati usando i tipi di dati basilari di Python (come le liste).
9. Padronanza delle applicazioni dello stack nel trattamento di espressioni (conversione da notazione infix a postfix, valutazione di espressioni postfix) e delle code nella simulazione di sistemi (simulazione di stampante).
10. Padronanza dei tre principi fondamentali della ricorsione: identificare correttamente e scrivere funzioni ricorsive che includano un caso base, una progressione verso lo stato base e una chiamata ricorsiva.

🔹 Lezione 1: Fondamenti di programmazione in Python e astrazione orientata agli oggetti

Panoramica: Questo modulo didattico ha lo scopo di guidare gli studenti dalla teoria di base della scienza dell'informazione alla pratica della programmazione in Python. Si inizia con una definizione chiara dei concetti fondamentali di scienza dell'informazione, algoritmi e tipi di dato astratto (ADT), quindi si approfondisce l'uso dei tipi di dati integrati di Python, delle strutture di controllo e della gestione delle eccezioni. Il modulo si conclude con la creazione della classe Fraction e di una gerarchia di ereditarietà per "porte logiche", mostrando così il potere della programmazione orientata agli oggetti (OOP) nell'astrazione di processi e dati.

Risultati dell'apprendimento:

• Comprendere il rapporto tra scienza dell'informazione, algoritmi e programmazione, e padroneggiare i concetti di tipo di dato astratto (ADT) e nascosta informazione.
• Utilizzare con sicurezza i tipi di dati integrati di Python (liste, tuple, insiemi, dizionari) e le strutture di controllo (cicli, condizioni, gestione eccezioni).
• Padronanza dei concetti fondamentali della programmazione orientata agli oggetti in Python: definizione di classi, metodi costruttori, sovraccarico di operatori (ad esempio addizione di frazioni), applicazione dell'algoritmo euclideo e distinzione tra uguaglianza profonda e superficiale.

🔹 Lezione 2: Analisi degli algoritmi e prestazioni dei container in Python

Panoramica: Questa lezione approfondisce come utilizzare la notazione O grande per valutare l'efficienza degli algoritmi, mostrando attraverso l'esempio del rilevamento di anagrammi come si passa da una complessità O(n!) a O(n) attraverso diverse strategie. Inoltre, analizza quantitativamente le prestazioni delle operazioni principali sulle strutture dati fondamentali di Python (liste e dizionari), per aiutare gli sviluppatori a scegliere in modo ottimale i container e a progettare algoritmi efficaci.

Risultati dell'apprendimento:

• Confronto tra diverse soluzioni algoritmiche: essere in grado di spiegare quattro approcci per rilevare parole anagrammatiche (conteggio, ordinamento, forza bruta, conteggio caratteri) e i rispettivi tempi di complessità.
• Misurazione della performance dei container in Python: conoscere l'efficienza asintotica (O grande) delle operazioni principali su liste e dizionari in Python, e distinguere le differenze prestazionali tra pop() e pop(i).
• Capacità di validare le prestazioni: saper utilizzare il modulo timeit per progettare esperimenti che verifichino la coerenza tra complessità teorica e tempo di esecuzione reale.

🔹 Lezione 3: Strutture lineari di base: stack, code e liste

Panoramica: Questa lezione approfondisce quattro strutture dati lineari fondamentali: stack (pila), code (coda), deque (coda doppia) e liste. Il principio centrale delle strutture lineari è mantenere un ordine relativo tra gli elementi; la differenza principale sta nel modo in cui gli elementi vengono inseriti e rimossi. Implementando queste astrazioni di tipi di dato (ADT) in Python, gli studenti impareranno ad applicare principi come LIFO (ultimo entrato, primo uscito) e FIFO (primo entrato, primo uscito) per risolvere problemi algoritmici reali, come conversione di espressioni, simulazione di sistemi e gestione della memoria in liste concatenate.

Risultati dell'apprendimento:

• Comprendere e distinguere le caratteristiche logiche delle strutture dati lineari (stack, code, deque, liste).
• Essere in grado di implementare stack, code e deque personalizzati usando i tipi di dati basilari di Python (come le liste).
• Padronanza delle applicazioni dello stack nel trattamento di espressioni (conversione da notazione infix a postfix, valutazione di espressioni postfix) e delle code nella simulazione di sistemi (simulazione di stampante).

🔹 Lezione 4: Principi degli algoritmi ricorsivi e introduzione alla programmazione dinamica

Panoramica: Questa lezione approfondisce i principi fondamentali degli algoritmi ricorsivi, partendo dai tre principi base della ricorsione, e illustrandoli con esempi come conversione numerica, geometria frattale e classici rompicapo (Torre di Hanoi e labirinto), rivelando così il meccanismo sottostante delle chiamate ricorsive — lo stack di attivazione. Alla fine, viene introdotto il concetto di programmazione dinamica (Dynamic Programming), mostrando come tecnologie di memorizzazione possano eliminare calcoli ripetuti nelle funzioni ricorsive, portando a un miglioramento qualitativo dell'efficienza algoritmica.

Risultati dell'apprendimento:

• Padronanza dei tre principi fondamentali della ricorsione: identificare correttamente e scrivere funzioni ricorsive che includano un caso base, una progressione verso lo stato base e una chiamata ricorsiva.
• Comprendere il meccanismo esecutivo interno: capire come lo stack di chiamata di Python (Stack Frame) gestisca variabili locali e percorsi di ritorno durante la ricorsione.
• Capacità di modellare problemi complessi: saper utilizzare la ricorsione e il backtracking per risolvere problemi non lineari come la Torre di Hanoi e il percorso in un labirinto.

🔹 Lezione 5: Tecniche di ricerca, hashing e algoritmi di ordinamento

Panoramica: Questo modulo si concentra sulle tecniche fondamentali di elaborazione dei dati nella scienza dell'informazione: ricerca, hashing (funzionamento hash) e ordinamento. Copre dalla ricerca sequenziale alla ricerca binaria, approfondisce i principi di costruzione delle tabelle hash, i metodi per gestire i conflitti e l'implementazione del tipo di dato astratto Map. Inoltre, analizza dettagliatamente l'algoritmo di ordinamento bubble sort, shell sort e merge sort dal punto di vista logico e prestazionale.

Risultati dell'apprendimento:

• Comprendere e confrontare scenari applicativi e complessità temporale tra ricerca sequenziale e ricerca binaria (O(n) vs O(\log n)).
• Padronanza della progettazione di funzioni hash (metodo della somma parziale, metodo del quadrato centrale) e dei meccanismi di gestione dei conflitti (sondaggio lineare, sondaggio quadratico, catena).
• Essere in grado di simulare manualmente e implementare in codice bubble sort, shell sort e merge sort, comprendendo l'applicazione della strategia divide et impera nell'ordinamento.

🔹 Lezione 6: Strutture ad albero: heap binario, alberi di ricerca e alberi bilanciati (AVL)

Panoramica: Questa lezione approfondisce una delle strutture dati più centrali nella scienza dell'informazione: gli alberi. Partiamo dalle definizioni base e dall'implementazione di alberi binari, per poi avanzare verso applicazioni avanzate come gli alberi di espressione e i loro metodi di traversamento. Successivamente, studieremo due varianti altamente efficienti: l'heap binario, utile per le code di priorità, e l'albero binario di ricerca (BST), ideale per ricerche efficienti. Infine, esploreremo gli alberi AVL, che mantengono l'equilibrio tramite rotazioni, risolvendo il problema di degradazione delle prestazioni nei casi peggiori degli alberi di ricerca.

Risultati dell'apprendimento:

• Poter definire con precisione i termini chiave degli alberi (radice, arco, cammino, altezza) e descrivere la proprietà ricorsiva degli alberi binari.
• Padronanza degli algoritmi principali per implementare heap binari, alberi di ricerca binari e alberi AVL in Python (inserimento, cancellazione, rotazioni, ri-equilibrio).
• Essere in grado di eseguire e interpretare tre algoritmi di traversamento degli alberi, e utilizzare alberi di parsing per gestire espressioni matematiche.

🔹 Lezione 7: Algoritmi sulla teoria dei grafi: ricerca, cammini minimi e albero di copertura minimo

Panoramica: Questa lezione approfondisce la teoria dei grafi e le sue implementazioni efficienti in Python. Copre il tipo di dato astratto per i grafi (matrice di adiacenza e lista di adiacenza), algoritmi di ricerca di base (BFS e DFS) e le loro applicazioni classiche. Alla fine, si affrontano algoritmi per grafi pesati: cammini minimi (Dijkstra) e albero di copertura minimo (Prim).

Risultati dell'apprendimento:

• Comprendere e confrontare le due principali rappresentazioni dei grafi (matrice di adiacenza e lista di adiacenza) in termini di prestazioni e scenari applicativi.
• Padronanza degli algoritmi BFS e DFS, e capacità di risolvere problemi di ricerca di cammini e visita completa.
• Essere in grado di applicare algoritmi sui grafi per risolvere problemi complessi come dipendenze logiche (ordinamento topologico) e connettività di reti (componenti fortemente connesse, albero di copertura minimo).

🔹 Lezione 8: Ripasso tematico: crittografia RSA, liste saltanti e quantizzazione con octree

Panoramica: Questa lezione esplora il passaggio da strutture dati semplici a algoritmi complessi nella scienza dell'informazione. Include l'implementazione interna delle liste in Python (ArrayList) con analisi ammortizzata, algoritmi ricorsivi in teoria dei numeri per supportare la crittografia RSA, la costruzione di liste saltanti per aumentare l'efficienza della ricerca nei dizionari, e il principio di quantizzazione dei colori nelle immagini digitali tramite octree.

Risultati dell'apprendimento:

• Comprendere l'organizzazione della memoria di ArrayList e la derivazione matematica dell'analisi ammortizzata (Amortized Analysis).
• Padronanza dei principi matematici fondamentali della crittografia RSA, inclusi il teorema dell'omotetia, residui modulari e l'algoritmo euclideo esteso.
• Essere in grado di descrivere la struttura a livelli delle liste saltanti, il processo probabilistico di costruzione e l'efficienza di ricerca O(\log n).