Algoritmi e Complessità

Appunti di Algoritmi e Complessità 2023/2024 del corso di laurea magistrale LM-18 in Informatica UniCT, by Darakuu. 

Non intendono e non vogliono sostituire libri, slide ufficiali e quant’altro. 

Questa pagina funge da indice.

Idealmente, vorrei:

• Fare io tutti gli esempi e i grafici/immagini;
• Sistemare alcune dimostrazioni o parti lacunose;
• Aggiungere risoluzioni di esercizi scritte bene bene in Latex.
• Infine (ma questo è utopico), aggiungere con citazioni stralci dal Cormen.

Prima Parte

• Analisi Ammortizzata:

  • Metodo dell’Aggregazione
  • Metodo degli Accantonamenti
  • Metodo del Potenziale

• Strutture Dati:

  • Splay Tree
  • B-Tree
  • Alberi Binomiali
  • Mergeable Heaps
  • Union-Find

• Notazione di Knuth

• Funzione di Ackermann

• Schema Esercizi Prima Parte

Seconda Parte

• Move To Front

• Minimum Spanning Tree

  • MST-Segnatura
  • MST-Reduce
  • MST-Clustering

• Cammini Minimi

  • Algoritmi per calcolo distanza e dei cammini minimi da una data sorgente
  • Cammini minimi tra tutte le coppie di nodi
  • Superare la complexity barrier

• Reti di Flusso

  • Edge Connectivity

• Schema Esercizi Seconda Parte

Changelog:

Data	Changes
2024-01-27	Major refactoring del sito
2024-01-27	Continua lavoro su shortest path, introduce reti di flusso
2024-01-26	Inizio lavoro su shortest path
2024-01-25	Aggiunge Segnatura, Reduce, Clustering (in wip)
2024-01-24	Aggiunto Prim con Esercizio
2024-01-23	Aggiunta pagina MST, Boruska, Kruskal
2024-01-20	Aggiunto changelog e indice seconda parte
2023-12-19	Ultimo commit per prima prova