ProgrammaCalcComp0708 < Calcolabilita

Tags: view all tags
<table width="700" border="0" cellspacing="2" cellpadding="2">
       <tbody>
        <tr>
         <td height="2">                               
      <p><br>
          </p>
                                   
      <table width="95%" border="0" cellspacing="2" cellpadding="2" align="center">
             <tbody>
              <tr>
               <td width="49%" align="left" valign="top" height="369">  
                                                      
            <table border="0" width="100%" cellspacing="0" cellpadding="0">
                   <tbody>
                    <tr>
                     <td width="100%" colspan="2">                      
                                                                  
                  <h1><font color="#000000" face="arial,helvetica">     
                               Calcolabilit&agrave; e Complessit&agrave; <br> a.a. 2007/2008
                                                     </font></h1>
                                     </td>
                   </tr>
                   <tr>
                     <td width="4%"><br>
                      </td>
                     <td width="96%">                                   
                                                                  
                  <h3><i><b><font face="arial,helvetica">               
              Docente: R. Silvestri                      
          </font></b></i></h3>
                      </td>
                   </tr>
                   <tr>
                     <td width="100%" colspan="2"><br>
                      </td>
                   </tr>
                                                                        
              </tbody>                                                 
            </table>
                                                                        
                                     
            <p></p>
                                                    
            <h2><b><font face="arial,helvetica">Finalit&agrave;</font></b></h2>
                                                    
            <p></p>
                                                                 
            <div align="right">                                         
                    
            <table border="0" width="90%">
                     <tbody>
                    <tr>
                       <td width="100%"><font face="Arial, Helvetica">  
                                                                        
                                
                  <p align="justify">L'obiettivo del corso &egrave;
introdurre alla teoria della calcolabilit&agrave; e alla teoria della complessit&agrave;
computazionale.                            
               </p>
                                       </font>                   </td>
                     </tr>
                                                                        
  
              </tbody>                                                 
            </table>
                 </div>
                                                                        
               
            <p></p>
                                                    
            <h2><b><font face="arial,helvetica">Programma</font></b></h2>
                                                    
            <p></p>
                                                                
            <div align="right">                                         
                    
            <table border="0" width="90%">
                     <tbody>
                    <tr>
                       <td width="100%"><font face="Arial, Helvetica">  
                                                                                                                                                          
   
                  <h3><b>Teoria degli automi e delle grammatiche</b></h3>

Cenni su modelli di calcolo. Automi a stati finiti (DFA). La classe dei linguaggi regolari:
chiusura rispetto a unione, intersezione e complemento. Automi non deterministici (NFA).
Equivalenza tra DFA e NFA (dimostrazione). Chiusura dei regolari rispetto a concatenazione di
linguaggi e stella di Kleene. Espressioni regolari. Equivalenza tra espressioni regolari e 
DFA (dimostrazione). Pumping lemma per i regolari (dimostrazione). Teorema di 
Myhill-Nerode (dimostrazione solamente del fatto che se <i>L</i> &egrave; regolare allora
l'indice della relazione di Nerode di <i>L</i> ha indice minore od uguale al numero degli stati 
di un qualsiasi automa che riconosce <i>L</i>). Uso della relazione di Nerode per determinare
delimitazioni inferiori sul numero di stati di DFA e NFA. <br>
Automi pushdown deterministici (DPDA). Chiusura della classe dei linguaggi accettati da DPDA
rispetto al complemento (senza dimostrazione) e all'intersezione con linguaggi regolari.
Automi pushdown non deterministici (NPDA). Chiusura dell classe dei linguaggi accettati da NPDA
rispetto a unione, concatenazione di linguaggi, stella di Kleene e intersezione con linguaggi regolari. 
Grammatiche context-free (CFG).
Alberi di derivazione e derivazioni pi&ugrave; a sinistra. Equivalenza tra CFG e NPDA (dimostrazione
solamente del verso da CFG a NPDA). Pumping lemma per linguaggi context-free (dimostrazione).

                  <h3><b>Teoria della calcolabilit&agrave;</b></h3>
