Autore Topic: Diario lezioni  (Letto 1056 volte)

0 Utenti e 1 Visitatore stanno visualizzando questo topic.

Offline Mithrandir

  • Maestro Geek
  • *
  • *
  • *
  • Post: 1.157
  • Reputazione: 44
  • Sesso: Maschio
  • Battlemage
Diario lezioni
« il: 18 Ottobre 2010, 21:45:11 »
Come discusso oggi a lezione, inauguro questo topic che consisterà in un diario degli argomenti trattati nelle lezioni del corso.
Per tenerci aggiornati... almeno ora che gli argomenti invitano a "saltare".

Lun 18 ott - 17.30
  • Esempio di un modello min-abs (Just-In-Time) e sua trasformazione in forma standard
  • Introduzione ai vincoli logici
    • Significato e utilizzo pratico
    • Implementazione mediante variabili booleane e vincoli con Big M
Spoiler (click to show/hide)
Gandalf? Yes... that was what they used to call me. Gandalf the Grey. That was my name.
I am Gandalf the White. And I come back to you now - at the turn of the tide.


Offline Cosmos

  • Signore dei Geek
  • *
  • *
  • *
  • Post: 1.493
  • Reputazione: 48
  • Sesso: Maschio
  • Is this the end?
Re:Diario lezioni
« Risposta #1 il: 19 Ottobre 2010, 16:40:06 »
Mar 19 ott - 13.00
  • Esempio svolto di modello con vincoli logici (Agenzia Pubblicitaria)
  • Esempio di modello tratto da tema d'esame di Programmazione Matematica (20-02-2010), che sarà, a breve, reso disponibile sul portale

La lezione di Ven 22 sarà tenuta dall'esercitatore, che inizierà a fare esercizi di modellazione.
« Ultima modifica: 19 Ottobre 2010, 16:43:43 da Cosmos »
Spoiler: XKCD (click to show/hide)



Regola Aurea: Qualsiasi calcolo ridicolmente complesso a vedersi, ed ancor più complesso a farsi, porterà certamente ad un risultato nullo...

Corollario: Se il risultato non si annulla, sarà 2\pi

Se X è un insieme non vuoto su cui è definita una relazione d'ordine parziale tale che ogni sua catena possiede un maggiorante, allora contiene almeno un elemento massimale. Chiaro no?

In trepidante attesa della pubblicazione di "Orchi, Antilopi e Calamari - Vol. I"

Offline Raptor

  • Utente Fidato
  • *
  • *
  • *
  • Post: 489
  • Reputazione: 11
  • Sesso: Maschio
    • rpt@altervista
Re:Diario lezioni
« Risposta #2 il: 22 Ottobre 2010, 13:16:46 »
Esercitazione con Guido Perboli.

Ven 22 ott - 13.00
  • Esempi di problemi di ricerca operativa (produzione industriale, schedulazione di jobs)
  • Carrellata di esempi in cui credo di migliorare ma peggioro il risultato: flow shop paradox, belady's anomaly, graham's multiprocessing, transportation paradox, braess paradox
  • MODELLO 1: un problema molto basilare di acquisto prodotti
  • (battuta sugli ingegneri: un ingegnere per appendere un quadro fa un sistema per appendere qualsiasi cosa e poi lo usa per appendere il quadro)
  • cenno teorico al problema dello zaino
  • MODELLO 2: esercizio di modellazione su un problema di produzione di pacchetti di dolci. qual è la proporzione perfetta per minimizzare i costi e produrre almeno 10000 pacchetti?
  • MODELLO 3: esercizio di modellazione su problema di assunzioni annuali
  • cenni ai modelli multiperiodali e ai problemi per effetto di bordo
  • MODELLO 4: da fare a casa (vedi slide)
« Ultima modifica: 22 Ottobre 2010, 15:46:12 da Raptor »

