Ders AdıKodu Yerel KrediAKTS Ders (saat/hafta)Uygulama (saat/hafta)Laboratuar (saat/hafta)
Hesaplama KuramıBLM250234300
ÖnkoşullarYok
YarıyılBahar
Dersin Diliİngilizce, Türkçe
Dersin SeviyesiLisans
Dersin TürüZorunlu @ Bilgisayar Mühendisliği Lisans Programı
Ders KategorisiTemel Meslek Dersleri
Dersin Veriliş ŞekliYüz yüze
Dersi Sunan Akademik BirimBilgisayar Mühendisliği Bölümü
Dersin KoordinatörüFerkan Yılmaz
Dersi Veren(ler)Ferkan Yılmaz, Oğuz Altun
Asistan(lar)ı
Dersin AmacıBu dersin amacı, öğrencilere, otomata teorisi ve biçimsel diller ve gramerler teorisini içeren hesaplamanın matematiksel temellerini tanıtmak; aynı zamanda otomatlar, eşdeğer düzenli ifadeler, otomatlar tarafından tanımlanan dillerin eşdeğerliği, düzenli ifadeler, pushdown otomatı, eşdeğer context-free gramerleri, pushdown otomata tarafından tanımlanan dillerin eşdeğeri, bağlam gibi temel kavramları kavratmaktır. ücretsiz gramerler, Turing makineleri ve Turing makineleri tarafından tanımlanan dillerin eşdeğerliği.
Dersin İçeriğiDersin İçeriği Matematiksel Araçlar (Tanımlar, Teoremler ve İspatlar); İspat Türleri; Düzenli Diller; Sonlu Otomatlar; Deterministik Olmayan Makinalar; Düzenli İfadeler; Düzensiz Diller; Bağlam İçermeyen (Context-free) Diller; Bağlam İçermeyen (Context-free) Gramerler; Basma Otomatiği; Turing Makineleri; Turing Makinelerinin Çeşitleri; "Algoritma" tanımı; Karar Verebilirlik; Kararlanabilir Diller; NP-bütünlüğü; İndirgenebilirlik; Tanınabilirlik.
Ders Kitabı / Malzemesi / Önerilen Kaynaklar
  • Michael Sipser, Introduction to the Theory of Computation, Cengage Learning, 3rd Edition, 2012
  • Daniel I. A. Cohen, Introduction to Computer Theory, Prentice-Hall, 2nd Edition, 1997
Opsiyonel Program BileşenleriYok

Ders Öğrenim Çıktıları

  1. Öğrenciler sonlu otomata, deterministik ve deterministik olmayan otomata, düzenli ifadeler, basmalı otomata, turing makineleri, biçimsel diller ve gramerler analiz edebileceklerdir.
  2. Öğrenciler sonlu otomata, deterministik ve deterministik olmayan otomata, düzenli ifadeler, basmalı otomata, turing makineleri, biçimsel diller ve gramerler için tasarımlar yapabileceklerdir.
  3. Öğrenciler problem çözme yoluyla algoritma, hesaplanabilirlik, karar verilebilirlik ve karmaşıklık gibi anahtar kavramların anlaşıldığını göstereceklerdir.
  4. Öğrenciler Turing Makinelerine ve Problem Sınıflarına aşina olacaklardır.
  5. Öğrenciler problem kurma ve çözme becerisini geliştireceklerdir.
  6. Öğrenciler, Hesaplama Kuramı'nın temel sonuçlarını kanıtlayabileceklerdir.

Haftalık Konular ve İlgili Ön Hazırlık Çalışmaları

HaftaKonularÖn Hazırlık
1Ön kavramların oluşturulması, matematiksel araçlar, tanımlar, teoremler ve ispatlar, ispat çeşitleriDers kitabının ilgili bölümü
2Deterministik sonlu otomata (DFA)Ders kitabının ilgili bölümü
3Deterministik olmayan sonlu otomata (NFA)Ders kitabının ilgili bölümü
4DFA ve NFA'nın eşdeğerliliği ve düzenli ifadelerDers kitabının ilgili bölümü
5Epsilon geçiş, pompalama Lemma, güvercin prensibi ve kapatma (closure) özellikleriDers kitabının ilgili bölümü
6Optimal DFA ve genel bakışDers kitabının ilgili bölümü
7Bağlamsız diller, bağlamsız gramerler, ayrıştırma ağacı, belirsizlik, kapalılık özellikleriDers kitabının ilgili bölümü
8Ara Sınav 1
9Yıl içi sınavı
10Yığıtlı OtomatlarDers kitabının ilgili bölümü
11Bağlamsız gramerlere ve Church-Turing hipotezine genel bakışDers kitabının ilgili bölümü
12Turing Makineleri, Tanıma ve Hesaplama, Church-Turing HipoteziDers kitabının ilgili bölümü
13Ara Sınav 2
14NP-eksiksizliği, karar verilebilirlik, indirgenebilirlik ve tanınabilirlikDers kitabının ilgili bölümü
15Final

Değerlendirme Sistemi

EtkinliklerSayıKatkı Payı
Devam/Katılım
Laboratuar
Uygulama
Arazi Çalışması
Derse Özgü Staj
Küçük Sınavlar/Stüdyo Kritiği330
Ödev00
Sunum/Jüri
Projeler
Seminer/Workshop
Ara Sınavlar130
Final140
Dönem İçi Çalışmaların Başarı Notuna Katkısı
Final Sınavının Başarı Notuna Katkısı
TOPLAM100

AKTS İşyükü Tablosu

EtkinliklerSayıSüresi (Saat)Toplam İşyükü
Ders Saati123
Laboratuar
Uygulama
Arazi Çalışması
Sınıf Dışı Ders Çalışması113
Derse Özgü Staj
Ödev00
Küçük Sınavlar/Stüdyo Kritiği210
Projeler
Sunum / Seminer
Ara Sınavlar (Sınav Süresi + Sınav Hazırlık Süresi)125
Final (Sınav Süresi + Sınav Hazırlık Süresi)135
Toplam İşyükü :
Toplam İşyükü / 30(s) :
AKTS Kredisi :
Diğer NotlarYok