Macchine di Turing (TM) ad un nastro. Configurazioni di una TM. 
Linguaggi semi-decidibili (o riconoscibili) e linguaggi decidibili 
(o ricorsivi). Esempi di linguaggi decidibili. Macchine di Turing a
k nastri (k-TM). Equivalenza tra k-TM e TM (dimostrazione). 
Macchine di Turing non deterministiche (NTM). Equivalenza tra NTM
e TM (dimostrazione). Robustezza del concetto di decidibilit&agrave;
tramite TM e cenni ad altri modelli di calcolo: RAM. 
Tesi di Church-Turing. <br>
Indecidibilit&agrave; del problema dell'accettazione, metodo della
diagonalizzazione (dimostrazione). Relazione tra decidibilit&agrave; e 
semi-decidibilit&agrave;. Indecibilit&agrave; dei problemi della 
terminazione, del linguaggio vuoto e dell'equivalenza (dimostrazioni).
Automi linearmente limitati (LBA). Decidibilit&agrave; dei linguaggi 
context free tramite LBA (dimostrazione). Decidibilit&agrave; del problema 
della terminazione per LBA (dimostrazione). Indecidibilit&agrave; 
del problema del linguaggio vuoto per LBA (dimostrazione). 
Decidibilit&agrave; del problema del linguaggio
vuoto e indecidibilit&agrave; del problema della totalit&agrave; per
CFG (dimostrazioni). Funzioni calcolabili e la m-riducibilit&agrave;. 
Conservazione della decidibilit&agrave; e della 
semi-decidibilit&agrave; da parte della m-riducibilit&agrave;.                        
                                            
                  <h3><b>Teoria della complessit&agrave;</b></h3>
Modelli di calcolo e la misura delle risorse computazionali. Complessit&agrave;
temporale di macchine di Turing: esempi. Misura della complessit&agrave; della
simulazione di k-TM tramite TM (dimostrazione). Cenni ad altri modelli (RAM)
che sono simulabili in tempo polinomiale da TM. Complessit&agrave; temporale
di macchine di Turing non deterministiche. Misura della complessit&agrave;
della simulazione di NTM tramite TM (dimostrazione). Classi di complessit&agrave;
temporali. La classe P. Crescita polinomiale e crescita esponenziale. 
Esempi di problemi in P: i linguaggi context free sono in P (dimostrazione).
La classe NP. Verificabilit&agrave; polinomiale. Riducibilit&agrave; polinomiale
e il concetto di NP-completezza. Teorema di Cook-Levin: NP-completezza di SAT
(dimostrazione). Esempi di riduzioni polinomiali tra problemi.
                                                                  
                      </font></td>
                     </tr>
                                                                        
  
              </tbody>                                                 
            </table>
                    </div>
                                                                        
                          
            <p></p>
                                                    
            <h2><b><font face="arial,helvetica">Testi</font></b></h2>
                                                                        
    
                                                                        
    
            <div align="right">                                         
                    
            <table border="0" width="90%">
                     <tbody>
                    <tr>
                       <td width="100%"><font face="Arial, Helvetica">  
                                                                        
                                                                          
                                                                     
          <ul>
<li><p><font color="#3c0eb7">  
<a href="http://www-math.mit.edu/~sipser/book.html">
M. Sipser &nbsp;&nbsp;&nbsp;&nbsp;  <i>Introduction to the Theory of Computation</i></a>&nbsp;&nbsp; 
Course Technology.</font></p>
&Egrave; il testo di riferimento per il corso. 
                        </li>
<p><br></p>
                    <li><p><font color="#3c0eb7">  
<a href="http://addison.it/site/show.php?curr_sec=catalogo&sub_sec=cat_sk_libro&ISBN=8871921542">
J. Hopcroft, R. Motwani, J. Ullman &nbsp;&nbsp;&nbsp;&nbsp;  <i>Automi, 
linguaggi e calcolabilit&agrave;</i></a>&nbsp;&nbsp; Pearson (Addison Wesley).</font></p>
Un utile testo di approfondimento. 
                        </li>                                                                    
                  </ul>
                                                                        
      
                              </font>                   </td>
                     </tr>
                                                                        
  
              </tbody>                                                 
            </table>
                 </div>
                                                                                                                               </td>
              </tr>
                                    
        </tbody>                         
      </table>
          </td>
        </tr>
            
  </tbody> 
</table>
    <br>
    <br>
   <br>
  <br>
 <br>



-- Users.RiccardoSilvestri - 23 Sep 2007