Taban Aritmetiği ve ASCII kodları

ASCII (American Standard Code for Information Interchange), bilgisayarlarda ve internette metin verileri için en yaygın karakter kodlama biçimidir. ASCII, siber güvenlik sistemlerinde şifreleme ve veri güvenliğini sağlayan temel araçlardan biridir. Bütün metin karakterleri, sosyal ağlarda kullanılan şifreler, ASCII (Amerikan Bilgi Değişimi İçin Standart Kod) karakter kümesinden seçilen harfler, sayılar ve sembollerle oluşturulur.  

Metin ve şifrelerde girilen her bir karakter ASCII karakter kümesinde belirli bir sayısal değere karşılık gelir. Standart ASCII kodlu verilerde, 128 alfabetik, sayısal veya özel ek karakter ve kontrol kodu için benzersiz değerler vardır. Yıllar içinde, orijinal 128 karakter kümesini ek semboller ve karakterlerle genişleten birkaç ASCII genişletilmiş küme ortaya çıkmıştır. (Resim: En sık kullanılan büyük ve küçük harf latin alfabesi karakterleri ve bazı sembollerin ASCII kodları)

 

Karatsuba Çarpım Algoritması

Çarpma işlemi, toplama işlemine göre daha karmaşık yapılı bir işlemdir. Çarpma işleminde sola kaydırma işlemi yaparak alt alta basamak sayısı kadar işlem yapılmış olur. Yani 3 basamaklı bir sayı ile 3 basamaklı bir sayı çarpılırsa 3²=9 kadar çarpma işlemi yapılır. 

4 basamaklı bir sayı ile 4 basamaklı bir sayı çarpılırsa 4²=16 kadar çarpma işlemi yapılır. 5 basamaklı bir sayı ile 5 basamaklı bir sayı çarpılırsa 5²=25 kadar çarpma işlemi yapılır. Bu şekilde devam edildiğinde n basamaklı bir sayı ile n basamaklı bir sayı çarpılırsa n² kadar çarpma işlemi yapılır. Bu nedenle klasik çarpma algoritmasında basamak sayısı arttıkça çarpım sonucunu bulmak daha zor hale gelir. Rus Matematikçi Anatoly Karatsuba, özellikle büyük basamaklı sayıların çarpımını daha kolay hesaplamak için yeni bir çarpım algoritması yazmıştır ve bu yönteme Karatsuba Algoritması adı verilmiştir. Bu algoritmada amaç; çarpılacak sayıları alt gruplara bölerek daha az sayıda işlem yaparak sonuca ulaşmaktır. 

 

Çarpma işlemi bilgisayar aritmetiğindeki en önemli işlemlerden biridir. Karatsuba algoritması, çarpma işlemini basitleştirerek işlemlerin verimliliğini arttırmak, işlem maliyetini ve süreyi azaltmak için geliştirilen algoritmalardan biridir. Klasik yöntemde n bitlik iki tamsayının toplanması O(n) bit işlemi gerektirmektedir. İki n bitlik tamsayının çarpılması ise O(n²) bit işlemi gerektirmektedir. Karatsuba algoritması iki n bitlik sayının çarpılması için böl ve fethet (divide and conquer) tekniğini kullanır ve bu algoritmada O(n^log3) bit işlemi gerekir. Karatsuba algoritması çarpma işleminde bazı çarpmaları yapmak yerine daha az maliyetli olan toplama ve çıkarma işlemleriyle değiştirerek işlem sayısını en aza indirmeyi sağlayarak işlemlerin daha hızlı sonuca ulaştırır. Karatsuba algoritması küçük basamaklı (dijit) sayılar için klasik çarpma algoritmasından daha yavaş çalışmaktayken daha büyük basamaklı sayılar için çarpma işlemi yapıldığında daha hızlı ve verimli bir sonuç sunar.