Offline Mithrandir

  • Maestro Geek
  • *
  • *
  • *
  • Post: 1.157
  • Reputazione: 44
  • Sesso: Maschio
  • Battlemage
Re:Diario lezioni
« Risposta #3 il: 26 Ottobre 2010, 18:42:37 »
Aggiornamento.

Lun 25 ott - 17.30
  • Definizione "formale" di problema, istanza di un problema  e algoritmo.
  • Complessità di un algoritmo come metodo di classificazione
    • Complessità di caso peggiore O\left\(g(n)\right\)
    • Complessità di caso migliore \Omega\left\(g(n)\right\)
  • Esempi di calcolo di complessità:
    • Ricerca lineare
    • Ricerca binaria
    • Ordinamento (selection sort)
  • Definizione di Complessità di problema

Mar 26 ott - 13.00
  • Analisi del problema MST (Minimum Spanning Tree) e dell'algoritmo di Prim
  • Classi di problemi
    • \mathcal{P} polinomiale
    • \mathcal{NP} non deterministico polinomiale
  • Introduzione dei concetti di Istanza-SI e Certificato

Venerdì non ci sarà esercitazione, ma lezione.
Spoiler (click to show/hide)
Gandalf? Yes... that was what they used to call me. Gandalf the Grey. That was my name.
I am Gandalf the White. And I come back to you now - at the turn of the tide.


Offline Cosmos

  • Signore dei Geek
  • *
  • *
  • *
  • Post: 1.493
  • Reputazione: 48
  • Sesso: Maschio
  • Is this the end?
Re:Diario lezioni
« Risposta #4 il: 29 Ottobre 2010, 16:37:42 »
Ven 29 ott - 13.00
  • Definizione di Riducibilità
  • Esempio di Riducibilità: Da SUBSET SUM a KNAPSACK 0/1
  • Problema: Soddisfacibilità (SAT)
  • Classi di problemi
    • \mathcal{NP}-completi
    • \mathcal{NP}-hard
  • Classi computazionali spaziali
    • \mathcal{P}-space
  • Esercizi di modellazione (in programma, ma non svolti per mancanza di tempo) disponibili sulle slide

Mar 2 Nov - 13.00
  • Esercitazione: Modelli
    • Sequenziamento del DNA
    • Agenzia Pubblicitaria
    • Investimenti
    • Quattro amici pignoli (da vedere...)

« Ultima modifica: 05 Novembre 2010, 15:17:07 da Cosmos »
Spoiler: XKCD (click to show/hide)



Regola Aurea: Qualsiasi calcolo ridicolmente complesso a vedersi, ed ancor più complesso a farsi, porterà certamente ad un risultato nullo...

Corollario: Se il risultato non si annulla, sarà 2\pi

Se X è un insieme non vuoto su cui è definita una relazione d'ordine parziale tale che ogni sua catena possiede un maggiorante, allora contiene almeno un elemento massimale. Chiaro no?

In trepidante attesa della pubblicazione di "Orchi, Antilopi e Calamari - Vol. I"

Offline Raptor

  • Utente Fidato
  • *
  • *
  • *
  • Post: 489
  • Reputazione: 11
  • Sesso: Maschio
    • rpt@altervista
