Informatica teorica: qualcuno ha studiato ste cose?

alexmaz · 17-10-2001, 21:32

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 · 17-10-2001, 22:04

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 · 17-10-2001, 22:10

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 · 17-10-2001, 23:33

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 · 18-10-2001, 00:28

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 · 20-10-2001, 11:38

Quote:

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 · 12-12-2010, 11:19

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 · 12-12-2010, 12:01

Quote:

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 · 12-12-2010, 13:59

Quote:

Originariamente inviato da Antonio23

thread necromancer... un thread del 2001!

questo dev'essere un vero record.

17-10-2001, 21:32	#1
alexmaz Senior Member Iscritto dal: Jan 2000 Città: Milano Messaggi: 1034	Informatica teorica: qualcuno ha studiato ste cose? 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...

17-10-2001, 22:04	#2
MickMacello Senior Member Iscritto dal: Dec 1999 Messaggi: 139	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) __________________ Ingegnere: colui che ha molta familiarità con i modelli e molto poca con le modelle.

17-10-2001, 23:33	#4
MickMacello Senior Member Iscritto dal: Dec 1999 Messaggi: 139	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) __________________ Ingegnere: colui che ha molta familiarità con i modelli e molto poca con le modelle.

12-12-2010, 11:19	#7
monicalombardi Junior Member Iscritto dal: Mar 2006 Città: potenza Messaggi: 1	Informatica teorica 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

17-10-2001, 22:10	#3
alexmaz Senior Member Iscritto dal: Jan 2000 Città: Milano Messaggi: 1034	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

18-10-2001, 00:28	#5
alexmaz Senior Member Iscritto dal: Jan 2000 Città: Milano Messaggi: 1034	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...

Strumenti
Mostra una versione stampabile Invia questa pagina per email