Informatica teorica: qualcuno ha studiato ste cose?

[alexmaz]

Questo semestre vorrei seguire informatica teorica e gli argomenti sono questi:

1. Premessa

Elementi di teoria della computabilita'
La Tesi di Church
Macchine di Turing
Funzioni parziali ricorsive (Kleene)
I programmi IMP
Proprieta’ decidibili e indecidibili degli insiemi e delle funzioni computabili


2. Semantica

Introduzione alla semantica operazionale

Sui principi di induzione e sulle definizioni induttive

Introduzione alla semantica denotazionale e alla teoria dei domini

Introduzione alla semantica assiomatica e discussione sulla completezza delle regole di Hoare

Introduzione alla specifica algebrica - tipi di dati astratti, semantiche iniziali


3. Complessita'

Classi di complessita' in spazio e tempo e relazioni tra di loro

Problemi di approssimazione

Definizione sintattica di classi di problemi: complessita’ descrittiva e complessita’ computazionale


Sapete se servono delle particolari conoscenze a priori? Purtroppo sto corso mi si sovrappone a quello di reti e quindi se non sono sicuro di poterlo fare decentemente lo faccio più avanti...

[MickMacello]

Yess !
Mi sono fatto il corso di info teorica e ho anche preso il 30 più scandaloso della mia storia universitaria

Non servono particolari conoscenze, ti basta sapere le basi della logica e dell' algebra.
(per lo meno, questo al politecnico)

[alexmaz]

Ecco gia sulle basi della logica e dell'algebra andiamo malino

Mi sapresti dire dove trovare del matriale o il titolo di un libro che tratti i primi argomenti?

Elementi di teoria della computabilita'
La Tesi di Church
Macchine di Turing
Funzioni parziali ricorsive (Kleene)
I programmi IMP
Proprieta’ decidibili e indecidibili degli insiemi e delle funzioni computabili

[MickMacello]

Beh, il libro di testo del corso per noi è stato quello scritto dal nostro prof:

Ghezzi - Mandrioli : Elementi di informatica teorica.


Un bel libro che tratta la teoria della computabilità in modo divertente e che ti potrebbe servire come introduzione è:

D. Harel - Algorithmics : The spirit of computing
(solo in inglese credo)

[alexmaz]

Ti ringrazio

cmq sono indeciso se seguire Info teorica quest'anno per due motivi: 1) Non ho ancora dato logica matematica e 2) Mi si sovrappone interamente al corso di reti e la cosa mi infastidisce parecchio, visto che poi nel secondo semestre vorrei dare anche sistemi distribuiti... che palle sti orari sovrapposti...

[Arpeda]

Originariamente inviato da alexmaz
[b]che palle sti orari sovrapposti...

Hai pienamente ragione .. pensa che io devo fare 3 esami in una settimana .. quest'anno all'uni gli orari li hanno fatti proprio con i piedi!!

Ciao

[monicalombardi]

Ciao ragazzi ,
leggevo nel forum che avete studiato informatica teorica e mi serve un piccolo aiuto.Il prof. mi ha chiesto una definizione più dettagliata sulle funzioni calcolabili della macchina di turing ovvero sulle funzioni ricorsive , ricorsive enumerabili, e sulle funzioni ricorsive parziali e totali..!!ho visto sul libro Automi,linguaggi e calcolabilità ,ma ho trovato solo le prime due.Per le funzioni ricorsive parziali e totali non sono riuscita a trovare molto,anche su internet.Mica vi dispiace darmi una dritta??grazie mille
ciaoo

[dojolab]

Originariamente inviato da MickMacello

Beh, il libro di testo del corso per noi è stato quello scritto dal nostro prof:

Ghezzi - Mandrioli : Elementi di informatica teorica.

Orribile questo libro, però è l'unico di decente che c'è tra i più orribili.
Comuque si, penso che tutti ci siamo fatti quell'esame con questi argomenti.

[goldorak]

Originariamente inviato da Antonio23

thread necromancer... un thread del 2001!

questo dev'essere un vero record.