Karatsuba algoritması çarpma işlemine göre 2 basamaklı iki sayıyı çarpmak istediğimizde, önce sayıları anlamlı bloklara ayırıp işlemleri kolaylaştırırız. Yukarıda verilen akış şemasına göre önce onlar basamağındaki iki sayıyı çarparız. (A) Sonra sayıların birler basamaklarındaki sayıları çarparız. (B) Arkasından her iki sayının da basamaklarını toplayıp bunları kendi arasında çarparız.(C) Bütün sonuçlar bulunduktan sonra her iki sayının da basamaklarını toplayıp bunları kendi arasında çarptığımız sonuçtan (C) diğer bulduğumuz iki sonucu çıkartırız. D=(C-A-B). En sonunda ayırma işlemine göre bulunan A,B ve D sonuçlarını blok içinde bulunduğu onluk bölük içinde A.10ⁿ +D.10^(n/2)+B biçiminde yazarak işlemi bitiririz. Burada klasik çarpmada 2 dijitli iki sayının çarpımında 2*2=4 işlem yapmak yerine sadece 3 çarpma işlemi yaparak daha kolay olan toplama ve çıkarma işlemleri ile sonuca ulaşılmış olur. Böylece bilgisayar programlamada büyük basamaklı sayılarda bu işlemleri yapmak zaman açısından daha verimli hale gelir.

Karatsuba algoritması çarpma işlemine göre 3 basamaklı (dijit) olarak verilen iki tane sayıyı çarpmak istediğimizde, önce sayıları anlamlı ikişerli uygun bloklara ayırıp işlemleri kolaylaştırırız. Yukarıda verilen akış şemasına göre önce bu bloklarda ayrı ayrı çarpma işlemi uygulayarak sonuca ulaşırız.

 

Karatsuba algoritması çarpma işlemine göre 4 basamaklı (dijit) olarak verilen iki tane sayıyı çarpmak istediğimizde, önce sayıları anlamlı ikişerl ikişer uygun bloklara ayırıp işlemleri kolaylaştırırız. Yukarıda verilen akış şemasına göre önce bu bloklarda ayrı ayrı çarpma işlemi uygulayarak sonuca ulaşırız.

Kaynakça

1.https://www.geeksforgeeks.org/karatsuba-algorithm-for-fast-multiplication-using-divide-and-conquer-algorithm/

2.https://brilliant.org/wiki/karatsuba-algorithm/

3.Karatsuba ve nikhilam çarpma işlemi algoritmalarının farklı bit uzunlukları için performanslarının karşılaştırılması, Can Eyüpoğlu, Ahmet Sertbaş, İstanbul Ticaret Üniversitesi Fen Bilimleri Dergisi Yıl:14 Sayı: 27 Bahar 2015 s. 55-64 

 

Karatsuba Çarpım Algoritması Konu Anlatım Özetini indirmek için tıklayınız. (PDF)

MSÜ-2025 Sınavı Matematik Çözümleri (%10)

(Milli Savunma Üniversitesi Askeri Öğrenci Aday Belirleme Sınavı) MSÜ 2025 Sınavı YKS provası olması açısından önemli bir sınav oldu. Hedefi askeri okullar olanlar için ciddi bir sınav olmakla birlikte MSÜ sınavı YKS'ye girecek olan adaylar için de kendilerini resmi bir ortamda test etmek amacına kavuştu. Bu vesile ile her sene adaylar artarak bu sınava rağbet göstermeye devam ediyorlar. MSÜ sorularının TYT sorularına kısmen benzerliği YKS öncesi moral ve motivasyon açısından da önemli oluyor.

Sınav Sorularına ÖSYM sitesinden ulaşabilirsiniz. 

https://www.osym.gov.tr/ 

23/02/2025 Pazar tarihinde Milli Savunma Üniversitesi Askeri Öğrenci Aday Belirleme Sınavı ÖSYM tarafından gerçekleştirildi ve akabinde sınav sorularının %10 luk kısmı basın yoluyla herkesin erişimine açıldı. Açıklanan matematik sorularının çözümleri aşağıda verilmiştir. Sınavın herkes için hayırlı olmasını temenni ediyorum.

