Ders Kodu | Ders Adı | Sınıf | Kredisi | Ders Saati | Haftalık Ders Saati(Teorik) | Haftalık Ders Saati(Uygulama) | Haftalık Ders Saati(Laboratuvar) |
---|---|---|---|---|---|---|---|
GNA 3377 | Grafiklerdeki temel algoritmalar | Üçüncü Sınıf | 5 | 150 | 15 | 30 |
Öğrencileri grafik teorisinin temel kavramlarıyla tanıştırmak ve onları kullanabilecekleri duruma getirmek; grafik teorisinde problemlerin sunumuna ve bunları çözme yöntemlerine hakim olmak; temel teorik ve grafiksel algoritmalara hakim olmak; Çeşitli alanlarda uygulanan problemler grafik teorisi açısından incelenmiştir.
kritik düşünce, beyin fırtınası, fikir alışverişi, tartışma, problem çözme yöntemleri.
1 | Graf teorisinin temel kavramlarını, graf türlerini ve temsil yöntemlerini bilir |
2 | Grafiklerde en kısa yolları bulmak ve ağdaki maksimum akışı bulmak için algoritmalar kullanabilir |
3 | Ağaç kavramını ve ağaç özelliklerini bilir |
4 | Euler ve Hamilton döngülerinin kavramlarını ve bunların varoluş koşullarını bilir |
5 | Düzlemsel ve düzlemsel grafik kavramlarını, bir grafiğin düzlemsel olması için gerekli ve yeterli koşulları, bir grafiğin kromatik sayısını tahmin etme yöntemlerini bilir |
6 | Grafik sağlama yöntemlerini kullanır |
7 | Grafiklerdeki en kısa yolları bulma problemlerini çözmek için klasik algoritmaları kullanır |
8 | En küçük ağırlıktaki ahşap çerçeveyi oluşturabilme |
9 | Euler ve Hamilton döngülerini grafiklerde bulabilir |
10 | Düzlemsel bir grafiği bir düzlemle ilişkilendirebilir, grafiğin en uygun rengini bulabilir |
Haftalık Konu | Değerlendirme Yöntemi | |
---|---|---|
1 | Grafik teorisinin tarihi. Suç ortaklığı. Grafikler ve benzeri nesneler. Grafiklerin izomorfizmi. Değerlik. | |
2 | Grafikleri aktarmanın yolları. Grafikler üzerinde işlemler. | |
3 | Grafik sayısı. Dahili grafikler. Grafik türleri. | |
4 | Yollar, zincirler, döngüler. Rota sayısını belirleme. Rotaların ve döngülerin varlığını belirleme. | |
5 | Bir grafiğin metrik özellikleri. Grafiğin geçişi. | |
6 | İletişim bileşenleri. Grafiklerde ve digraflarda bağlantı. Yoğuşma oluşturma algoritması. Baz ve antibazı tanımlayın. | |
7 | Çevrimiçi akışlar. Ford-Falkerson teoremi. Maksimum akışı bulmak için algoritma. | |
8 | Ağırlıklı grafiklerde en kısa yollar. En kısa yolları bulmanın hesaplanması. Dijkstra'nın algoritması. Ford-Bellman algoritması. | |
9 | Ağaçlar ve özellikleri. Ağaçların merkez noktası. Prufer kodu | |
10 | Ağaçlardaki sorunlar. Boğumlu ağaçların zincirlenmesi. Budaklı ağaçları saymak. | |
11 | Minimum ağaçlar. Kraskal'ın algoritması. Prim'in algoritması. Yönlendirilmiş, sıralı ve ikili ağaçlar. | |
12 | Temel döngüler ve temel bölüm sistemleri. Bir dizi bağımsız döngü. Temel döngülerin oluşturulması için algoritma. Bir dizi bağımsız bölüm. Temel bölümlerin oluşturulması için algoritma. | |
13 | Euler çevrimleri (zincirler). Euler çevrimlerinin varlığı için gerekli ve yeterli koşullar. Euler döngülerini bulma algoritması. Hamilton çevrimleri. Hamilton çevriminin varlığı için yeterli koşullar. Hamilton döngülerini bulmak için algoritma (cebirsel yöntem). | |
14 | Bağımsız (iç kararlılık) köşe kümesi kavramı. Maksimum bağımsız kümeleri aramak için algoritma. Baskın (dış stabilite) zirveler kümesi kavramı. Minimal baskın kümeleri aramak için algoritma. | |
15 | Düzlemsel grafikler. Düzlemsel grafikler. Bir grafiği bir düzleme eşlemek için algoritma. Bir grafiğin kromatik sayısı. Grafik renklendirme algoritmaları. |
PÇ1 | PÇ2 | PÇ3 | PÇ4 | PÇ5 | PÇ6 | PÇ7 | PÇ8 | PÇ9 | PÇ10 | PÇ11 | PÇ12 | PÇ13 | PÇ14 | PÇ15 |
---|
Ders Kitabı / Malzemesi / Önerilen Kaynaklar | ||
---|---|---|
1 | A. Tolep, B. Yeskarayeva. Graph theory. Educational tool. - Turkestan, 2019. - 115 p.. 2. A.Tolep, B. Yeskarayeva. Discrete mathematics. Theory and practice. -Shymkent, 2020. -132 p | |
2 | Abildayeva G. Discrete Mathematics: An Electronic Textbook. - Karaganda: KMTU, 2017 | |
3 | Shevelev Yu. Discrete mathematics: textbook. - 4th edition, st. - St. Petersburg: Lan, 2022. http | |
4 | www.rmebrk.kz |