Geri

 

Dersin Adı

Kodu

Yarıyılı

T+U

Kredisi

AKTS

Hesaplama Kuramı

0504401

4

3+0

3

5

 

Ön koşul Dersler

 

 

Dersin Dili

Türkçe

Dersin Türü

Zorunlu

Dersin Koordinatörü

 

Dersi Veren

Yrd.Doç.Dr. M.Akif NACAR

Dersin Yardımcıları

 

Dersin Amacı

Öğrenciye bilgisayar biliminin matematiksel gelişimi anlatmak ve dillerin sonlu gösterimleri ile derleyici tasarımının temelleri hakkında genel bilgiler vermektir.

Dersin Öğrenme Çıktıları

Bu dersin sonunda öğrenci; 

·      Eşdeğer reguler ifade (RE) için sonlu otomata (FA), PDA, CFG, TM ve PM üretebilir.

·      Tanımlanmış dillerdeki FA ile RE, PDA ile CFG, TM ile PM nin eşdeğer olduklarını ispatlayabilir.

·      Teorik makinalarla günümüzdeki bilgisayarlar arasındaki bağlantı kurabilir.

·      Matematiksel modelleri pratik hayattaki dizge arama, şifreleme ve dil tasarlama gibi problemlere uygulama becerisi kazanabilir.

Dersin İçeriği

Temel tanımlar. Otomat ve sonlu otomat. Düzenli ifadeler ve formal diller. Düzenli dillerin özellikleri. İçerikten bağımsız dilbilgisi yapıları ve diller. Pushdown otomat. İçerikten bağımsız dillerin özellikleri. Turing makinelerine giriş. Karar verilemeyen

problemler. Zor problemler.

 

Haftalar

Konular

1

Temel tanımlar

2

Otomat ve sonlu otomat

3

Düzenli ifadeler ve formal diller

4

Düzenli ifadeler ve formal diller

5

Düzenli dillerin özellikler

6

İçerikten bağımsız dilbilgisi yapıları ve diller

7

Pushdown otomat

8

Pushdown otomat

9

İçerikten bağımsız dillerin özellikleri

10

Turing makinelerine giriş

11

Turing makinelerine giriş

12

Karar verilemeyen problemler

13

Karar verilemeyen problemler

14

Zor problemler

 

 

 

Genel Yeterlilikler

Eşdeğer reguler ifade (RE) için sonlu otomata (FA), PDA, CFG, TM ve PM üretebilme.

Tanımlanmış dillerdeki FA ile RE, PDA ile CFG, TM ile PM nin eşdeğer olduklarını ispatlayabilme.

Teorik makinalarla günümüzdeki bilgisayarlar arasındaki bağlantı kurabilme.

Matematiksel modelleri pratik hayattaki dizge arama, şifreleme ve dil tasarlama gibi problemlere uygulama.

 

Kaynaklar

Cohen, Daniel I. A. M. , 1997, Introduction to Computer Theory, Wiley Pub. 634 p.

Sipser, Micheal,2006, Introduction to Theory of Computation, Second Ed., Thomson Pub. 415 p.

Hopcroft, John E. , 2006, Introduction to Automata Theory, Languages, and Computation, Addison Wesley Pub. , 535 p.

 

 

Değerlendirme Sistemi

Arasınav :40     
Final:        60

Projeler:   -

Ödevler:   -