Mersin Üniversitesi
Ders Bilgileri
| BİÇİMSEL DİLLER VE SOYUT MAKİNELER | ||||||
|---|---|---|---|---|---|---|
| Kodu | Dönemi | Teori | Uygulama | Ulusal Kredisi | AKTS Kredisi | |
| Saat / Hafta | ||||||
| BM306 | Bahar | 3 | 0 | 3 | ||
| Ön Koşulu Olan Ders( ler ) | BM105 |
| Dili | tr |
| Türü | Zorunlu |
| Seviyesi | Lisans |
| Öğretim Elemanı( ları ) | Dr.Öğr.Üyesi Çiğdem ACI |
| Öğretim Sistemi | Yüz Yüze |
| Önerilen Hususlar | Yok |
| Staj Durumu | Yok |
| Amacı | Bu derste, temel amaç Chomsky hiyerarşisindeki dil sınıflarını gramer ve otomata açısından tanımlamaktır. |
| İçeriği | Sonlu ototmataya giriş, deterministik sonlu otomata, düzenli ifadeler, deterministik olmayan sonlu otomata, düzenli diller ve düzenli gramerler, push-down otomata, içerik bağımsız diller, turing makineleri, chomsky hiyerarşisi, karar verilemezlik, hesaplama karmaşıklığı ve NP-bütünlüğü. |
Dersin Öğrenim Çıktıları
| # | Öğrenim Çıktıları |
|---|---|
| 1 | Kombinasyonal yöntemleri kullanarak farklı hesaplama yöntemlerini analiz eder. |
| 2 | Diller, gramerler ve otomata özelliklerini kanıtlamak için geleneksel matematiksel yöntemler uygular. |
| 3 | Farklı problemler için algoritmalar oluşturur ve hesaplamanın farklı makine modelleri üzerindeki doğruluğu hakkında tartışır. |
| 4 | Bazı hesaplama modellerin sınırlamalarını ve olası ispat yöntemlerini tanımlar. |
| 5 | Yazılım araçları kullanarak hesaplamalı problemleri uygular. |
Haftalık Ayrıntılı Ders İçeriği
| # | Konular | Öğretim Yöntem ve Teknikleri |
|---|---|---|
| 1 | Kesikli matematiksel yapılar tekrarı | Anlatım, tartışma |
| 2 | Sonlu otomaya giriş, deterministik sonlu otomata | Anlatım, tartışma |
| 3 | Düzenli ifadeler, deterministik olmayan otomata | Anlatım, tartışma |
| 4 | İçerik bağımsız diller, düzenli diller ve düzenli gramerler | Anlatım, tartışma |
| 5 | Push-Down otomata (deterministik ve deterministik olmayan) | Anlatım, tartışma |
| 6 | İçerik bağımsız ve içerik bağımsız olmayan diller | Anlatım, tartışma |
| 7 | Arasınav | Ölçme ve Değerlendirme |
| 8 | Turing makineleri | Anlatım, tartışma |
| 9 | Church-Turing tezi | Anlatım, tartışma |
| 10 | Deterministik olmayan Turing makineleri, Evrensel Turing Makineleri | Anlatım, tartışma |
| 11 | Özyinelemeli sayılabilir diller, Chomsky hiyerarşisi | Anlatım, tartışma |
| 12 | Karar verilemezlik, Azalma ve Durdurma | Anlatım, tartışma |
| 13 | Bazı hesaplanabilir fonksiyonlar | Anlatım, tartışma |
| 14 | Hesaplama Karmaşıklığı ve NP-bütünlük | Anlatım, tartışma |
| 15 | Hesaplama Karmaşıklığı ve NP-bütünlük | Anlatım, tartışma |
| 16 | Dönem Sonu Sınavı | Ölçme ve Değerlendirme |
Resources
| # | Malzeme / Kaynak Adı | Kaynak Hakkında Bilgi | Referans / Önerilen Kaynak |
|---|---|---|---|
| 1 | Introduction to Theory of Computation, Anil Maheshwari and Michiel Smid, Carleton University, 2012. | 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. | |
| 2 |
Ölçme ve Değerlendirme Sistemi
| # | Ağırlık | Çalışma Türü | Çalışma Adı |
|---|---|---|---|
| 1 | 0.4 | 1 | 1. Ara Sınav |
| 2 | 0.6 | 5 | Son Sınav |
Dersin Öğrenim Çıktıları ve Program Yeterlilikleri ile İlişkileri
| # | Öğrenim Çıktıları | Program Çıktıları | Ölçme ve Değerlendirme |
|---|---|---|---|
| 1 | Kombinasyonal yöntemleri kullanarak farklı hesaplama yöntemlerini analiz eder. | 2͵4͵5͵7 | 1͵2 |
| 2 | Diller, gramerler ve otomata özelliklerini kanıtlamak için geleneksel matematiksel yöntemler uygular. | 2͵4͵5͵7 | 1͵2 |
| 3 | Farklı problemler için algoritmalar oluşturur ve hesaplamanın farklı makine modelleri üzerindeki doğruluğu hakkında tartışır. | 2͵4͵5͵7 | 1͵2 |
| 4 | Bazı hesaplama modellerin sınırlamalarını ve olası ispat yöntemlerini tanımlar. | 2͵4͵5͵7 | 1͵2 |
| 5 | Yazılım araçları kullanarak hesaplamalı problemleri uygular. | 2͵4͵5͵7 | 1͵2 |
Not: Ölçme ve Değerlendirme sütununda belirtilen sayılar, bir üstte bulunan Ölçme ve Değerlerndirme Sistemi başlıklı tabloda belirtilen çalışmaları işaret etmektedir.
İş Yükü Detayları
| # | Etkinlik | Adet | Süre (Saat) | İş Yükü |
|---|---|---|---|---|
| 0 | Ders Süresi | 14 | 3 | 42 |
| 1 | Sınıf Dışı Ders Süresi (Ön çalışma, pekiştirme) | 14 | 3 | 42 |
| 2 | Sunum ve Seminer Hazırlama | 0 | 0 | 0 |
| 3 | İnternette tarama, kütüphane ve arşiv çalışması | 0 | 0 | 0 |
| 4 | Belge/Bilgi listeleri oluşturma | 0 | 0 | 0 |
| 5 | Atölye | 0 | 0 | 0 |
| 6 | Ara Sınav için Hazırlık | 1 | 0 | 0 |
| 7 | Ara Sınav | 1 | 10 | 10 |
| 8 | Kısa Sınav | 0 | 0 | 0 |
| 9 | Ödev | 0 | 0 | 0 |
| 10 | Ara Proje | 0 | 0 | 0 |
| 11 | Ara Uygulama | 0 | 0 | 0 |
| 12 | Son Proje | 1 | 0 | 0 |
| 13 | Son Uygulama | 0 | 0 | 0 |
| 14 | Son Sınav için Hazırlık | 1 | 0 | 0 |
| 15 | Son Sınav | 1 | 10 | 10 |
| 104 | ||||