BİL207U-VERİ YAPILARI
Ünite 1: Veri Yapılarına Giriş
Giriş
Teknolojideki son gelişmelerin çoğu, sorunları çözmek için sistem kaynaklarının etkin kullanımı sayesinde hayata geçmektedir ve bu genellikle algoritmaların etkin bir şekilde geliştirilmesi, uygulanması ve veri yapılarının akıllıca kullanılmasıyla gerçekleştirilmektedir.
Algoritma ve veri yapılarının diline; bilgisayar bilimcileri, yazılım geliştiricileri, veri bilimcileri ve diğer sektör çalışanları da dahil olmak üzere işi hesaplamaya dayanan herkes tarafından hâkim olunması gerekmektedir. İlgili teknoloji sektörlerindeki işletmelerde en çok karşılaşılan sorunlardan birinin de bu alan olduğu görülmektedir.
Veri Yapıları
Veri, teknik anlamına bakılacak olursa bir nesne hakkındaki tüm niteliksel ve niceliksel değişkenliklerin sayısal değeri olduğu söylenebilir. Bilgisayar verileri ise bilgisayar tarafından işlenen ve saklanan ses, video, metin, resim gibi çeşitli türlerdeki verilerdir. Ham veriler, verileri en temel dijital biçiminde tanımlamak için kullanılan bir terimdir. Formülleştirilmeye veya kayıt altına alınmasına gerektiği düşünülen tüm fikir ve olaylardır. Ham veriler, doğru şekilde ve karıştırılmadan bulundurulmalı ve anlaşılır bir şekilde düzenlenmelidir. Veri tüm alanlarda kullanılabilir fakat tek başına bir anlam ifade etmediği için yorumlanmaya ihtiyaç duymaktadır.
Veri yapısı ise bilgisayardaki dijital verileri depolamanın ve bu veriler üzerinde farklı eylemleri gerçekleştirmenin en kolay yolunu sağlayan bir veri ögeleri grubudur. Veri yapısı, bir bilgisayardaki verileri etkin bir şekilde kullanılabilecek şekilde düzenlemenin özel bir yoludur. Veri yapıları, verilerin bilgisayar ortamında yönetilmesi ve depolanmasını sağlayan veri nesneleri koleksiyonu olarak tanımlanabilir. Çeşitli veri yapıları türleri olarak: ağaç (tree) yapıları, yığınlar (stack), diziler (array), kuyruklar (queues), listeler vb. örnek gösterilebilir. Veri yapısı kullanmadaki amaç, farklı görevlerin uzay ve zaman karmaşıklığını azaltmaktır.
Zaman karmaşıklığı, algoritma tarafından her bir talimat setini yürütmek için geçen zamandır. Basit bir problemin farklı yöntemlerle çözülebileceği durumlarda en verimli algoritmayı seçmenin her zaman daha iyi sonuç vereceği unutulmamalıdır. Uzay/Alan karmaşıklığı genellikle algoritma tarafından tüketilen bellek miktarı olarak adlandırılır. Yardımcı alan ve girdi alanı olmak üzere iki farklı alandan oluşmaktadır.
Veri Türü
Veri türü, derleyiciye veya yorumlayıcıya programcının verileri nasıl kullanmayı planladığını söyleyen bir veri sınıflandırmasıdır. Çoğu programlama dili, tamsayı (int), gerçek (reel), karakter (char) veya dize (string) ve Boolean dahil olmak üzere çeşitli veri türlerini desteklemektedir.
Veri türleri, geçerli bir C# değişkeninin tutabileceği veri türünü belirtmektedir. C#, güçlü bir şekilde yazılmış
programlama dili olduğu için her veri türü (tamsayı, karakter, kayan noktalı sayı vb.) programlama dilinin bir parçası olarak önceden tanımlanmıştır. Ayrıca belirli bir program için tanımlanan tüm sabit veya değişkenlerin, veri türlerinden biri ile tanımlanması gerekmektedir (kitabınızın 4-5 sayfasında C# Veri Tipleri tablo 1.1 ve Veri tipleri ile veri yapılarının karşılaştırması tablo 1.2 gibi).
Veri Yapıları Neden Gereklidir?
Bilgisayar algoritmaları daha karmaşık hâle geldikçe dolaylı olarak daha fazla veri kullanılır, bu da programların verimli şekilde çalışmasını etkileyebilir ve bazı sorunları da beraberinde getirebilir. Sıralanacak endişeler, veri yapılarına neden ihtiyaç duyulduğunun sebebi olduğu söylenebilir;
• Çok sayıda istek • İşlem hızı • Veri arama
Veri yapılarını kullanmanın avantajlarını ise şu şekilde sıralayabiliriz:
• Soyutlama (abstraction) • Hafızanın verimli kullanımı • Yeniden kullanılabilirlik
Veri Yapısının Sınıflandırılması
Veri yapısı, günlük hayatımızda birçok farklı kullanım alanına sahiptir. Farklı matematiksel ve mantıksal problemleri çözmek için kullanılan birçok farklı veri yapısı vardır. Veri yapısını kullanarak nispeten kısa bir sürede çok büyük miktarda veri işlenebilir ve düzenlenebilir (kitabınızın 6 sayfasında Veri Yapısı Sınıfları şekil 1.1 gibi).
.NET Ortamı Kurulumu
Açık kaynak kodlu .NET Core platformu, Microsoft tarafından geliştirilen .NET platformunun devamı olan bir yazılım geliştirme platformudur. .NET platformu her ne kadar yazılım dilinden bağımsız bir geliştirme platformu olsa da sadece Windows işletim sistemi ortamında çalışacak şekilde tasarlanmıştır. 2016 yılında .NET platformlarının işletim sistemi bağımsız olarak çalışabilecek yeni versiyonu olan .NET Core yazılım geliştirme platformunu kullanıma sunmuştur. Böylece Windows işletim sisteminde hazırlanan bir kod, Linux işletim sisteminde de aynı şekilde çalışacaktır.
.NET framework’te iki önemli bileşen mevcuttur. Bunlar .NET kütüphanesi ve CLR’dir. Geliştirilen programların çalışması CLR (Common Language Runtime) yani ortak çalışma zamanı yönetmektedir. CLR, .NET kütüphanesi ile birçok fonksiyonu bünyesinde barındıran, sınıf sistemine göre kategorize edilmiş bir kütüphanedir.
Algoritma, Akış Şeması ve Analizi
Algoritma; adını 9.yy.’da yaşamış, Özbekistan’ın Harezm şehrinde doğmuş olan Ebu Abdullah Muhammed İbn Musa el-Hârizmî’den almıştır. Algoritma ilk defa “Hisab el-cebir
ve el-mukabala” kitabında ele alınmıştır. İlk başlarda Arap sayılarını kullanarak problemlere aritmatik çözümler bulma olarak kullanılan algorizm, daha sonraları Algoritma adını alarak daha genel kapsamda kullanılmaya başlanmıştır.
Programlama algoritması; bir problemi çözmek için kullanılan bir prosedür, formül veya izlenmesi gereken yola denmektedir. Bu prosedürdeki adımlar, bir işlemin nasıl yapılacağının açıklandığı bir dizi belirli eylemi gerçekleştirmeye dayanmaktadır. Ayrıca bilgisayar, bu adımları her seferinde tam olarak aynı şekilde gerçekleştirmektedir. Bir algoritma, girdilerden oluşan bir prosedürü izleyerek çalışır. Tüm girdiler işlenerek çıktı olarak da bilinen bir sonuç oluşturulmaktadır.
Bir algoritmanın özellikleri:
• Kesinlik – adımlar kesin olarak belirtilmelidir. • Benzersizlik – her adımın sonucu benzersiz bir şekilde tanımlanır ve yalnızca önceki adımların girdisine ve sonucuna bağlıdır. • Sonluluk – sınırlı sayıda komut yürütüldükten sonra algoritma durmalıdır. • Girdi – algoritma girdi alır. • Çıktı – algoritma çıktı üretir. • Genellik, Uygulanabilirlik – algoritma bir dizi girdiye uygulanır.
Programlama algoritmalarının avantajlarını şu şekilde listeleyebiliriz:
• Belirli bir sorunun çözümünün adım adım temsili, anlaşılmasını kolaylaştırır. • Kesin bir prosedür kullanır. • Belirli bir programlama diline bağlı değildir. • Bir algoritmadaki her adımın, hata ayıklamayı kolaylaştıran kendi mantıksal sırası vardır. • Algoritmada problem daha küçük parçalara veya adımlara bölünür, bu nedenle programcının onu gerçek bir programa dönüştürmesi daha kolaydır. • Takım çalışmasını kolaylaştırır.
Algoritma Tasarımı
Algoritma yazmak için ön koşul olarak aşağıdakilere ihtiyaç vardır:
• Bu algoritma ile çözülecek problemin net tanımı yapılmalıdır. • Problem çözülürken problemin kısıtları göz önünde bulundurulmalıdır. • Sorunu çözmek için alınacak girdi belirlenmelidir. • Sorun çözüldüğünde beklenen çıktı belirlenmelidir. • Problemin çözümü, verilen kısıtlamalar dahilinde olmalıdır.
Akış Şemaları
Akış şeması, sistemdeki bir akışı veya dinamik ilişkiler kümesini temsil eden diyagram için kullanılan bir terimdir. Akış şeması terimi aynı zamanda akış diyagramı ile eş
anlamlı olarak da kullanılmaktadır. Akış şemaları, karmaşık bir sistemi yapılandırmak ve sıralamak ya da ögelerin altında yatan yapıyı ve bunların etkileşimini ortaya çıkarmak için kullanılır. Akış diyagramı terimi teoride ve pratikte farklı anlamlarda kullanılmaktadır. Genel olarak akış diyagramı ve akış şeması, bir sürecin gösteriminde birbirinin yerine kullanılabilir.
Akış şemaları, algoritmanın şekilsel ve görsel olarak gösterimi için kullanılmaktadır. Algoritmanın aksine, programın başlangıcından sonuna kadar tüm adımları geometrik formlarla temsil edilir. Her geometrik form ve sembol, bir komut veya işi temsil etmektedir bu nedenle algoritmadan farklı olarak her adım için bir açıklama yapma ihtiyacı yoktur.
Akış Şemalarında Kullanılan Şekiller
Akış şemalarındaki şekiller, algoritmanın en net ve anlaşılır şekilde gösterimi için kullanılmaktadır. Akışta kullanılan şekillerin içlerine; algoritmadaki gibi uzun atamalar, karşılaştırma ve uzun değişken isimleri yazılması tavsiye edilmez. Şekiller anlamayı zorlaştırmayacak bir biçimde kullanılmalıdır (kitabınızın 11. Sayfasında Akış Şeması Şekilleri tablo 1.3 gibi).
Büyük O Notasyonu (Big O Notasyonu)
Basit bir ifade ile Big O notasyonu (Büyük O notasyonu), cebirsel terimler kullanarak kodun karmaşıklığının açıklanmasıdır. Big-O notasyonu, bir algoritmanın performansını veya zaman karmaşıklığını (time complexity) hesaplamak için kullanılır.
Zaman Karmaşıklığı (Time Complexity)
Bir algoritmanın çalışması için gerekli olan süreye zaman karmaşıklığı denmektedir. Buradaki süre; saniye olarak geçen zaman değil, gerçekleştirilen işlem sayısına göre hesaplanmaktadır.
Bir algoritmanın büyük girdiler karşısındaki davranışını inceleyen matematiksel yönteme Asimptotik analiz adı verilmektedir. Algoritma adımlarının çalışması için gerekli sürenin yani zaman karmaşıklığının alt ve üst sınırlarının matematiksel olarak gösterilmesini sağlayan bir algoritma analizi metodudur. Algoritmaların asimptotik analizi, Büyük O notasyonu ile ifade edilmektedir.
Big O Notasyonu’nun Yaygın Çeşitleri
Big-O Notation’ın çeşitleri sadece bunlarla sınırlı değildir fakat karşılaşmanız en muhtemel olanları şu şekilde sıralayabiliriz:
• O(1) - Sabit Zaman Karmaşıklığı • O(N) - Doğrusal Zaman Karmaşıklığı • O(LogN) - Logaritmik Zaman Karmaşıklığı • O(NLogN) - Doğrusal Aritmik (Linearitmik) Zaman Karmaşıklığı • O(sqrt(N)) - Kare Kök Zaman Karmaşıklığı • O(N²) - Kuadratik Zaman Karmaşıklığı • O(N³) - Kübik Zaman Karmaşıklığı • O(N^c) - Polinom Zaman Karmaşıklığı
• O(c^N) - Üstel Zaman Karmaşıklığı • O(N!) - Faktöriyel Zaman Karmaşıklığı
Ekran Çıktısı
Zaman karmaşıklığı, algoritmalar için 3 durum sunmaktadır:
• En iyi durum (Best case) • Ortalama durum (Average case) • En kötü durum (Worst case)
Yazılım geliştiriciler genellikle en kötü senaryo olan Big O için çözüm üretmektedir çünkü algoritmanın her zaman en iyi veya ortalama durumlarda çalışması beklenemez. “En kötü senaryoda algoritmam bu kadar hızlı çalışacaktır.” gibi analitik ifadeler yapılmasını sağlar.