Türev ve Değişim Hızı

Türevde değişim oranı, bir fonksiyonun belirli bir noktadaki eğimini ifade eder. Matematikte türev, bir fonksiyonun herhangi bir noktadaki anlık değişim hızını hesaplamak için kullanılır. Değişim oranı fonksiyonun ne kadar hızlı değiştiğini gösterir ve genellikle bu değişim hızı, birim zamandaki değişimin büyüklüğü olarak ifade edilir. Türevde değişim oranı, bir fonksiyonun eğiminin o noktada ne kadar keskin olduğunu belirlememizi sağlar ve bu sayede optimize etme, modelleme ve analitik hesaplamalar gibi birçok alanda kullanılır.

Bir fonksiyonun bir aralıktaki değişim oranı, o aralıktaki fonksiyon değerlerinin farkının, o aralıktaki bağımsız değişkenin değerlerinin farkına bölünmesi ile hesaplanır.

Matematiksel olarak değişim hızı, (f(b) - f(a)) / (b - a) formülü ile ifade edilir, burada f(b) ve f(a) sırasıyla aralığın sağ ve sol uçlarındaki fonksiyon değerlerini, a ve b ise aralığın sağ ve sol uçlarındaki bağımsız değişken değerlerini temsil eder.

Bir fonksiyonun değişim oranı, o fonksiyonun belirli bir aralıktaki eğimi ya da artış hızını temsil eder. Bu değişim oranı genellikle iki nokta arasındaki eğimi ölçmek için kullanılır. Eğer bu oran (eğim) pozitif ise fonksiyon artıyor, (eğim) negatif ise fonksiyon azalıyor demektir. Değişim oranı, bir fonksiyonun davranışını anlamak ve analiz etmek için önemli bir kavramdır ve matematiksel modellemede ve çeşitli alanlarda sıkça kullanılır. Bağımsız değişkenler arasındaki ilişkiyi belirlemek ve trendleri anlamak için değişim oranı oldukça faydalı bir araçtır. Aşağıda konu ile ilgili çeşitli örnek soru çözümleri verilmiştir.

Örnek: Bir eşkenar üçgenin bir kenarı 4 cm/sn hızla büyümektedir. Bir kenar uzunluğu 12 cm olduğu anda alanının büyüme hızı kaç

cm²/sn  olur?

Örnek: Küre şeklindeki bir balon üzerinde bulunan bir delikten hava kaçırmaktadır. Balonun yarıçapı 6cm olduğu anda hacminin azalma hızı 24 cm³/sn olduğuna göre yarıçapının azalma hızı kaç cm/sn olur?

Örnek: Kare dik prizma şeklindeki cam su deposunun altında yer alan bir musluktan saniyede 3 m³ su boşalmaktadır. Buna göre depo içindeki suyun yüksekliğinin azalma hızı kaç m/sn olur?

Örnek: Başlangıçtaki yarıçapı 5 cm olan küre şeklindeki bir balon t = 0 anından itibaren geçen sürede t saniye sonra r=(80-t)/16 cm olacak şekilde içinden sürekli hava sızdırmaktadır. Buna göre, t= 40 iken içerdeki hava kaç cm³/sn hızla dışarı sızar?

Örnek: İçi tamamen su dolu olan taban yarıçapı 9cm ve yüksekliği 18 cm olan koni şeklindeki bir cisim tepe noktasındaki A noktasından delinip ters çevrildikten sonra içindeki su akmaya başlamıştır. Su yüksekliği 6 cm olduğu anda, kaptaki suyun yüksekliğine bağlı değişim oranı kaç cm³ olur?

