BİL694 - ÇİZGE KURAMI
| Dersin Adı | Kodu | Yarıyılı | Teori (saat/hafta) |
Uygulama (saat/hafta) |
Yerel Kredi | AKTS |
|---|---|---|---|---|---|---|
| ÇİZGE KURAMI | BİL694 | Herhangi Yarıyıl/Yıl | 3 | 0 | 3 | 8 |
| Önkoşul(lar)-var ise | ||||||
| Dersin Dili | Türkçe | |||||
| Dersin Türü | Seçmeli | |||||
| Dersin verilme şekli | Yüz yüze | |||||
| Dersin öğrenme ve öğretme teknikleri | Anlatım Sorun/Problem Çözme | |||||
| Dersin sorumlusu(ları) | Bölüm Sorumluları (bbm-bologna@cs.hacettepe.edu.tr) | |||||
| Dersin amacı | Bu dersin amacı, çeşitli alanlardaki problemleri çözmek için kullanılabilecek güçlü bir modelleme aracı olan çizge kavramını vermektir. | |||||
| Dersin öğrenme çıktıları |
| |||||
| Dersin içeriği | Temel kavramlar, Özel çizgeler, Eşbiçimlilik, Erişebilirlik, Düzlemsellik, Eular ve Hamilton çizgeleri, Düğüm boyama, Maksimum akış | |||||
| Kaynaklar | ? Ronal Gould,?Graph Theory?, Ben/Cummings Pub.,1988 ? M.N.S. Swamy, K. Thulasiraman,? Graphs, networks, and algorithms?, New York : Wiley, 1981 | |||||
Haftalara Göre İşlenecek Konular
| Haftalar | Konular |
|---|---|
| 1. Hafta | Temel Kavramlar : Yönsüz, yönlü çizge, basit çizge, derece toplamlarına ilişkin teorem, kenar ve düğüm indirimli alt çizgeler, yürüyüş, iz, yol, döngü |
| 2. Hafta | Özel Çizgeler: Tam, düzenli, ikiye ayrılır, tam ikiye ayrılır çizgeler, bitişiklilik, bileşenler, tümleyen, Ramsey problemi |
| 3. Hafta | Eşbiçimlilik, Erişilebilirlik ve uzaklık, Warshall algoritması Çizge işlemleri(düğüm kaydırma, kenar kaydırma, kesme düğümü, köprü) |
| 4. Hafta | Düzlemsellik: Düzlemsel çizgeler, eular formülü, Kuratowski teoremi, düzlemselliğin diğer özellikleri, bir düzlemsellik algoritması |
| 5. Hafta | Derece dizileri: Havel Hakimi teoremi, Erdös-Gallai teoremi, Çizge dizisi testi |
| 6. Hafta | Arasınav |
| 7. Hafta | En kısa yol, minimum yayılım ağacı: Dijkstra?ın algoritması , Kruskal?ın algoritması, Prim?in algoritması |
| 8. Hafta | Eular çizgesi: Eular döngüsü, eular izi, bazı teoremler, önce derinliğine arama, Fleury?un algoritması, Hieholzer?in algoritması |
| 9. Hafta | İki bitişiklilik ve güçlü bitişiklilik: İki bitişiklilik algoritması, yönlü çizgeler için önce derinliğine arama, güçlü bitişiklilik algoritması |
| 10. Hafta | Hamilton çizgesi: Hamilton çizgesi üzerine bazı teoremler Bondy-Chvâtal koşuluna dayalı bir algoritma |
| 11. Hafta | Arasınav |
| 12. Hafta | Düğüm boyama: Renk sayısı, bağımsız küme, 4 renk teoremi, düğüm boyama üzeriene bazı teoremler, sıralı boyama algoritması, Brelaz?ın renk dereceli algoritması |
| 13. Hafta | Maksimum akış: Akış ağları, akış ağlarında kesmeler, temel ford-Fulkerson algoritması |
| 14. Hafta | Bazı özel çizge uygulamaları |
| 15. Hafta | Genel sınava hazırlık |
| 16. Hafta | Genel sınav |
Değerlendirme Sistemi
| Yarıyıl içi çalışmaları | Sayısı | Katkı Payı % |
|---|---|---|
| Devam (a) | 0 | 0 |
| Laboratuar | 0 | 0 |
| Uygulama | 0 | 0 |
| Alan Çalışması | 0 | 0 |
| Derse Özgü Staj (Varsa) | 0 | 0 |
| Ödevler | 4 | 10 |
| Sunum | 0 | 0 |
| Projeler | 1 | 10 |
| Seminer | 1 | 10 |
| Ara Sınavlar | 20 | 20 |
| Genel sınav | 1 | 50 |
| Toplam | 100 | |
| Yarıyıl İçi Çalışmalarının Başarı Notuna Katkısı | 0 | 50 |
| Yarıyıl Sonu Sınavının Başarı Notuna Katkısı | 0 | 50 |
| Toplam | 100 | |
AKTS (Öğrenci İş Yükü) Tablosu
| Etkinlikler | Sayısı | Süresi | Toplam İş Yükü |
|---|---|---|---|
| Ders Süresi | 12 | 3 | 36 |
| Laboratuvar | 0 | 0 | 0 |
| Uygulama | 0 | 0 | 0 |
| Derse özgü staj (varsa) | 0 | 0 | 0 |
| Alan Çalışması | 0 | 0 | 0 |
| Sınıf Dışı Ders Çalışma Süresi (Ön Çalışma, pekiştirme, vb) | 4 | 10 | 40 |
| Sunum / Seminer Hazırlama | 1 | 20 | 20 |
| Proje | 1 | 25 | 25 |
| Ödevler | 4 | 10 | 40 |
| Ara sınavlara hazırlanma süresi | 2 | 20 | 40 |
| Genel sınava hazırlanma süresi | 1 | 15 | 15 |
| Toplam İş Yükü | 25 | 103 | 216 |
Dersin Öğrenme Çıktılarının Program Yeterlilikleri İle İlişkilendirilmesi
| D.9. Program Yeterlilikleri | Katkı Düzeyi* | ||||
|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | |
| 1. Mezunlar, Bilgi Yığını (Bilgisayar Bilimleri kapsamındaki tüm temel alanlar) ile tanımlanan Bilgisayar Bilimleri alanına hakim olmalıdır. | X | ||||
| 2. Mezunlar, soyutlama, karmaşıklık ve evrimsel değişim gibi sıkça adı geçen konular ve ortak kaynak, güvenlik ve paralellik gibi genel ilkeler hakkında bir anlayışa sahip olmalıdır. Mezunlar, bu konular ve ilkelerin bilgisayar bilimleri alanında geniş bir uygulama alanına sahip olduğunun farkında olmalı ve bunların sadece tanıtıldıkları alanlarla ilgili olmadığını da göz önünde bulundurmalıdır. | X | ||||
| 3. Bilgisayar Bilimlerindeki temel bir husus teori ve pratiğin karşılıklı etkileşimine dair anlayış ve onlar arasındaki esas bağlantılardır. Bilgisayar Bilimlerinden mezun olanlar teori ve pratiğin nasıl birbirini etkilediğini anlamak durumundadır. | X | ||||
| 4. Bilgisayar Bilimlerinden mezun olanlar detay ve soyutlamanın farklı düzeylerinde düşünmelidir. Bu anlayış, bilgisayar sistemlerinin yapısını ve onların kurulumunda ve analizinde izlenen süreçlerin değerini anlamak için çeşitli bileşenlerin detaylarının gerçekleştirilmesinde etkin olmalıdır. Mezunlar, bir bilgisayar sisteminin, insanlar ve fiziksel dünyayı da kapsayacak şekilde hangi ortamda işlevsel olabileceğinin farkında olmalıdır. | X | ||||
| 5. Mezunlar, sadece kod yazma ve bitlerle oynama değil, aynı zamanda edindikleri bilgi birikimini araştırmalarındaki gerçek problemleri çözmede de kullanabilmelidir. Mezunlar herhangi bir teknik veya bilimsel problemleri kendi başlarına çözebilmeli ve her türlü problem için başka çözüm önerileri getirebilmelidir. Verilen bir problemin birden fazla çözümünün olduğunun ve bu çözümler arasından birini seçmenin yalnızca teknik bir eylem olmadığının, çünkü bu çözümlerin insanların hayatlarında gerçek bir | X | ||||
| 6. Mezunların edindikleri bilgi birikimini başarılı bir şekilde uyguladıklarından emin olmak için, bütün mezunlar en az bir kapsamlı projede yer almalıdır. Çoğu durumda, bu deneyim bir yazılım geliştirme projesi olacaktır, ancak diğer deneyimler de özel durumlarda uygundur. Bunun gibi projeler öğrencileri birleştirici olmaya teşvik etmeli, potansiyel çözümlerin hesaplamalarını gerektirmeli ve tipik ders projelerine göre daha geniş ölçekli çalışmalar yapmalarını gerektirmelidir. Öğrenciler, proje de | X | ||||
| 7. Bilgisayar Bilimleri mezunları, hesaplama alanının çok hızlı bir şekilde geliştiğinin farkında olmalıdır. Belirli diller ve teknoloji platformları zaman içinde değişebilir. Bu nedenle, mezunlar öğrenmeye devam etmeleri ve becerilerini de bu yönde geliştirmeleri gerektiğinin farkında olmalıdır. Bu beceriyi geliştirmek için, öğrenciler eğitimleri boyunca temel öncelikli ilkelerin yanında çeşitli programlama dillerine, araçlara ve teknolojilere maruz bırakılmalıdır. Mezunlar araştırmalarına devam e | X | ||||
| 8. Mezunlar, bilgisayar teknolojisinin kurulumu ve kullanımında sosyal, yasal, etik ve kültürel hususların farkında olmalıdır. Bu hususlara kişisel ve profesyonel ilkelerle güdümlenmiş olarak bilinçli bir perspektiften yanıt vermelilerdir. Aynı zamanda sosyal, yasal ve etik standartların uluslar arası olarak değiştiğinin farkında olmalıdırlar. | X | ||||
| 9. Mezunlar hem İngilizce hem de Türkçe dillerinde teknik terimlere vakıf olmalıdır. Teknik problemler ve çözümleri hakkında çeşitli dinleyici gruplarına kısa ve öz sunum yapma becerileri olmalıdır. Bu, yüz yüze, yazılı veya elektronik iletişimi içerebilir (Türkçe ve İngilizce'de). Takım üyeleri halinde etkili bir şekilde çalışmaya hazırlıklı olmalıdırlar. Mezunlar, tamamlama zamanını, öncelikleri ve ilerlemeyi de göz önünde bulundurarak kendi öğrenme ve gelişimlerini yönetebilmelidir. | X | ||||
| 10. Platformlar, gömülü mikro-sensörlerden yüksek performanslı öbeklere ve dağıtık bulutlara kadar değişebilir. Bilgisayar uygulamaları modern yaşamın neredeyse bütün yönleri üzerinde etkilidir. Mezunlar hesaplamada var olan bütün imkanlar üzerinde bir anlayışa sahip olmalıdır. | X | ||||
| 11. Mezunlar, hesaplamanın birçok farklı alanla etkileşim içerisinde olduğunu anlamalıdır. Birçok problem için çözümler hem hesaplama becerileri hem de alan bilgisi gerektirir. Bu nedenle, mezunlar kariyerleri boyunca farklı alanlardaki uzmanlarla iletişim kurmalı ve onlardan öğrenmelidir. | X | ||||
| 12. Mezunlar, uzman düzeyinde gerekli olan bilgi birikimlerini geliştirmeli ve bilimsel yöntemleri bilimsel problemleri çözmek için kullanabilmelidir. Mezunlar özgün araştırma tanımlayabilmeli ve yürütebilmelidir. | X | ||||
*1 En düşük, 2 Düşük, 3 Orta, 4 Yüksek, 5 Çok yüksek