ASD2 - Lecture Notes Summary

  • Informazioni Lezione

  • Formule di Horn

    • 3SAT per Formule di Horn

  • Algoritmo GreedyHorn

    • Esempio esecuzione

    • Analisi algoritmo

      • Correttezza

      • Complessità

    • Implementazione

  • Informazioni Lezione

  • Moltiplicazione tra Interi

    • Approccio Divide et Impera

    • Diminuire il Numero di Moltiplicazioni

    • Algoritmo di Karatsuba

  • Teorema Master per Algoritmi Divide et Impera

  • Moltiplicazione tra Matrici

  • Esponenziazione Modulare

    • Algoritmo Efficiente di tipo Divide et Impera

  • Massimo Comun Divisore

    • Correttezza

    • Complessità

  • Informazioni Lezione

  • Moltiplicazione Matriciale

  • Indipendent Set

  • Sottosequenza Palindroma

  • Informazioni Lezione

  • Riduzione Polinomiale

  • Problema 2-SAT

    • Definizione del problema

    • Esempi

    • Riduzione

      • Costruzione

      • Codice

  • Informazioni Lezione

  • Riduzioni per Dimostrare la Difficoltà di un Problema

  • SAT \(\preceq\) 3-SAT

    • \((g, X) \in \text{SAT} \implies f(g, X) \in \text{3-SAT}\)

    • \((g, X) \in \text{SAT} \impliedby f(g, X) \in \text{3-SAT}\)

  • 3-SAT \(\preceq\) IS

    • \((\varphi, X) \in \text{3-SAT} \implies f(\varphi, X) \in \text{IS}\)

    • \((\varphi, X) \in \text{3-SAT} \impliedby f(\varphi, X) \in \text{IS}\)

  • IS \(\preceq\) VC

  • VC \(\preceq\) IS

  • IS \(\preceq\) CLIQUE

  • Mappa delle Riduzioni

  • Informazioni Lezione

  • Ricerca Esaustiva Intelligente

  • Backtracking

    • Esempio SAT

  • Branch and Bound

  • Informazioni Lezione

  • Algoritmi Approssimanti

  • Load Balancing

    • Analisi 1 (Senza Ordinamento)

    • Analisi 2 (Con Ordinamento)

  • FPTAS

    • Knapsack

      • Algoritmo Dinamico

      • Designing a FTPAS for Knapsack

  • Approximation Gap

    • Travelling Salesman Problem (TSP)

    • Approssimare il TSP è NP-Hard