Örnek: Bir pistte yer alan roket dik doğrusal hareket etmektedir. Başlangıçta zemine dik bir şekilde sabit bir noktada olan roketin, aynı zeminde bulunan bir A noktasına uzaklığı 80 m'dir. Roketin kalkış yaptıktan sonra aynı zemindeki başlangıç noktasına uzaklığı 60 m olduğu andaki değişim hızı 10 m/sn olduğuna göre roketin zeminde bulunan A noktasına olan uzaklığının değişim hızı kaç m/sn olur?

Örnek: Sokak lambasından 5 m/s hızla yürüyerek uzaklaşan ve boyu 2 metre olan bir kişinin lambadan uzaklığı 10 m olduğu anda bu kişinin gölgesinin ucu da 6 m/s hızla kendisinden uzaklaşarak hareket ediyorsa sokak lambasının boyu kaç m'dir?

Örnek: Dik üçgen biçimindeki oda yeniden düzenlenirken zemine dik olacak sekilde bir kontrplak zemine yerleştiriliyor. Yerleştiriken kontrplak duvara doğru ok yönünde saniyede 28 cm hızla hareket ettirildiğinde x uzunluğunun artma hızı kaç cm/sn olur?

Örnek: Boyu 5 metre olan dikdörtgen biçimli bir kutu duvara dayalı halde dururken kutunun alt kısmından çekildiğinde kutunun üst ucu duvardan ayrılmadan aşağıya doğru kaymaktadır. Kutunun alt ucu saniyede 8 cm hızla 3 metre kaydığında üst ucun kayma hızı kaç metre/sn olur?

Kadane Algoritması

Kadane Algoritması, belirli bir sayı dizisi içindeki maksimum alt dizi toplamını bulmak için kullanılan dinamik bir programlama tekniğidir. Dinamik Programlama, karmaşık bir problemi daha basit alt problemlerden oluşan bir koleksiyona bölerek, bu alt problemlerin her birini yalnızca bir kez çözerek ve çözümlerini bellek tabanlı bir veri yapısı (dizi, harita vb.) kullanarak saklayarak çözme yöntemidir. Yani bir dahaki sefere aynı alt problem ortaya çıktığında, çözümünü yeniden hesaplamak yerine, daha önce hesaplanan çözüme bakılır ve böylece hesaplama süresinden tasarruf edilir. Adını mucidi Jay Kadane'den alan algoritma; bilgisayar bilimi ve veri analizinden finans ve görüntü işlemeye kadar çeşitli alanlarda uygulamalara sahiptir. Algoritma 1984 yılında Jay Kadane tarafından önerilmiştir ve O(n) zaman karmaşıklığına sahiptir. 

Kadane Algoritması, belirli bir dizideki maksimum alt dizi toplamını bulmak için kullanılan doğrusal bir zaman algoritmasıdır. Bir alt dizi, dizi içindeki öğelerin bitişik bir alt kümesi olarak tanımlanır. Algoritma, pozitif ve negatif sayıları çok verimli bir şekilde ele alır, bu da onu alt dizileri içeren birçok sorunu çözmek yerine daha pratik çok yönlü bir çözüm aracı haline getirir.Kadane'nin algoritmasından önce, maksimum alt dizi problemini çözmek için tüm olası alt dizileri kontrol eden kaba kuvvet yaklaşımı ve böl ve yönet algoritması gibi başka algoritmalar önerilmişti. Ancak bu algoritmalar daha yüksek zaman karmaşıklığına sahiptir ve Kadane'nin algoritmasından daha az verimlidir. Kadane'nin Algoritmasının altında yatan mekanizmaları, Java kodu uygulamalarını, adım adım süreci, Kadane'nin algoritma leetcode'unu, C, C++'yi, zaman karmaşıklığını, avantajlarını ve dezavantajlarını, pratik uygulamaları ve daha fazlasını anlamanız sizin için faydalı olacaktır.

