CEN343 Theory of Computation

5 AKTS - 3-0 Süre (T+U)- 5. Yarıyıl- 3 Yerel Kredi

Genel Bilgi

Kod CEN343
Ad Theory of Computation
Yarıyıl 5. Yarıyıl
Süre (T+U) 3-0 (T-U) (17 Hafta)
AKTS 5 AKTS
Yerel Kredi 3 Yerel Kredi
Eğitim Dil İngilizce
Seviye Lisans Dersi
Tür Normal
Öğretim Şekli Yüz Yüze Öğretim
Bilgi Paketi Koordinatörü Prof. Dr. UMUT ORHAN


Dersin Amacı

Bu derste temel amaç, dil sınıflarını gramer ve otomata açısından tanımlamaktır.

Dersin İçeriği

Chomsky hiyerarşisi, Düzenli diller, İçerikten bağımsız diller, Turing makineleri, Karar-verilebilirlik, P ve NP dilleri, NP-complete diller

Dersin Ön Koşulu

yok

Kaynaklar

Introduction to Theory of Computation, Anil Maheshwari and Michiel Smid, Carleton University, 2012.

Notlar

Introduction to the Theory of Computation, 2nd Edition, Michael Sipser, Thomson Course Technnology, Boston, 2006. Introduction to Languages and the Theory of Computation, 4th Edition. John C. Martin, 2011, Mc Graw Hill.


Dersin Öğrenme Çıktıları

Sıra Dersin Öğrenme Çıktıları
ÖÇ01 Chomsky hiyerarşisini bilir
ÖÇ02 Düzenli dil problemlerini çözer
ÖÇ03 İçerikten bağımsız dil problemlerini çözer
ÖÇ04 Turing makinelerini bilir ve tasarlar
ÖÇ05 Karar-verilebilirlik kavramını bilir
ÖÇ06 P, NP ve NP-complete problemlerini bilir ve dönüştürür


Program Öğrenme Çıktıları ile İlişkisi

Sıra Tür Program Öğrenme Çıktıları Duzey
PÖÇ01 Bilgi - Kuramsal, Olgusal 1. Matematik, fen bilimleri ve bilgisayarla ilgili mühendislik konularında yeterli altyapıya sahip olma; bu alanlardaki kuramsal bilgileri beraber kullanabilme 4
PÖÇ02 Bilgi - Kuramsal, Olgusal 2. Karmaşık mühendislik problemlerini saptama, tanımlama, formüle etme ve çözme becerisi; bu amaçla uygun analitik yöntemler ve modelleme tekniklerini seçme ve uygulama 3
PÖÇ03 Bilgi - Kuramsal, Olgusal 3. Karmaşık bir sistemi, sistem bileşenini ya da süreci analiz etme ve istenen gereksinimleri karşılamak üzere gerçekçi kısıtlar altında tasarlama becerisi; bu doğrultuda modern tasarım yöntemlerini uygulama becerisi 4
PÖÇ04 Bilgi - Kuramsal, Olgusal 4. Mühendislik uygulamaları için gerekli olan modern teknik ve araçları geliştirme, seçme ve kullanma becerisi; bilişim teknolojilerini etkin kullanma becerisi 3
PÖÇ05 Bilgi - Kuramsal, Olgusal 5. Karmaşık bilgisayar mühendisliği problemlerin çözümüne ilişkin deney tasarlama, deney yapma, veri toplama, sonuçları analiz etme ve yorumlama becerisi 4
PÖÇ06 Bilgi - Kuramsal, Olgusal Bireysel olarak ve disiplin içi/çok disiplinli takımlarda etkin çalışabilme becerisi, sorumluluk alma ve özgüven
PÖÇ07 Beceriler - Bilişsel, Uygulamalı Bilgiye erişebilme, kaynak araştırması yapabilme ve bilgi kaynaklarını kullanabilme becerisi 3
PÖÇ08 Beceriler - Bilişsel, Uygulamalı Yaşam boyu öğrenmenin gerekliliği bilinci; bilim ve teknolojideki gelişmeleri izleme ve kendini sürekli yenileme becerisi 3
PÖÇ09 Yetkinlikler - Bağımsız Çalışabilme ve Sorumluluk Alabilme Yetkinliği 9. Türkçe sözlü ve yazılı etkin iletişim kurma, ve en az bir yabancı dilde teknik yayın okuyup anlayabilme, rapor hazırlama ve sunum yapma becerisi 4
PÖÇ10 Yetkinlikler - Öğrenme Yetkinliği Mesleki ve etik sorumluluk bilinci; mühendislik uygulamalarında kullanılan standartlar hakkında bilgi 2
PÖÇ11 Yetkinlikler - Öğrenme Yetkinliği 11. Proje yönetimi, işyeri uygulamaları, çalışanların sağlığı, çevre ve iş güvenliği, ve mühendislik uygulamalarının hukuksal sonuçları hakkında farkındalık 3
PÖÇ12 Yetkinlikler - Öğrenme Yetkinliği 12. Mühendislik çözümlerinin ve uygulamalarının evrensel ve toplumsal boyutlardaki etkileri, girişimcilik ve yenilikçilik, ve çağın sorunları hakkında bilgi sahibi olmak 2


