İSTANBUL MEDİPOL ÜNİVERSİTESİ
METİN İŞLEME ALGORİTMALARI DERS ÇIKTI TABLOSU
Dersin Kodu ve Adı
ELED111531, ELEY111531 / Metin İşleme Algoritmaları
Ders Saati
Haftada 3 saat
Bölüm/Program
Elektrik Elektronik Bölümü / Elektrik Elektronik ve Siber Sistemler Lisansüstü Programı
Dersin Dili
İngilizce
Dersin Türü
Seçmeli
Dersi Verenler
Doç. Dr. M. Oğuzhan Külekci
Dersle İlgili Görüşme
Saatleri
Perşembe 15:00-17:00
Dersin Amacı
Öğrencilerin verilen tek boyutlu bir veri üzerinde hızlı arama yapma, hızlı erişim için dizin
oluşturma, ve veri üzerinde dizgi bulmaya yönelik algoritmaları öğrenmesi, bu teknikleri
verilen bir problemde uygulayabilme becerisini kazanması
Öğrenci bu dersin sonunda;
Öğrenme Çıktıları ve Alt
Beceriler
1. Tek boyutlu bir dizi üzerinde tarama işleminin nasıl hızlı bir şekilde yapılabileceğini
anlatabilecektir.
1.1. Önek ve sonek tabanlı çözümleri açıklayabilir.
1.2. Öznitelik tabanlı çözümleri açıklayabilir.
1.3. Özdevinir sistemler üzerine çözümleri açıklayabilir.
1.4. Bilgisayar yapısından kaynaklanan bit-parelellik ve vektörizasyon ile nasıl daha hızlı arama
yapılabileceğini açıklayabilir.
1.5. Bu yöntemleri birbirleri ile karşılaştırarak tartışabilir, sınıflandırabilir.
1.6. Hangi yöntemin ne tür veride daha iyi sonuç verdiğini değerlendirebilir.
1.7. Çoklu dizgi eşleştirme metodlarını tartışabilir.
1.8. Dinamik programlama yapabilir.
2. Tek boyutlu veri üzerinde dizin oluşturma tasarlayabilir.
2.1. İlgili veri yapılarını açıklayabilir.
2.2. Sonek ağaçları/katarları ile tersinir dizinlerin farklarını ve performanslarını tartışabilir.
2.3. Hangi ihtiyaç için handi dizin yönteminin iyi olduğunu anlatabilir.
2.4. BWt transformunu ve transform ile aram yapmayı anlatabilir.
Genel Yeterlilikler
Üretken, yaratıcı, sorgulayan, bir yabancı dili etkin kullanma,
Haftalara Göre İşlenecek
Konular
1. Metin işleme algoritmalarının genel tanıtımı, temel kavramlar ve notasyon
2. Önek arama tabanlı çözümler: Kaba-kuvvet çözümü, Morris-Pratt (MP) and
Knuth-Morris-Pratt (KMP) algoritmaları
3. Sonek tabanlı çözümler: Boyer-Moore algoritması ve bazı değişik tipleri: Horspool, quick
search, maximal shift, optimal mismatch algoritmaları.
4. Özdevinir tabanlı çözümler: Sonek özdevinir yapısı ve Aho-Corasick algoritması, DAWG
çizgeleri, tersine DAWG eşleştirmesi, BOM algoritması.
5. Öznitelik tabanlı çözümler: Filtreleme yaklaşımı, Karp-Rabin ve q-hash algoritmaları.
6. Bit-paralelizm kullanan algoritmalar: Shift-Or, BNDM, ve BLIM algoritmaları
7. SIMD parelelizmini kullanan algoritmalar: SIMD kavramı, komut seti, EPSM ve SSEF
algoritmaları.
8. Çoklu dizgi eşleştirme: Aho-Corasick makiması, Wu-Manber (agrep) algoritması, ve diğer
tekil dizgi eşleştirme algoritmalarının çoklu eşleştirmeye uyarlanması.
9. Yaklaşık dizgi eşleştirme: Dizgi yakınlığı metrikleri ve dinamik programlama,
Smith-Waterman algoritması.
10. Genel/ve yerel dizi eşleştirme, en uzun ortak dizge bulma, güvercin-yuvası prensibi
tabanlı yaklaşık dizgi eşleştirme kavramı .
11. Dizin oluşturmanın temelleri ve temel dizin veri yapıları soneke ağaçları, katarları ve bazı
değişik uyarlamaları
12. Kelime tabanlı dizinler : Tersinir dizinler ve arama motorlarının temel arama yaklaşımı.
13. Dizin oluşturmada ileri veri yapıları: Burrows—Wheeler dönüşümü ve FM-index.
14. Diziler üzerinde tekrarları, en kısa tekil dizgileri ve en uzun tekrarları tesbit etme
algoritmaları
Öğretim ve Teknikleri
Anlatım, gösterim, uygulama-alıştırma, problem çözme, rapor hazırlama
Dersin Koşulları
Kaynaklar
Derslere katılım, ödev yapma, verilen ders notlarını ve kaynakları okumak ve araştırmak, vize
ve final sınavlarına katılım
Ders Notu
Ders notları ve okumalar ilgili derslerde dağıtılacaktır.
Önerilen
Kaynaklar
1. Jewels of Stringology: Text Algorithms, Maxime Crochemore, Wojciech Rytter,World
Scientific Publishing
2. Algorithms on Strings, Maxime Crochemore, Christophe Hancart, Thierry Lecroq,
Cambridge University Press
3. Flexible pattern matching in strings: Practical on-line search algorithms for texts and
biological sequences Gonzalo Navarro, Mathieu Raffinot, Cambridge University Press
Download

istanbul medipol üniversitesi metin işleme algoritmaları ders çıktı