Kadane Algoritması, dizi üzerinde yineleme yaparak ve her konumda biten alt dizinin maksimum toplamını takip ederek çalışır. Her i konumunda, iki seçeneğimiz vardır: ya i konumundaki elemanı geçerli maksimum alt diziye ekleyin ya da i konumunda yeni bir alt dizi başlatın. Bu iki seçeneğin maksimumu i konumunda biten maksimum altdizidir.

Yazılım dilinde bu algoritma şu şekilde işler: Başlangıç toplamı max_so_far ve max_ending_here değerleri 0 olarak alınıp dizi öğeleri tek tek incelenir. Sırasıyla şu ana kadar görülen maksimum toplamı ve geçerli konumda biten maksimum toplamı takip etmek için max_so_far ve max_ending_here olmak üzere iki değişkeni her dizi elemanında korunur. Algoritma, her iki değişkeni de dizinin ilk öğesinden başlayarak sırasıyla değiştirir. Daha sonra dizinin elemanlarını aldıktan sonra geçerli toplamı maksimum toplamla kıyaslayarak ikinci öğeden dizinin sonuna kadar aynı işlemler tekrarlanır. Her i konumunda, geçerli öğenin maksimumunu ve önceki maksimum alt diziye eklenen geçerli öğeyi alarak max_ending_here'i güncellenir. Daha sonra max_so_far'ı max_so_far ve max_ending_here'nin maksimumu olacak şekilde güncelleme işlemine devam edilir. Geçerli toplam maksimum toplamdan büyük ise artık yeni maksimum toplam değeri buna göre güncellenir aksi halde önceki maksimum toplam aynı kalır. Algoritma, dizideki herhangi bir alt dizinin maksimum toplamı olan max_so_far değerini sürekli olarak döndürür. Dizinin son terimine gelince işlem biter ve maksimum toplamı veren alt dizi elde edilir.

Kadane Algoritmasını şöyle bir sayı dizisi örneğiyle gösterelim:

Giriş Dizisi: [-2, 1, 6, -3, 4, -1, -7, -3, 5] Bu dizinin maksimum altdizi toplamını bulmak istiyoruz. Bu sorunu çözmek için Kadane'nin algoritmasını uygulayabiliriz.

İki değişkeni başlatarak algoritmayı başlatıyoruz:

1) max_so_far: Bu değişken şu ana kadar gördüğümüz maksimum alt dizi toplamını takip edecektir. (Geçerli Toplam)

2) max_ending_here: Bu değişken mevcut endekste biten maksimum toplamı takip edecektir. (Max Toplam)

3) İlk başlangıç toplamı max_so_far ve  max_ending_here=0 olur. Daha sonra ikinci elemandan başlayarak dizi boyunca toplamları yineliyoruz: Öğe -2 ye gidip yeni toplam -2 olur. (0+(-2)=-2) [Sub:-2]

4) Geçerli öğeyi önceki toplama ekleyerek geçerli toplamı güncelleyin: Geçerli Toplam=0+(-2)=-2 [Sub:-2]

5) Şu ana kadar görülen maksimum toplamı güncelleyin: 0+(-2)=-2 olur.(Maksimum Toplam=-2) [Sub:-2, Max:-2]

6) Dizi boyunca ilerleyerek yerel toplam (Geçerli toplam) ve maksimum toplam sonuçlarını yinelemeye başlayalım.

Dizide öğe 1 elemanına gelince: Geçerli toplam -1 olur. (-2+1=-1)  [Sub:-1]

Maksimum toplam, geçerli toplam olan -1, max toplam -2 yi geçtiği için -1 olarak güncellenir. [Sub:-1, Max:-1]

7) Öğe 6 elemanına gidelim: Yeni geçerli toplamı 5 olur. ((-1)+6=5) Maksimum toplamı ise 5 toplamı önceki maksimum toplam olan -1 sayısını geçtiği için güncellenir ve maksimum toplam 5 olur.  [Sub:5, Max:5]