Haftalık Akış

Hafta Konu Ön Hazırlık Yöntemler
1 Kesikli matematiksel yapılar tekrarı Ders notunun ilgili bölümünü incelemek Öğretim Yöntemleri:
Anlatım
2 Deterministik sonlu otomata (DFA) ve Deterministik olmayan sonlu otomata (NFA) Ders notunun ilgili bölümünü incelemek Öğretim Yöntemleri:
Anlatım
3 DFAdan NFAya dönüşüm, Düzenli ifadeler Ders notunun ilgili bölümünü incelemek Öğretim Yöntemleri:
Anlatım
4 DFA'dan düzenli ifadeye dönüşüm, Düzenli diller için Pumping Lemma Ders notunun ilgili bölümünü incelemek Öğretim Yöntemleri:
Anlatım
5 İçerik bağımsız gramerler, Chomsky normalizasyonu Ders notunun ilgili bölümünü incelemek Öğretim Yöntemleri:
Anlatım
6 Push-Down otomata Ders notunun ilgili bölümünü incelemek Öğretim Yöntemleri:
Anlatım
7 İçerik-bağımsız diller için Pumping Lemma Ders notunun ilgili bölümünü incelemek Öğretim Yöntemleri:
Anlatım
8 Arasınav Ders notları ve uygulamalara hazırlanmak Ölçme Yöntemleri:
Yazılı Sınav
9 Turing makineleri, Church-Turing tezi Ders notunun ilgili bölümünü incelemek Öğretim Yöntemleri:
Anlatım
10 Deterministik olmayan Turing makineleri Ders notunun ilgili bölümünü incelemek Öğretim Yöntemleri:
Anlatım
11 Karar-verilebilir ve Karar-verilemez diller Ders notunun ilgili bölümünü incelemek Öğretim Yöntemleri:
Anlatım
12 Sayılabilirlik ve Sayılabilir diller Ders notunun ilgili bölümünü incelemek Öğretim Yöntemleri:
Anlatım
13 Karmaşıklık Teorisine giriş, P ve NP sınıfları Ders notunun ilgili bölümünü incelemek Öğretim Yöntemleri:
Anlatım
14 Deterministik olmayan algoritmalar, NP-bütün diller Ders notunun ilgili bölümünü incelemek Öğretim Yöntemleri:
Anlatım
15 Final sınavı için tekrar Ders notunun ilgili bölümünü incelemek Öğretim Yöntemleri:
Soru-Cevap
16 Final Sınavı Ders notları ve uygulamalara hazırlanmak Ölçme Yöntemleri:
Yazılı Sınav
17 Final Sınavı Ders notları ve uygulamalara hazırlanmak Ölçme Yöntemleri:
Yazılı Sınav


Öğrenci İş Yükü - AKTS

Çalışmalar Sayısı Süresi (Saat) İş Yükü (Saat)
Ders ile İlgili Çalışmalar
Ders (Sınav haftaları dahil değildir) 14 3 42
Sınıf Dışı Ders Çalışma (Ön çalışma, pekiştirme) 14 3 42
Değerlendirmeler ile İlgili Çalışmalar
Ödev, Proje, Diğer 0 0 0
Ara Sınavlar (Yazılı, Sözlü, vs.) 1 12 12
Yarıyıl/Yıl Sonu/Final Sınavı 1 18 18
Toplam İş Yükü (Saat) 114
Toplam İş Yükü / 25 (s) 4,56
AKTS 5 AKTS