Profile cover photo
Profile photo
Nicola Galesi Teaching
65 followers
65 followers
About
Posts

Topics of 24-10-2017 ----------------------------------
Space complexity
Configuration graph and its property for bounded space computations.
NSPACE(S(n)) in DTIME(2^{O(S(s)})
NSPACE(S(n)) in SPACE(S(n)^2) (Savitch Thm)
NP in PSPACE
PSPACE-completeness
QBF is PSPACE complete

Argomenti Lezione del 20-10-2017 ------------------------------------------------------
Oracle Turing Machines
Relativizing results
Limits of Diagonalization
Baker Gill Solovay Theorem.

Argomenti Lezione del 24-10-2017 ------------------------------------------------------

Certificato di illimitatezza di PPL
Caratterizzazione di soluzione ottime di PPL
Esercizi
Forme non standard
Variabili Artificiali
Metodo della BIG M
Variabili Surplus
Esempi.

Argomenti Lezione del 20-10-2017 -------------------------------------------------------

Esercitazioni
Certificati di insolubilita di sistemi di equazioni lineari

Argomenti Lezione del 17-10-2017 -------------------------------------------------------

Forma aumentata
Metodo del simplesso: soluzione algebrico
Metodo del simplesso: soluzione tabellare

There was a proposal by some of you to write notes of the lectures.
If we divide that work among all, I would be very very happy to do that. Let me know if you like (but you do not have to do necessarily that) and I'll try to organize the format and give you more info about each of the lecture.

Nicola

LEZIONE di Venerdi 13-10-2017 ---------------------------------------------------
Problema: max profitto creme
Problema: minimizzare costi produzione macchine filati

Le 3 Proprietà del Simplesso
- soluzioni ottime su vertici (dim)
- finitezza vertici (dim)
- località (un vertice non migliorabile è ottimo) idea dim
correttezza e finitezza del metodo del simplesso
Geometria del simplesso
- Test ottimalità (scelta direzione)
- test del minimo rapporto (nuovo vertice)
Forma standard
Forma aumentata

Lezione di Venerdi 13-10-2017 ------------------------------------------------
CNFSAT NP-completeness
Cook's Theorem
Hw: reduction from CNFSAT to 3-CNF-SAT
Co-NP
EXP
NEXP
Padding technique: EXP \nor = NEXP implies P not = NP

Class of 11-10-2017 -----------------------------------
Def of NTIME
Def of NP
Equivalence between different def of NP
Karp polynomial reducibility and its properties
NP-completeness
SATis NP-complete (starting)

Argomenti Lezione del Martedi 10 -10 -2017 ---------------------------------------------------------------------

Problemi di Programmazione Lineare
Esempio
Soluzione Grafica
Forma Standard
Introduzione la simplesso
Complessità di PL e IP
Problemi
Wait while more posts are being loaded