8) Öğe -3'e gelince:Yeni geçerli toplamı 2 olur. (5+(-3)=2) Maksimum toplamı ise 2 toplamı önceki maksimum toplam olan 5 sayısını  sayısını geçemediği için aynı kalır. Yeni maksimum toplam halen 5'tir. [Sub:2, Max:5]

9)Öğe 4'e gelince:Yeni geçerli toplamı 6 olur. (2+4=6) Maksimum toplamı 6 ise önceki max toplam 5'i geçtiği için yeniden güncellenir ve yeni maksimum toplam 6 olur. [Sub:6, Max:6]

10)Öğe -1'e gelince:Yeni geçerli toplamı 5 olur. (6+(-1)=5) Maksimum toplamı ise 5 toplamı önceki maksimum toplam olan 6 sayısını geçemediği için halen aynı kalır ve 6 olur. [Sub:5, Max:6]

11)Öğe -7'e gelince:Yeni geçerli toplamı -6 olur. (5+(-7)=-2) Maksimum toplamı ise -2 önceki maksimum toplam olan 6 sayısını geçemediği için aynı kalır. [Sub:-2, Max:6]

12)Öğe -3'e gelince:Yeni geçerli toplamı -5 olur. ((-2)+(-3)=-5) Maksimum toplamı ise -5 önceki maksimum toplam olan 6 sayısını geçemediği için aynı kalır. [Sub:-5, Max:6]

13)Öğe 5'e gelince:Yeni geçerli toplamı 0 olur. ((-5)+5=0) Maksimum toplamı ise 0 toplamı önceki maksimum toplam olan 6 sayısını artık geçemediği için aynı kalır. [Sub:0, Max:6]

Tüm dizi için bu işleme devam edip en son öğeye gelindiği için işlem biter. Bu örnekteki maksimum alt dizi, toplamının en büyük olduğu değer 6 olduğundan buna uygun bir alt dizi [-2, 1, 6, -3, 4] olur.

Java ve C++ programlamada Kadane Algoritması şöyle çalışır:

1)İki değişkeni, max_so_far ve max_ending_here'i 0'a başlatın.

2)Diziyi soldan sağa doğru yineleyin ve her öğeyi tek tek inceleyin.

3)Her öğe için, maksimum değer ya geçerli öğe ya da geçerli öğe ile max_ending_here'in toplamı olduğundan max_ending_here'i güncelleyin.

4)Max_so_far'ı mevcut max_so_far veya max_ending_here'in maksimumu kadar güncelleyin.

5)Dizideki tüm öğeler için 3. ve 4. adımları tekrarlayın.

6)Yinelemenin sonundaki max_so_far değeri maksimum altdizi toplamı olacaktır.

#include <iostream>

using namespace std;

int maxSubarraySum(int arr[], int size) {

  int maxEndingHere = arr[0];

  int maxSoFar = arr[0];

  for (int i = 1; i < size; i++) {

      maxEndingHere = max(arr[i], maxEndingHere + arr[i]);

      maxSoFar = max(maxSoFar, maxEndingHere);

  }

  return maxSoFar;

}

int main() {

  int nums[] = {-2, -1, -3, 4, -1, 2, 1, -5, 4};

  int size = sizeof(nums) / sizeof(nums[0]);

  int maxSum = maxSubarraySum(nums, size);

  cout << "Maximum subarray sum: " << maxSum << endl;

  return 0;

}

Kaynakça:

https://www.tpointtech.com/kadanes-algorithm

https://www.simplilearn.com/kadanes-algorithm-article

https://www.interviewbit.com/blog/maximum-subarray-sum/

https://www.guru99.com/tr/largest-sum-contiguous-subarray.html

https://www.codecademy.com/resources/docs/general/algorithm/kadanes-algorithm

 

Kadane Çarpım Algoritması Konu Anlatım Özetini indirmek için tıklayınız. (PDF)