Materiale didattico aggiuntivo

Avviso

    Il contenuto di queste pagine è da considerarsi integrativo al testo adottato nei corsi di Algoritmi e Strutture Dati I. Il materiale elettronico in queste pagine non costituisce quindi una presentazione completa degli argomenti trattati e, onde evitare possibili violazioni del copyright ©, il materiale è ad accesso limitato e l'uso è esclusivamente riservato agli studenti del corso.

    È consentito il solo uso personale di queste pagine ed è fatto divieto di pubblicare queste pagine su altri siti WEB o server di qualunque tipo, essendo http://www.di.unipi.it/didadoc/asd1 il sito ufficiale del corso.

    La non accettazione dei principi suddetti implica automaticamente il divieto di proseguire nella consultazione di queste pagine.

Alcune delle pagine Web sono disponibili in formato:

Codice Java disponibile (in corso di definizione).

Animazioni di alcuni algoritmi visti a lezione:

    Istruzioni per l'uso del menù  di animazione (VCR):
  • Mantenere sempre attivata la finestra AWTapp per il controllo VCR.
  • Step (Ctrl-S): fai un singolo passo di animazione.
  • Multiple step/back (Ctrl-M): fai più passi di animazione.
  • Back (Ctrl-B): vai indietro di un singolo passo nell'animazione.
  • Reset (Ctrl-R): riparti dallo stato iniziale con l'animazione.
  • go Forward (Ctrl-F): esecuzione automatica di tutti i passi dell'animazione.
  • Go back (Ctrl-G): esecuzione all'indietro di tutti i passi dell'animazione.
  • Pause (Ctrl-P): sospendi l'esecuzione avviata nei due comandi precedenti.
  • rEsume (Ctrl-E): riprendi l'esecuzione sospesa.
  • speeD (Ctrl-D): imposta la velocità di esecuzione automatica.
  • PER USCIRE: chiudere semplicemente la finestra AWTapp del VCR; le altre finestre scompariranno.
  • Si consiglia di usare le versioni più recenti di Netscape e Internet Explorer abilitate a Java: se non supportano JDK1.1 possono dare problemi. Codice Java scritto da Pierluigi Crescenzi, Giancarlo Bongiovanni, Gaia Innocenti, Patrizia Pallai e Gabriella Rago © Copyright 1999.
    Per ulteriori animazioni di algoritmi e visualizzazione del loro codice Java, si vedano le pagine di Antonio Brogi.

Raccolta di esercizi
Si consiglia di svolgere gli esercizi senza guardare le soluzioni, fornite in alcuni casi. Provare quindi a risolvere gli esercizi varie volte prima di sbirciare le soluzioni. Gli asterischi denotano esercizi che presentano una difficoltà di risoluzione maggiore rispetto agli altri.

    Analisi di algoritmi e complessità
  1. confronto asintotico tra funzioni
  2. algoritmi con complessità prefissata 1
  3. algoritmi con complessità prefissata 2
  4. algoritmi con complessità prefissata 3
  5. due equazioni di ricorrenza
  6. analisi funzione ricorsiva 1
  7. analisi funzione ricorsiva 2
  8. analisi funzione ricorsiva 3
  9. analisi funzione ricorsiva 4
  10. analisi funzione ricorsiva 5
  11. analisi funzione ricorsiva 6
  12. analisi di algoritmo ricorsivo
  13. Strutture dati

  14. ricerca e cancellazione in una lista a due livelli
  15. mediano in una lista dinamica
  16. fusione di due liste ordinate
  17. cancellazione chiave più frequente
  18. proprietà di heap
  19. operazioni su heap 1
  20. operazioni su heap 2
  21. incremento valore di chiave
  22. proprietà di alberi
  23. algoritmi su alberi con complessità prefissata
  24. nonni di nodi
  25. alberi e cugini
  26. nodi a livello k
  27. alberi e vettori ordinati
  28. mediano e radice
  29. k-esimo elemento in un albero
  30. tipo di dato Insieme con gli AVL
  31. inserimento di chiavi in alberi AVL e B-alberi
  32. analisi hash
  33. scansione lineare
  34. scansione quadratica
  35. *cinque esercizi su tabelle hash
  36. dizionari
  37. insiemi
  38. rotazioni in alberi binari di ricerca
  39. costruzione di alberi AVL
  40. *split nei B-alberi
  41. Progetto di algoritmi

  42. anagrammi
  43. ricerca in un vettore
  44. tre esercizi su vettori
  45. due esercizi su minimi e massimi
  46. *mediano randomizzato
  47. mediano e k-esimo elemento
  48. esecuzione di vari ordinamenti
  49. heapsort
  50. buildheap
  51. analisi mergesort/quicksort
  52. moltiplicazione di polinomi
  53. ricerca di sequenze
  54. conteggio di 0 e 1
  55. rappresentazione di grafi
  56. labirinti e grafi
  57. rappresentazione di grafi orientati
  58. pozzi e grafi
  59. visite DFS e BFS
  60. visita DFS su grafo orientato
  61. archi entranti
  62. vertici indipendenti
  63. cricca di vertici
  64. direzione di archi invertita
  65. cammini nei grafi
  66. Problemi computazionalmente difficili

  67. procedura non-deterministica
  68. commesso viaggiatore