Re:Diario lezioni
« Risposta #5 il: 05 Novembre 2010, 13:15:17 »
Ven 5 nov - 13.00
  • Metodi esatti: il Branch and Bound
    • criteri di potatura
    • esempio
    « Ultima modifica: 05 Novembre 2010, 16:05:46 da Raptor »

    Offline Cosmos

    • Signore dei Geek
    • *
    • *
    • *
    • Post: 1.493
    • Reputazione: 48
    • Sesso: Maschio
    • Is this the end?
    Re:Diario lezioni
    « Risposta #6 il: 08 Novembre 2010, 19:42:55 »
    Lun 8 nov - 17.30
    • Branch and Bound (continuazione)
    • Regole di Esplorazione
      • Depth First
      • Best First
    • Calcolo del Lower Bound
      • Eliminazione di vincoli
      • Modifica della f.o.
      • Rilassamento Lagrangiano
      • Rilassamento Surrogato

    Mar 9 nov - 13.00
    • Branch and Bound (continuazione)
    • Esercizi
      • Dato un albero generico determinare prossimo nodo da visitare, nodi da chiudere, analizzarne la correttezza.
      • KP 0/1
    « Ultima modifica: 09 Novembre 2010, 20:55:26 da Cosmos »
    Spoiler: XKCD (click to show/hide)



    Regola Aurea: Qualsiasi calcolo ridicolmente complesso a vedersi, ed ancor più complesso a farsi, porterà certamente ad un risultato nullo...

    Corollario: Se il risultato non si annulla, sarà 2\pi

    Se X è un insieme non vuoto su cui è definita una relazione d'ordine parziale tale che ogni sua catena possiede un maggiorante, allora contiene almeno un elemento massimale. Chiaro no?

    In trepidante attesa della pubblicazione di "Orchi, Antilopi e Calamari - Vol. I"

    Offline Mithrandir

    • Maestro Geek
    • *
    • *
    • *
    • Post: 1.157
    • Reputazione: 44
    • Sesso: Maschio
    • Battlemage
    Re:Diario lezioni
    « Risposta #7 il: 14 Novembre 2010, 19:21:24 »
    Ven 12 nov - 13.00
    • Esercitazione: Branch and Bound
      • Un esercizio.
    Spoiler (click to show/hide)
    Gandalf? Yes... that was what they used to call me. Gandalf the Grey. That was my name.
    I am Gandalf the White. And I come back to you now - at the turn of the tide.


    Offline Cosmos

    • Signore dei Geek
    • *
    • *
    • *
    • Post: 1.493
    • Reputazione: 48
    • Sesso: Maschio
    • Is this the end?
    Re:Diario lezioni
    « Risposta #8 il: 15 Novembre 2010, 20:26:14 »
    Lun 15 nov - 17.30
    • Programmazione Dinamica
      • Ottimalità di Bellman
      • Cammino Minimo
      • KP 0/1
    Spoiler: XKCD (click to show/hide)



    Regola Aurea: Qualsiasi calcolo ridicolmente complesso a vedersi, ed ancor più complesso a farsi, porterà certamente ad un risultato nullo...

    Corollario: Se il risultato non si annulla, sarà 2\pi

    Se X è un insieme non vuoto su cui è definita una relazione d'ordine parziale tale che ogni sua catena possiede un maggiorante, allora contiene almeno un elemento massimale. Chiaro no?

    In trepidante attesa della pubblicazione di "Orchi, Antilopi e Calamari - Vol. I"

    Offline Mithrandir

    • Maestro Geek
    • *
    • *
    • *
    • Post: 1.157
    • Reputazione: 44
    • Sesso: Maschio
    • Battlemage
    Re:Diario lezioni
    « Risposta #9 il: 16 Novembre 2010, 14:44:46 »
    Mar 16 nov - 13.00
    • Esempi di programmazione dinamica
      • Esempio di cammino minimo su grafo
      • Esempio di KP 0/1 (pag. 227)
    Spoiler (click to show/hide)
    Gandalf? Yes... that was what they used to call me. Gandalf the Grey. That was my name.
    I am Gandalf the White. And I come back to you now - at the turn of the tide.


    Offline Raptor

    • Utente Fidato
    • *
    • *
    • *
    • Post: 489
    • Reputazione: 11
    • Sesso: Maschio
      • rpt@altervista
    Re:Diario lezioni
    « Risposta #10 il: 19 Novembre 2010, 13:19:55 »
    Ven 19 nov - 13.00
    • Esercizi sul KP risolti con programmazione dinamica
    • Metodo per trovare la soluzione corrispondente all'ottimo a partire dalla tabella degli ottimi

    (me ne vado alle 14.00 causa sciopero, ma penso che faccia solo più 1,2 esercizi)
    « Ultima modifica: 19 Novembre 2010, 13:53:28 da Raptor »

    Offline Cosmos

    • Signore dei Geek
    • *
    • *
    • *
    • Post: 1.493
    • Reputazione: 48
    • Sesso: Maschio
    • Is this the end?
    Re:Diario lezioni
    « Risposta #11 il: 22 Novembre 2010, 19:46:04 »
    Lun 22 nov - 17.30
    Euristiche
    • Tecniche Miopiche
      • Euristiche Greedy
      • Beam Search
       
    • Introduzione alla ricerca locale
      • Steepest Descent
      • First Improvement
      • Generalizzazione di un algoritmo basato su ricerca locale
    « Ultima modifica: 22 Novembre 2010, 23:36:15 da Cosmos »
    Spoiler: XKCD (click to show/hide)



    Regola Aurea: Qualsiasi calcolo ridicolmente complesso a vedersi, ed ancor più complesso a farsi, porterà certamente ad un risultato nullo...

    Corollario: Se il risultato non si annulla, sarà 2\pi

    Se X è un insieme non vuoto su cui è definita una relazione d'ordine parziale tale che ogni sua catena possiede un maggiorante, allora contiene almeno un elemento massimale. Chiaro no?

    In trepidante attesa della pubblicazione di "Orchi, Antilopi e Calamari - Vol. I"

    Offline Mithrandir

    • Maestro Geek
    • *
    • *
    • *
    • Post: 1.157
    • Reputazione: 44
    • Sesso: Maschio
    • Battlemage
    Re:Diario lezioni
    « Risposta #12 il: 23 Novembre 2010, 14:39:39 »
    Mar 23 nov - 13.00
    • Euristiche
      • Esempi generazione vicinato: K/P e TSP.
    • Meta-euristiche
      • Presentazione
      • Classificazione
      • Introduzione alle meta-euristiche multi-start
    Spoiler (click to show/hide)
    Gandalf? Yes... that was what they used to call me. Gandalf the Grey. That was my name.
    I am Gandalf the White. And I come back to you now - at the turn of the tide.


    Offline Cosmos

    • Signore dei Geek
    • *
    • *
    • *
    • Post: 1.493
    • Reputazione: 48
    • Sesso: Maschio
    • Is this the end?
    Re:Diario lezioni
    « Risposta #13 il: 27 Novembre 2010, 19:51:12 »
    Ven 26 nov - 13.00
    • Metaeuristiche Multistart (continuazione)
      • ILS (Iterated Local Search)
      • VNS (Variable Neighborhood Search)
      • VND (Variable Neighborhood Descent)
      • GRASP (Greedy Randomized Adaptive Search Procedure)
    • Metaeuristiche basate su vicinati
      • Presentazione generale (Tabu Search, Simulated Annealing, Guided LS)
      • Introduzione al TS: colorazione di un grafo (da completare)
    « Ultima modifica: 27 Novembre 2010, 19:53:49 da Cosmos »
    Spoiler: XKCD (click to show/hide)



    Regola Aurea: Qualsiasi calcolo ridicolmente complesso a vedersi, ed ancor più complesso a farsi, porterà certamente ad un risultato nullo...

    Corollario: Se il risultato non si annulla, sarà 2\pi

    Se X è un insieme non vuoto su cui è definita una relazione d'ordine parziale tale che ogni sua catena possiede un maggiorante, allora contiene almeno un elemento massimale. Chiaro no?

    In trepidante attesa della pubblicazione di "Orchi, Antilopi e Calamari - Vol. I"

    Offline Cosmos

    • Signore dei Geek
    • *
    • *
    • *
    • Post: 1.493
    • Reputazione: 48
    • Sesso: Maschio
    • Is this the end?
    Re:Diario lezioni
    « Risposta #14 il: 29 Novembre 2010, 20:11:06 »
    Lun 29 nov - 17.30
    • Simulated Annealing
    • Esempio: Graph Partitioning
    Spoiler: XKCD (click to show/hide)



    Regola Aurea: Qualsiasi calcolo ridicolmente complesso a vedersi, ed ancor più complesso a farsi, porterà certamente ad un risultato nullo...

    Corollario: Se il risultato non si annulla, sarà 2\pi

    Se X è un insieme non vuoto su cui è definita una relazione d'ordine parziale tale che ogni sua catena possiede un maggiorante, allora contiene almeno un elemento massimale. Chiaro no?

    In trepidante attesa della pubblicazione di "Orchi, Antilopi e Calamari - Vol. I"

    Offline Mithrandir

    • Maestro Geek
    • *
    • *
    • *
    • Post: 1.157
    • Reputazione: 44
    • Sesso: Maschio
    • Battlemage
    Re:Diario lezioni
    « Risposta #15 il: 30 Novembre 2010, 17:17:16 »
    Mar 30 nov - 13.00
    • Algoritmi genetici
      • Funzionamento
      • Operatori genetici (crossover, mutazione e inversione)
      • Ibridizzazione (cfr. Algoritmi Memetici)
      • Esempi:
        • TSP
        • \max x^2 (for dummies)

    Venerdì sarà prevista una esercitazione.
    Spoiler (click to show/hide)
    Gandalf? Yes... that was what they used to call me. Gandalf the Grey. That was my name.
    I am Gandalf the White. And I come back to you now - at the turn of the tide.


    Offline Mithrandir

    • Maestro Geek
    • *
    • *
    • *
    • Post: 1.157
    • Reputazione: 44
    • Sesso: Maschio
    • Battlemage
    Re:Diario lezioni
    « Risposta #16 il: 03 Dicembre 2010, 16:14:49 »
    Ven 3 dic - 13.00
    • Applicazione di algoritmi genetici
      • KP 0/1 con approccio elitista
      • KP 0/1 con approccio probabilistico
      • Discussione sul problema dei cloni
        Spoiler (click to show/hide)
    « Ultima modifica: 23 Febbraio 2011, 19:06:55 da Mithrandir »
    Spoiler (click to show/hide)
    Gandalf? Yes... that was what they used to call me. Gandalf the Grey. That was my name.
    I am Gandalf the White. And I come back to you now - at the turn of the tide.


    Offline Cosmos

    • Signore dei Geek
    • *
    • *
    • *
    • Post: 1.493
    • Reputazione: 48
    • Sesso: Maschio
    • Is this the end?
    Re:Diario lezioni
    « Risposta #17 il: 06 Dicembre 2010, 21:48:34 »
    Lun 6 dic - 17.30
    • Problemi sui Grafi
      • Concetti generali sui grafi: notazioni e rappresentazione
      • Ricerca di cammini
      • MST: Prim e Kruskal (teoria)
      • Flusso di costo minimo (introduzione)

    Mar 7 dic - 13.00
    • Problemi sui Grafi
      • Flusso di costo minimo (reprise)

    Ven 10 dic - 13.00
    • Problemi sui Grafi
      • Flusso di costo minimo riassunto teorico completo
      • Flusso di costo minimo: esempio numerico con fase 0
    • Fuga dall'aula causa lavori al piano di sopra e polveri sospette

    Lun 13 dic - 17.30
    • Esercitazione: Tabu Search

      Mar 14 dic - 13.00
      • Max Flow
        • Modello matematico
        • Definizione di Taglio
        • Definizione di Cammino Aumentante
        • Introduzione a Ford-Fulkerson (ripreso a seguire con esempio)
        • Quesiti su cui riflettere: Complessità di F-F, Allocazione di Job ricondotto a Max-Flow, Min-Cut

      Ven 17 dic - 13.00
      • Max Flow
        • Scheduling ricondotto a Min Cut
        • Complessità di Ford-Fulkerson
        • Definizione dell'algoritmo
        • Esempio numerico

      Lun 20 dic - 17.30
      • Max Flow
        • Algoritmo di Preflow/Push
        • Introduzione dell'algoritmo
        • Definizioni e teoria su cui si basa
        • Esempio numerico (solamente iniziato)

      Mar 21 dic - 13.00
      • Max Flow
        • Algoritmo di Preflow/Push (termine dell'esempio)
        • Varianti di P/P e analisi della complessità algoritmica (cenni)
        • Esempio di P/P in presenza di reflusso verso la sorgente
        • Auguri di Natale (e invito a godersi il meritato riposo)

      Lun 10 gen - 17.30
      • Multi-commodities Network Flow
        • Introduzione
        • Sotto problema: Min-Cost Capacitato
        • Trattazione teorico/pratica del Min-Cost Capacitato

      Mar 11 gen - 13.00
      • Multi-commodities Network Flow (continua)
        • Modello matematico e sua analisi
        • Introduzione delle tre famiglie di algoritmi che saranno trattati
        • 1) Rilassamento Lagrangiano

      Nel corso della lezione è stato detto che un argomento a seguire sarà la programmazione non lineare.
      L'equilibrio nella Forza ha subito un brusco cambiamento.


      Ven 14 gen - 13.00
      • Esercitazione: Rilassamento Lagrangiano
        • Richiamo teorico e introduzione
        • Applicazione: SPTT (Shortest Path with Time Traversal)
        • Cenni: Metodo del Sub-gradiente

      Lun 17 gen - 17.30
      • Rilassamento Lagrangiano & MCNF
        • Problemi tecnici vari...
        • UFA (Uncapacitated Facilities Allocation): Modello matematico e due rilassamenti Lagrangiani
        • Ritorno al MCNF: Approccio Multicolumn (introduzione e modello)

      Mar 18 gen - 13.00
      • MCNF
        • Conclusione approccio multicolumn, con malefico richiamo al Simplesso
      • Programmazione non lineare
        • Panoramica degli argomenti
        • PNL non vincolata

      Ven 21 gen - 13.00
      • Esercitazione:
        • MCF - Column Generation

      Lun 24 gen - 17.30
      • PNL
        • PNL vincolata: condizioni del I e II ordine con esempi numerici
        • Introduzione agli algoritmi di soluzione di PNL vincolata in una variabile

      Mar 25 gen - 13.00
      • PNL n/vincolata in una variabile
        • Ricerca lineare
        • Ricerca dicotomica
        • Ricerca basata su sezione aurea
        • Ricerca basata su serie di Fibonacci (cenno)
        • Metodo di Newton (basato su derivate)

      Con oggi si chiude il corso.
      Anticipazione delle lezioni a venire:
      Venerdì - Esercitazione PNL
      Lunedì/Martedì - Q&A, ripasso, esercizi
      Venerdì - Simulazione



      Considerazioni sull'esame:

      Gli argomenti per cui non è prevista una parte di esercizi sono la complessità computazionale, il max flow nella versione preflow flush e il Multicommodities Network Flow.
      Tutto il resto può essere anche 'eserciziato'.
      Dovrebbero apparire sul portale esercizi relativi a Lagrangiano e PNL.
      « Ultima modifica: 01 Febbraio 2011, 15:50:14 da Cosmos »
      Spoiler: XKCD (click to show/hide)



      Regola Aurea: Qualsiasi calcolo ridicolmente complesso a vedersi, ed ancor più complesso a farsi, porterà certamente ad un risultato nullo...

      Corollario: Se il risultato non si annulla, sarà 2\pi

      Se X è un insieme non vuoto su cui è definita una relazione d'ordine parziale tale che ogni sua catena possiede un maggiorante, allora contiene almeno un elemento massimale. Chiaro no?

      In trepidante attesa della pubblicazione di "Orchi, Antilopi e Calamari - Vol. I"