Libro di testo su algoritmi e strutture dati
Chissà se qualcuno mi può consigliare un buon testo che tratti di algoritmi e strutture dati. Mi serve per la preparazione dell'esame di Informatica 2 (prevede la programmazione in C++).
Grazie.
Grazie.
Risposte
Mi hanno parlato bene del testo di Pilu Crescenzi - ma non credo introduca il C++ (che c'entra poi?)
http://www.algoritmica.org/
PS. Che roba è "Informatica 2"?!? C'è un'informatica 1? Che CdL?
http://www.algoritmica.org/
PS. Che roba è "Informatica 2"?!? C'è un'informatica 1? Che CdL?
"Rggb":
Mi hanno parlato bene del testo di Pilu Crescenzi - ma non credo introduca il C++ (che c'entra poi?)
http://www.algoritmica.org/
PS. Che roba è "Informatica 2"?!? C'è un'informatica 1? Che CdL?
Sono iscritto alla triennale di Matematica a Torino. Siccome il mio piano di studi è ancora in base al DM509, all'epoca (fino a 3 anni fa) il corso di studi prevedeva Informatica I (1° anno) e Informatica II (2° anno).
Ma ti serve un libro su algoritmi e strutture dati, sulla loro implementazione in C++ o un'introduzione alla programmazione C++? Perché un libro che faccia tutte tre queste cose non credo esista e se esistesse ne diffiderei.
Mi sono espresso male. Il libro che chiedo di consigliarmi deve riguardare algoritmi e strutture dati. L'accenno alla programmazione in C++ era riferito alla prova d'esame che prevederà per l'appunto la scittura di programmi in C++ sulla base di quelli visti a lezione (a cui io non ho potuto partecipare).
Il più famoso e utilizzato testo per un'introduzione agli algoritmi e strutture dati è sicuramente il Cormen-Leiserson-Rivest-Stein.
Tratta una quantità molto elevata di algoritmi (di ordinamento, su grafi,...), di strutture dati (alberi, heap, tabelle hash,...) nonché le tecniche di programmazione più utilizzate (programmazione dinamica, divide et impera, algoritmi greedy ecc.).
Vengono anche trattate le nozioni matematiche fondamentali che è necessario conoscere per sapere analizzare un algoritmo (risoluzione di sommatorie, equazioni di ricorrenza, funzioni generatrici,...).
È sostanzialmente però un libro sull'analisi degli algoritmi fondamentali piuttosto che sulla costruzione di nuovi.
Ho sentito parlare molto bene anche di questo, però non l'ho mai letto, solo sfogliato.
Tratta una quantità molto elevata di algoritmi (di ordinamento, su grafi,...), di strutture dati (alberi, heap, tabelle hash,...) nonché le tecniche di programmazione più utilizzate (programmazione dinamica, divide et impera, algoritmi greedy ecc.).
Vengono anche trattate le nozioni matematiche fondamentali che è necessario conoscere per sapere analizzare un algoritmo (risoluzione di sommatorie, equazioni di ricorrenza, funzioni generatrici,...).
È sostanzialmente però un libro sull'analisi degli algoritmi fondamentali piuttosto che sulla costruzione di nuovi.
Ho sentito parlare molto bene anche di questo, però non l'ho mai letto, solo sfogliato.
"Deckard":
Il più famoso e utilizzato testo per un'introduzione agli algoritmi e strutture dati è sicuramente il Cormen-Leiserson-Rivest-Stein.
Tratta una quantità molto elevata di algoritmi (di ordinamento, su grafi,...), di strutture dati (alberi, heap, tabelle hash,...) nonché le tecniche di programmazione più utilizzate (programmazione dinamica, divide et impera, algoritmi greedy ecc.).
Vengono anche trattate le nozioni matematiche fondamentali che è necessario conoscere per sapere analizzare un algoritmo (risoluzione di sommatorie, equazioni di ricorrenza, funzioni generatrici,...).
È sostanzialmente però un libro sull'analisi degli algoritmi fondamentali piuttosto che sulla costruzione di nuovi.
Ho sentito parlare molto bene anche di questo, però non l'ho mai letto, solo sfogliato.
Siccome sto anche io a Torino sarò molto sincero... Se sono 3 anni che deve dare un esame come quello il libro che hai consigliato è tanto inutile quanto dare il Lang ad uno che non capisce il Warner in geometria differenziale... In pratica lo confondi e basta.
A mio avviso dovresti comprendere esattamente cosa non capisci dell'informatica perché le richieste dell'esame sono piuttosto basse. A parte la conoscenza del linguaggio si tratta soltanto di comprendere come risolvere un problema avendo particolari restrizioni. Conoscere degli algoritmi molto avanzati serve a poco. Devi programmare e vedere programmi scritti bene.
io sto usando quel libro per prepararmi alla fase nazionale delle olimpiadi di informatica... devo dire che secondo me è molto chiaro e vasto (nel senso che ci trovi un po' di tutto) anche se forse a volte è un po' troppo dispersivo e pedante. Ciònonostante tratta gli algoritmi in modo concettuale, e quindi dà per scontata una padronanza quantomeno decente di un linguaggio di programmazione
Ti posso consigliare un libro che è diretto a diversi livelli.
"Algoritmi e Strutture Dati, 2° ed" di Alan Bertossi e A.Montresor
Usa uno pseudo-codice, che è ovviamente puoi integrare nel tuo codice preferito (gli algoritmi si scrivono in pseudo-codice, ma sono la stessa cosa di un linguaggio qualsiasi).
E' molto discorsivo, ma non manca di formalismo nei punti giusti, è pieno di esercizi e problemi, con relative soluzioni (nel libro di Corner le soluzioni te le scordi).
Io lo ho usato, è anche divertente l'autore
Il Corner, oltre mancare le soluzioni, è che usa l'approccio Pro (professional americano), cioè un mattone. Va bene per un corso di algoritmi avanzati.
Invece ti consiglio il libro di Bertossi, chiaro, semplice e valido per un corso di Algoritmi e strutture dati.
Ciao
"Algoritmi e Strutture Dati, 2° ed" di Alan Bertossi e A.Montresor
Usa uno pseudo-codice, che è ovviamente puoi integrare nel tuo codice preferito (gli algoritmi si scrivono in pseudo-codice, ma sono la stessa cosa di un linguaggio qualsiasi).
E' molto discorsivo, ma non manca di formalismo nei punti giusti, è pieno di esercizi e problemi, con relative soluzioni (nel libro di Corner le soluzioni te le scordi).
Io lo ho usato, è anche divertente l'autore
Il Corner, oltre mancare le soluzioni, è che usa l'approccio Pro (professional americano), cioè un mattone. Va bene per un corso di algoritmi avanzati.
Invece ti consiglio il libro di Bertossi, chiaro, semplice e valido per un corso di Algoritmi e strutture dati.
Ciao
Il programma del corso di informatica II a Torino (ormai disattivato) prevedeva il seguente programma di studi:
Come si può notare il corso tratta solo una minima parte del contenuto di un normale libro di algoritmi e lo fa in modo abbastanza superficiale. Vengono inoltre insegnate anche alcune nozioni legate al linguaggio C++ che non hanno valore generale (non sono cioè facilmente trasportabili ad altri linguaggi). Secondo me, è inutile studiare da un libro di algoritmi avanzati ai fini di questo esame. Può essere utile per approfondimenti, ma se il tuo scopo è solo quello di passare l'esame e la programmazione non ti interessa è sufficiente leggerti le dispense e cercare di svolgere gli esercizi (gli esercizi all'esame sono analoghi).
P.S. Siccome non hai frequentato l'esame e non puoi ricevere commenti e correzioni sugli esercizi,
ricordati che puoi sempre chiedere consiglio nel forum.
Programma d'esame di Informatica 2
Astrazione procedurale: Astrazione ed organizzazione di un programma. Le procedure. Specifica con pre e post condizioni.
Iterazione. Il metodo delle asserzioni. Invarianti di ciclo. Contatori ed accumulatori.
Ricorsione. Ricorsione lineare e ad albero. Trasformazione di ricorsioni lineari in ricorsioni di coda. Simulazione della ricorsione mediante una pila. Ricorsione induttiva o ben fondata. Tecniche di programmazione ricorsiva: divide et impera (Merge Sort).
Complessità computazionale. Confronto asintotico tra funzioni. Classi O-grande. Proprietà delle classi e algebra di O-grande.Altre nozioni asintotiche: Omega e Theta. Relazioni di ricorrenza. Confini inferiori alla complessità di problemi: il sorting.
Memoria dinamica. Puntatori. Dereferenziazione. L'operatore indirizzo. I riferimenti. Vettori e puntatori. Passaggio di parametri per valore, riferimento e puntatore. Allocazione dinamica della memoria. Allocazione di un vettore. I record (strutture): loro allocazione ed accesso. Definizione di nuovi tipi: il tipo Vettore e Matrice. Deallocazione.
Le strutture informative. Strutture dati. Le liste: definizione, rappresentazione, algoritmi iterativi e ricorsivi sulle liste. Alberi: definizione, rappresentazione, algoritmi elementari. DFS e BFS.
ADT e classi. Nozione di "tipo di dato astratto". Specifica sintattica e semantica. Astrazione ed incapsulamento.Strutture dati come realizzazione di ADT: primitive d'accesso, programmazione delle funzioni base, invariante di struttura. Gli oggetti: stato e funzioni membro (metodi). Le classi. Istanziazione di una classe: il costruttore ed il distruttore. Oggetti statici e dinamici. Il costruttore di copia. Esempi: razionali, polinomi, matrici.
Polimorfismo. Cenni all'ereditarietà, alle classi astratte ed ai modelli (template).
Come si può notare il corso tratta solo una minima parte del contenuto di un normale libro di algoritmi e lo fa in modo abbastanza superficiale. Vengono inoltre insegnate anche alcune nozioni legate al linguaggio C++ che non hanno valore generale (non sono cioè facilmente trasportabili ad altri linguaggi). Secondo me, è inutile studiare da un libro di algoritmi avanzati ai fini di questo esame. Può essere utile per approfondimenti, ma se il tuo scopo è solo quello di passare l'esame e la programmazione non ti interessa è sufficiente leggerti le dispense e cercare di svolgere gli esercizi (gli esercizi all'esame sono analoghi).
P.S. Siccome non hai frequentato l'esame e non puoi ricevere commenti e correzioni sugli esercizi,
ricordati che puoi sempre chiedere consiglio nel forum.
Io l'avevo consigliato perché risponde alla descrizione "un buon testo che tratti di algoritmi e strutture dati". Poi la sua richiesta era un po' generica, pensavo si trattasse di un classico corso su algoritmi e strutture dati. Per il quale consiglierei fermamente il Cormen.
Mmm... non sono d'accordo. Sinceramente io il Cormen l'ho trovato un'ottima introduzione agli algoritmi. Non è mica necessario leggerlo tutto, capitoli come quelli sugli heap di Fibonacci e sull'NP-completezza non verranno svolti in un corso introduttivo. Però a parte singoli capitoli, l'impostazione generale è, come da titolo, quella di un'introduzione agli algoritmi. Che sia un mattone non lo metto in dubbio, ma solo a causa della sua lunghezza. Sarà che i libri italiani ormai li scarto a prescindere (preferisco l'asciuttezza dell'inglese nei testi scientifici) e quindi sono ormai familiare a questo approccio "Pro" che sinceramente non avevo mai pensato nemmeno esistesse
Detto questo poi ognuno ha i suoi bisogni e le sue preferenze. Le recensioni su Amazon e l'anteprima su Google Books sono fatte apposta per capire se un libro è quello che fa al caso nostro.
EDIT: stavo per postare ed ho letto ora la risposta di apatriarca: visto il programma del corso sconsiglierei anch'io il Cormen, ma più che altro perché di algoritmi e strutture dati c'è solo un assaggio nel corso.
Il Corner, oltre mancare le soluzioni, è che usa l'approccio Pro (professional americano), cioè un mattone. Va bene per un corso di algoritmi avanzati.
Mmm... non sono d'accordo. Sinceramente io il Cormen l'ho trovato un'ottima introduzione agli algoritmi. Non è mica necessario leggerlo tutto, capitoli come quelli sugli heap di Fibonacci e sull'NP-completezza non verranno svolti in un corso introduttivo. Però a parte singoli capitoli, l'impostazione generale è, come da titolo, quella di un'introduzione agli algoritmi. Che sia un mattone non lo metto in dubbio, ma solo a causa della sua lunghezza. Sarà che i libri italiani ormai li scarto a prescindere (preferisco l'asciuttezza dell'inglese nei testi scientifici) e quindi sono ormai familiare a questo approccio "Pro" che sinceramente non avevo mai pensato nemmeno esistesse
Detto questo poi ognuno ha i suoi bisogni e le sue preferenze. Le recensioni su Amazon e l'anteprima su Google Books sono fatte apposta per capire se un libro è quello che fa al caso nostro.
EDIT: stavo per postare ed ho letto ora la risposta di apatriarca: visto il programma del corso sconsiglierei anch'io il Cormen, ma più che altro perché di algoritmi e strutture dati c'è solo un assaggio nel corso.
Ringrazio tutti per i suggerimenti. Solo qualche precisazione:
non so se ho delle difficoltà particolare o se c'è qualcosa che non capisco di Informatica; l'esame non è che non riesco a darlo da tre anni, ma ho dato altri esami (lavorando 9 ore al giorno non riesco a stare dietro a tutti gli esami come dovrei fare) e questo mi è rimasto indietro (nel frattempo hanno disattivato il corso). Allora ho chiesto consiglio per avere un supporto oltre le dispense del professore. Mi sembra comunque di aver capito che un testo di algoritmi e strutture dati vada oltre quanto richiesto dal corso. Magari faccio un salto in biblioteca per farmi un'idea.
Ancora grazie a tutti per l'aiuto che potrete darmi.
Max
"vict85":
Siccome sto anche io a Torino sarò molto sincero... Se sono 3 anni che deve dare un esame come quello il libro che hai consigliato è tanto inutile quanto dare il Lang ad uno che non capisce il Warner in geometria differenziale... In pratica lo confondi e basta.
A mio avviso dovresti comprendere esattamente cosa non capisci dell'informatica perché le richieste dell'esame sono piuttosto basse. A parte la conoscenza del linguaggio si tratta soltanto di comprendere come risolvere un problema avendo particolari restrizioni. Conoscere degli algoritmi molto avanzati serve a poco. Devi programmare e vedere programmi scritti bene.
non so se ho delle difficoltà particolare o se c'è qualcosa che non capisco di Informatica; l'esame non è che non riesco a darlo da tre anni, ma ho dato altri esami (lavorando 9 ore al giorno non riesco a stare dietro a tutti gli esami come dovrei fare) e questo mi è rimasto indietro (nel frattempo hanno disattivato il corso). Allora ho chiesto consiglio per avere un supporto oltre le dispense del professore. Mi sembra comunque di aver capito che un testo di algoritmi e strutture dati vada oltre quanto richiesto dal corso. Magari faccio un salto in biblioteca per farmi un'idea.
"apatriarca":
P.S. Siccome non hai frequentato l'esame e non puoi ricevere commenti e correzioni sugli esercizi,
Ancora grazie a tutti per l'aiuto che potrete darmi.
Max
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo