SonsuzUs

Rekabetçi Programcı Çizgenin Temelleri

Çoğu kodlama sorusu bir çizge problemi olarak modellenip uygun bir çizge algoritmasıyla çözülebilir. Tipik bir örnek, bir ülkedeki yolları ve şehirleri temsil eden ağdır. Bazen çizge sorunun içinde gizli olduğundan fark edilmesi güçleşir. Bu bölümde çizgelerle ilgili temel kavramları ele alıp algoritmalarda çizgeleri göstermenin farklı yollarını inceleyeceğiz.

11.1 Çizge Terminolojisi

Bir çizge (graph), düğümlerden (nodes) ve kenarlardan (edges) oluşur. Bu yazıda $n$ çizgedeki toplam düğüm sayısını, $m$ ise toplam kenar sayısını belirtecektir. Düğümler $1, 2, \ldots, n$ tamsayılarıyla numaralandırılır.

Yol ve Döngü

Yol (path), $a$ düğümünden $b$ düğümüne kenarlar kullanılarak ulaşılmasını sağlar. Yolun uzunluğu, yolda geçilen kenar sayısına eşittir. Örneğin $1 \to 3 \to 4 \to 5$ yolu, 1. düğümden 5. düğüme 3 uzunluğunda bir yoldur.

Başlangıç ve son düğümün aynı olduğu yola döngü (cycle) denir. Bir yolda her düğüm en fazla bir kez geçiyorsa bu yol basittir (simple).

Bağlılık

Her iki düğümü arasında bir yol bulunan çizge bağlıdır (connected). Bir çizgenin bağlı alt gruplarına parça (component) denir. Örneğin ${1,2,3}$, ${4,5,6,7}$ ve ${8}$ olmak üzere üç parçalı bir çizge bağlı değildir.

Bir çizge bağlıysa ve $n$ düğüm ile $n-1$ kenardan oluşuyorsa bu çizge bir ağaçtır (tree). Ağaçta her iki düğüm arasında tam olarak bir yol vardır.

Kenar Yönleri

Kenarların tek yönlü olduğu çizge yönlüdür (directed). Yönlü bir çizgede $3 \to 1 \to 2 \to 5$ yolu olabilirken $5$’ten $3$’e giden herhangi bir yol olmayabilir.

Kenar Ağırlıkları

Ağırlıklı (weighted) bir çizgede her kenarın bir ağırlığı vardır; bu ağırlık genellikle uzunluk olarak yorumlanır. Ağırlıklı bir çizgedeki yolun uzunluğu, yoldaki kenarların ağırlıklarının toplamıdır. Örneğin $1 \to 2 \to 5$ yolunun uzunluğu 12, $1 \to 3 \to 4 \to 5$ yolunun uzunluğu 11 olabilir; burada ikinci yol daha kısadır.

Komşular ve Dereceler

İki düğüm arasında kenar varsa bunlar komşu (neighbor) düğümlerdir. Bir düğümün derecesi (degree), komşu sayısına eşittir.

$m$ kenarlı bir çizgenin toplam derece sayısı her zaman $2m$’dir; çünkü her kenar iki düğümün derecesini birer artırır. Bu nedenle derece toplamı daima çifttir.

Yönlü çizgelerde bir düğümün iç derecesi (indegree) o düğüme gelen kenar sayısını, dış derecesi (outdegree) ise o düğümden çıkan kenar sayısını verir.

Her düğümün derecesi $d$ ise çizge sıradan (regular), her düğüm birbirine bağlıysa (derece $n-1$) çizge tam (complete) olarak adlandırılır.

Boyamalar

Çizgeyi boyarken komşu düğümlerin farklı renk almasına dikkat edilir. Yalnızca iki renkle boyanabilen çizge iki parçalıdır (bipartite). Bir çizgenin iki parçalı olabilmesi için tek sayıda kenarlı herhangi bir döngü içermemesi gerekir.

Örneğin altı düğümlü bir çizge iki parçalıysa düğümler iki gruba ayrılıp her kenar gruplar arasında geçer; iki renkle boyanabilir. Ama tek sayıda kenarlı bir döngü içeriyorsa boyama mümkün olmaz.

Genel durumda bir çizgenin $k$ renkle boyanıp boyanamayacağını bulmak zordur. $k = 3$ için dahi bilinen verimli bir algoritma yoktur — bu problem NP-hard‘dır.

Basitlik

Aynı düğümde başlayıp biten kenar (öz-döngü) veya iki düğüm arasında birden fazla kenar içeren çizge basit değildir (not simple). Genellikle çizgelerin basit olduğu kabul edilir.

11.2 Çizge Gösterimi

Algoritmalarda çizgeleri göstermenin birkaç yaygın yolu vardır. Veri yapısının seçimi çizgenin büyüklüğüne ve algoritmanın çizgeyi işleme biçimine göre değişir.

Komşuluk Listesi Gösterimi

Komşuluk listesi (adjacency list) gösteriminde her $x$ düğümüne bir liste atanır; bu liste $x$’ten çıkan kenarların ulaştığı düğümleri içerir. Komşuluk listeleri çizgeleri göstermenin en popüler yoludur ve çoğu algoritma bu yöntemle verimli biçimde kodlanabilir.

Komşuluk listesini oluşturmanın pratik yolu vektörlerden oluşan bir dizi kullanmaktır:

Rekabetçi Programcı Bit Manipülasyonu

Bilgisayar programlarındaki tüm veriler bit olarak yani 0 ve 1 sayıları biçiminde tutulur. Bu bölüm tam sayıların bit gösterimlerini açıklayıp bit operasyonlarının kullanıldığı örneklere değinecektir. Algoritma programlamasında bit manipülasyonunu kullanmanın pek çok farklı yolu vardır.

10.1 Bit Gösterimi

Programlamada bir $n$ bitlik tamsayı, $n$ bitten oluşan bir binary sayısı olarak tutulur. Örneğin C++’da int 32-bit olup her int sayısı 32 bitten oluşur.

int 43 sayısının bit gösterimi:

Rekabetçi Programcı Aralık Sorguları

Bir dizinin alt aralıklarında hızlıca sorgu yapmak rekabetçi programlamada sık karşılaşılan bir ihtiyaçtır. Bir aralık sorgusunda görev, bir dizinin belirli bir alt aralığında bir değeri hesaplamaktır. Tipik aralık sorguları şunlardır:

• sumq(a, b): $[a, b]$ aralığındaki sayıların toplamını bul
• minq(a, b): $[a, b]$ aralığındaki minimum sayıyı bul
• maxq(a, b): $[a, b]$ aralığındaki maksimum sayıyı bul

Örneğin [1, 3, 8, 4, 6, 1, 3, 4] dizisinde $[3,6]$ aralığı için sumq(3,6) = 14, minq(3,6) = 1, maxq(3,6) = 6 olur.

En basit yaklaşım aralık içindeki tüm elemanlara tek tek bakmaktır; bu $O(n)$ sürer. $q$ sorgu için toplam $O(nq)$ zaman gerekir. Hem $n$ hem de $q$ büyük olduğunda bu yavaş kalır. Neyse ki aralık sorgularını çok daha verimli yapmanın yolları vardır.

9.1 Statik Dizi Sorguları

Dizinin statik olduğu (sorgular sırasında değerlerin değişmediği) duruma ilk bakacağız. Bu durumda sorguları sabit zamanda yanıtlayan bir veri yapısı oluşturmak yeterlidir.

Toplam Sorguları

Statik bir dizideki toplam sorgularını prefix toplam dizisi ile kolayca çözebiliriz. Prefix toplam dizisindeki $k$. konum, orijinal dizinin $[0, k]$ aralığının toplamına eşittir; yani sumq(0, k) değerini tutar. Bu dizi $O(n)$ zamanda oluşturulabilir.

Örneğin [1, 3, 4, 8, 6, 1, 4, 2] dizisine karşılık gelen prefix toplam dizisi:

Rekabetçi Programcı Amortize Analizi

Bir algoritmanın sadece yapısını inceleyerek (örneğin döngü sayılarına bakarak) zaman karmaşıklığını hesaplamak kolaydır. Fakat bazen bu üstünkörü analiz, algoritmanın gerçek verimliliğini doğru yansıtmaz.

Amortize Analizi, zaman karmaşıklığı farklı olan operasyonları içeren algoritmaları inceler. Buradaki fikir, tek tek operasyonların en kötü durumuna bakmak yerine, algoritmanın çalışması sürecinde bütün operasyonlar için harcanan toplam zamanı tahmin etmektir. Bazen bazı operasyonlar yavaş olsa da, toplamda bu yavaş operasyonlar sık gerçekleşmediği için ortalama performans verimli olabilir.

8.1 İki İşaretçi Methodu (Two Pointers Method)

İki işaretçi methodunda, dizinin elemanları üzerinden geçmek için iki işaretçi (pointer) kullanılır. Bu işaretçiler genellikle tek bir yöne doğru hareket ederler, bu da algoritmanın verimli çalışmasını sağlar.

Altdizi (Subarray) Toplamı

Problem: n tane pozitif sayıdan oluşan bir dizide, toplamı x olan ardışık bir altdizi bulmak.

Fikir: Altdizinin başlangıcını ve sonunu gösteren iki işaretçi (sol ve sağ) tutulur. sağ işaretçi, toplam x‘i geçmediği sürece ilerletilir. Toplam x‘i geçerse, sol işaretçi ilerletilerek altdizi küçültülür. Eğer toplam tam olarak x olursa, bir çözüm bulunmuş olur.

[1, 3, 2, 5, 1, 1, 2, 3] dizisinde toplamı 8 olan altdiziyi bulmak için iki işaretçi yönteminin adımları

Her iki işaretçi de dizi boyunca sadece ileri doğru hareket ettiği için toplamda en fazla 2n adım atarlar. Bu yüzden algoritma $O(n)$ zamanda çalışır.

2SUM Problemi

Problem: n sayıdan oluşan bir dizide, toplamı x olan iki eleman bulmak.

Fikir:

1. Diziyi artan sırada sıralayın.
2. Bir işaretçiyi (sol) dizinin başına, diğerini (sağ) dizinin sonuna yerleştirin.
3. array[sol] + array[sağ] toplamını kontrol edin:
   • Toplam x‘ten küçükse, daha büyük bir değere ihtiyacımız var demektir, bu yüzden sol işaretçisini bir sağa kaydırın.
   • Toplam x‘ten büyükse, daha küçük bir değere ihtiyacımız var demektir, bu yüzden sağ işaretçisini bir sola kaydırın.
   • Toplam x‘e eşitse, bir çözüm bulunmuştur.
4. İşaretçiler karşılaşana kadar devam edin.

Sıralama $O(n \log n)$, iki işaretçi ile arama ise $O(n)$ sürdüğü için toplam zaman karmaşıklığı $O(n \log n)$ olur. Daha zor bir problem olan 3SUM problemi (toplamı x olan üç eleman bulmak), bu fikir genişletilerek $O(n^2)$ zamanda çözülebilir¹.

8.2 En Yakın Küçük Elemanlar (Nearest Smaller Elements)

Problem: Bir dizideki her eleman için, o elemanın solunda bulunan ve kendisinden küçük olan en yakın elemanı bulmak.

Fikir: Dizinin solundan sağına doğru ilerlerken bir yığın (stack) kullanılır. Her eleman için:

1. Yığının tepesindeki eleman mevcut elemandan küçük olana kadar veya yığın boşalana kadar yığından eleman çıkarılır.
2. Eğer yığın boş değilse, tepedeki eleman aranan en yakın küçük elemandır.
3. Mevcut eleman yığına eklenir.

[1, 3, 4, 2, 5, 3, 4, 2] dizisi için yığının adım adım değişimi

Bir eleman yığına en fazla bir kez eklenip bir kez çıkarıldığı için, her eleman amortize olarak $O(1)$ yığın operasyonu gerektirir. Bu yüzden algoritmanın toplam zaman karmaşıklığı $O(n)$’dir.

8.3 Sürgülü Pencere Minimumu (Sliding Window Minimum)

Problem: Sabit k boyutundaki bir altdizinin (sürgülü pencere), dizi boyunca soldan sağa hareket ederken her pozisyondaki minimum elemanı bulmak.

Fikir: Bir deque (çift yönlü kuyruk) veri yapısı kullanılır. Bu deque her zaman pencere içindeki elemanların indislerini artan değer sırasında tutar. deque‘in başındaki eleman her zaman o anki pencerenin minimumudur. Her adımda pencere bir sağa kaydığında:

1. deque‘in sonundan, yeni eklenecek elemandan daha büyük olan elemanlar çıkarılır.
2. Yeni elemanın indisi deque‘in sonuna eklenir.
3. deque‘in başındaki elemanın indisi pencerenin dışına çıkmışsa, baştan çıkarılır.

Her eleman deque‘e en fazla bir kez eklenip bir kez çıkarıldığı için, bu algoritma da amortize olarak $O(n)$ zamanda çalışır.

Rekabetçi Programcı Dinamik Programlama (Dynamic Programming)

Dinamik programlama, tam bir aramanın doğruluğu ile açgözlü algoritmaların verimliliğini birleştiren bir tekniktir. Eğer bir problemde aynı alt problemler birkaç defa çözülüyorsa ve bu alt problemler bağımsız bir şekilde çözülebiliyorsa dinamik programlama kullanabiliriz.

Dinamik programlamanın iki temel kullanımı vardır:

• Optimal bir çözüm bulmak: Olabildiğince büyük veya küçük bir sonuç aradığımız durumlar.
• Olası çözüm sayısını hesaplamak: Toplam olası çözüm sayısını bulmak.

Bu bölüm, dinamik programlamanın temellerini ve klasik problemler üzerindeki uygulamalarını gösterecektir.

7.1 Para Problemi

Bölüm 6’da gördüğümüz para problemini tekrar ele alalım: coins = {c_1, c_2, ..., c_k} değerlerinden oluşan bir para kümesiyle, n toplamını oluşturan en az sayıda parayı bulmak. Açgözlü yaklaşımın her zaman çalışmadığını görmüştük. Şimdi bu problemi her para kümesi için çalışan dinamik programlama ile çözeceğiz.

Özyinelemeli Formülleştirme

Problemin çözümünü daha küçük alt problemlerin çözümlerinden bulabiliriz. solve(x), x toplamı için gereken minimum para sayısını ifade etsin.

Eğer coins = {1, 3, 4} ise, x toplamına ulaşmak için ilk seçtiğimiz para ya 1, ya 3, ya da 4 olabilir.

• Eğer 1 seçersek, geri kalan x-1 toplamı için solve(x-1) kadar paraya ihtiyacımız olur.
• Eğer 3 seçersek, geri kalan x-3 toplamı için solve(x-3) kadar paraya ihtiyacımız olur.
• Eğer 4 seçersek, geri kalan x-4 toplamı için solve(x-4) kadar paraya ihtiyacımız olur.

Bu durumda özyineleme formülü şu şekilde olur: solve(x) = min(solve(x-1)+1, solve(x-3)+1, solve(x-4)+1) Temel durum solve(0) = 0‘dır.

Memoization

Yukarıdaki özyinelemeli fonksiyon, aynı solve(x) değerini tekrar tekrar hesapladığı için verimsizdir. Memoization tekniği ile, hesaplanan her solve(x) değerini bir dizide saklarız. Fonksiyon tekrar aynı x değeri için çağrıldığında, sonucu yeniden hesaplamak yerine doğrudan diziden alırız.

Rekabetçi Programcı Açgözlü Algoritmalar (Greedy Algorithms)

Açgözlü algoritma, her zaman o anki en iyi gözüken kararı vererek çözüme ulaşan bir yaklaşımdır. Açgözlü bir algoritma asla daha önce verdiği kararları geri almaz ve doğrudan son sonucu oluşturur. Bu yüzden açgözlü algoritmalar genellikle verimlidir. Açgözlü bir algoritma oluşturmanın zorluğu, her zaman en iyi (optimal) cevabı verecek bir açgözlü strateji bulmaktır. Yapılan küçük optimal kararların, genel olarak da optimal olması gerekir. Genellikle bir açgözlü algoritmanın doğru çalıştığını kanıtlamak zordur.

6.1 Para Problemi (Coin problem)

Elimizdeki madeni paraları kullanarak n miktarında bir para üstü vermemiz isteniyor. Elimizdeki paraların değerleri coins = {c_1, c_2, ..., c_k}‘dir ve her parayı istediğimiz kadar kullanabiliriz. Amaç, toplam için gereken minimum sayıda madeni para kullanmaktır.

Örneğin, {1, 2, 5, 10, 20, 50, 100, 200} paralarıyla n = 520 oluşturmak için en az 4 para gerekir: 200 + 200 + 100 + 20.

Açgözlü Algoritma

Basit bir açgözlü algoritma, gereken miktar toplanana kadar her zaman seçilebilecek en büyük değerli parayı seçmektir. Bu strateji, standart Euro madeni paraları gibi sistemlerde işe yarar.

Genel Durum

Ancak genel durumda, sahip olduğumuz paralar rastgele değerlerde olabilir ve bu açgözlü algoritma her zaman optimal çözümü vermeyebilir. Örneğin, elimizdeki paralar {1, 3, 4} ise ve istenen toplam 6 ise, açgözlü algoritma 4 + 1 + 1 (3 adet para) çözümünü verirken, en iyi çözüm 3 + 3‘tür (2 adet para).

Para problemi için her zaman çalışan genel bir açgözlü algoritma bilinmemektedir¹.

6.2 Zaman Planlaması (Scheduling)

Çoğu zaman planlama sorusu açgözlü algoritmalar ile çözülebilir. Klasik bir problem, başlangıç ve bitiş zamanları bilinen n tane etkinlikten, birbiriyle çakışmayacak şekilde en fazla sayıda etkinliği seçmektir.

Bu durumda en fazla iki etkinlik seçilebilir, örneğin B ve D.

Farklı açgözlü stratejiler denenebilir:

1. En kısa etkinliği seç: Bu strateji her zaman çalışmaz. Kısa bir etkinlik, daha uzun süren iki etkinliğin seçilmesini engelleyebilir.
2. En erken başlayan etkinliği seç: Bu da her zaman çalışmaz. Erken başlayan uzun bir etkinlik, daha sonraki birçok etkinliği engelleyebilir.
3. En erken biten etkinliği seç: Bu strateji her zaman doğru çalışır. Her adımda, mevcut etkinliklerle çakışmayan ve bitiş zamanı en erken olan etkinliği seçmek, kalan zamanı maksimize ettiği için optimal bir çözüm üretir.

6.3 Görevler ve Son Teslimler (Tasks and Deadlines)

Süresi ve son teslim tarihi bilinen n tane görevimiz olduğunu düşünelim. Amacımız görevleri yapmak için bir sıra oluşturmak. Her görev için $d - x$ puan kazanıyoruz, burada d görevin son teslim tarihi ve x görevi bitirdiğimiz zamandır. En fazla alabileceğimiz toplam puan kaçtır?

İlginç bir şekilde, bu sorunun optimal çözümü son teslim tarihlerine bağlı değildir. Doğru açgözlü strateji, görevleri sürelerine göre artan bir şekilde sıralamaktır. Bunun nedeni, eğer daha uzun süren bir görevi daha kısa süren bir görevden önce yaparsak, bu iki görevin yerini değiştirdiğimizde toplam puanın her zaman artması veya aynı kalmasıdır. Daha kısa görevleri önce bitirmek, sonraki tüm görevlerin bitiş zamanını öne çeker ve toplam puanı iyileştirir.

6.4 Toplamları Küçültmek (Minimizing Sums)

Bize n tane $a_1, a_2, …, a_n$ sayısı verildiğinde, $\sum_{i=1}^{n} \lvert a_i - x\rvert ^c$ toplamını en küçük yapacak x değerini bulma problemi.

c = 1 Durumu

$\sum \lvert a_i - x\rvert $ toplamını minimize etmek için en iyi x değeri, sayıların medyanıdır. Sayılar sıralandıktan sonra ortadaki eleman medyandır.

c = 2 Durumu

$\sum (a_i - x)^2$ toplamını minimize etmek için en iyi x değeri, sayıların aritmetik ortalamasıdır ($(\sum a_i) / n$).

6.5 Veri Sıkıştırma (Data Compression)

Bir metni sıkıştırmak için her karaktere bir bit dizisi (kod) atanabilir. Daha sık geçen karakterlere daha kısa kodlar, daha az geçenlere daha uzun kodlar atayarak metnin toplam uzunluğu azaltılabilir.

Huffman Kodlaması

Huffman Kodlaması, bir metni sıkıştırmak için en optimal kodu (prefix code) üreten bir açgözlü algoritmadır².

Algoritma, karakterlerin metindeki frekanslarına (geçme sıklıklarına) dayalı bir ikili ağaç (binary tree) oluşturur.

1. Her karakteri, frekansı kadar ağırlığa sahip bir düğüm olarak başlat.
2. Her adımda, en düşük ağırlığa sahip iki düğümü seç ve bunları yeni bir ebeveyn düğüm altında birleştir. Yeni düğümün ağırlığı, birleştirilen iki düğümün ağırlıkları toplamıdır.
3. Tek bir kök düğüm kalana kadar bu işleme devam et.

Oluşturulan ağaçta, kökten bir karakterin yaprağına giden yol o karakterin kodunu verir (sola gitmek ‘0’, sağa gitmek ‘1’).

Bu yöntemle, sık geçen ‘A’ karakteri gibi karakterler kısa kodlar alırken, az geçen ‘B’ ve ‘D’ gibi karakterler daha uzun kodlar alır, bu da optimal sıkıştırmayı sağlar.

Rekabetçi Programcı Tam Arama (Complete Search)

Tam arama, neredeyse her algoritma probleminde kullanılan bir metottur. Buradaki fikir, kaba kuvvet (brute force) kullanarak bütün olası çözümleri oluşturup sonrasında probleme göre aralarından en iyi çözümü bulmak veya bütün çözümleri saymaktır. Tam arama, bütün çözümler denenebiliyorsa işe yarar bir tekniktir çünkü bu aramayı koda dökmek kolaydır ve aynı zamanda her zaman doğru çözümü bulur. Eğer tam arama soru için çok yavaş kalıyorsa, açgözlü (greedy) algoritmalar veya dinamik programlama gibi başka yöntemler gerekebilir.

5.1 Alt küme Oluşturmak (Generating Subsets)

n elemanlı bir kümenin bütün alt kümelerini oluşturmak için iki yaygın yöntem vardır: özyineleme (recursion) veya bit maskeleme (bitmasking).

Yöntem 1: Özyineleme (Recursion)

Bütün alt kümeleri oluşturmanın şık yollarından biri özyinelemedir. Aşağıdaki search fonksiyonu {0, 1, ..., n-1} kümesinin alt kümelerini oluşturur.

Rekabetçi Programcı Veri Yapıları

Veri yapısı, bilgisayarın hafızasında veri saklamak için bir yoldur. Ele alınan problem için uygun bir veri yapısı seçimi yapmak önemlidir çünkü her veri yapısının kendine göre avantajları ve dezavantajları bulunmaktadır. Bu noktada cevaplanması gereken ana soru, hangi işlemlerin seçtiğimiz veri yapısında verimli olacağıdır.

Bu bölümde C++ standart kütüphanesindeki en önemli veri yapıları tanıtılacaktır. Standart kütüphane zamandan tasarruf sağlayacağı için mümkün olduğunca onu kullanmaya özen gösterilmelidir.

4.1 Dinamik Diziler

Dinamik dizi, programın çalışması sırasında boyutu değiştirilebilen bir dizidir. C++’daki en popüler dinamik dizi vector yapısıdır.

Aşağıdaki kod, boş bir vektör oluşturur ve bu vektöre üç eleman ekler:

Rekabetçi Programcı Sıralama

Sıralama, temel algoritma sorularından biridir. Çoğu algoritmanın içeriğinde, veriyi sıralı halde işlemek daha kolay olduğu için sıralama bulunur. Örneğin “Bu dizide birbiriyle aynı iki eleman var mı?” sorusu sıralamayla çok kolay bir şekilde çözülebilir. Eğer dizi birbiriyle aynı iki eleman içeriyorsa, dizi sıralandıktan sonra bu elemanlar ardışık olacaktır.

Verimli çalışan sıralama algoritmaları $O(n \log n)$ zamanda çalışır ve genelde içeriğinde sıralama bulunan algoritmalar da bu zaman karmaşıklığına sahiptir.

3.1 Sıralama Teorisi

Temel sıralama problemi şöyledir: n elemana sahip bir diziyi artan sırada sıralayın. Örneğin [1, 3, 8, 2, 9, 2, 5, 6] dizisi sıralandıktan sonra [1, 2, 2, 3, 5, 6, 8, 9] haline dönüşür.

$O(n^2)$ Algoritmalar

Basit dizi sıralama algoritmaları $O(n^2)$ zamanda çalışır. Bu algoritmalar kısa olup genelde iki for döngüsüyle çalışır. Çok bilinen $O(n^2)$ algoritmalarından biri olan kabarcık sıralaması (bubble sort), dizideki elemanların değerlerine göre “kabarcık” gibi yer değiştirmesiyle çalışır.

Kabarcık sıralaması n defa tur atar. Her turda, algoritma sıraya uymayan iki ardışık eleman bulduğunda yerlerini değiştirir.

Rekabetçi Programcı Zaman Karmaşıklığı

Rekabetçi programlamada algoritmaların verimliliği önemlidir. Genelde soruyu çözen yavaş bir algoritma oluşturmak kolaydır ama asıl zorluk hızlı bir algoritma oluşturmaktır. Eğer algoritma çok yavaşsa ya sorudan kısmi puan alacaktır ya da hiç almayacaktır.

Zaman karmaşıklığı, bir algoritmanın bir girdi için tahmini olarak ne kadar süre gerektireceğini belirtir. Bunun amacı, girdinin boyutuna göre değişen ve algoritmanın verimliliğini gösteren bir fonksiyon oluşturmaktır. Zaman karmaşıklığını hesaplayarak, algoritmayı koda dökmeden önce yeterince hızlı olup olmadığını anlayabiliriz.

2.1 Hesaplama Kuralları

Bir algoritmanın zaman karmaşıklığı O(...) ile gösterilir. Genelde, girdi büyüklüğü olarak n değişkeni kullanılır. Örneğin sayılardan oluşan bir dizide n dizinin büyüklüğünü, eğer girdi bir yazı ise n yazının uzunluğunu verir.

Döngüler

Algoritmanın yavaşlamasına neden olan genel sebeplerden biri, girdi üzerinde çalışan çok fazla döngü bulundurmasıdır. Bir algoritma ne kadar çok iç içe geçmiş döngü içerirse o kadar yavaşlar. Eğer k tane iç içe geçmiş döngü varsa zaman karmaşıklığı O(n^k) olur.

Örneğin aşağıdaki kodun zaman karmaşıklığı O(n)‘dir:

Rekabetçi Programcı Giriş

Rekabetçi programlama iki konudan oluşur: uygun algoritmayı bulmak (algoritmanın dizaynı) ve uygun algoritmanın koda geçirilmesi (implementasyonu). Uygun algoritmayı bulmak (dizayn) için soru çözmek ve matematiksel düşünme gerekir. Soruların analiz edilip yaratıcı bir şekilde çözülmesi önemlidir. Soruyu çözen algoritmanın hem doğru hem de verimli olması gerekir. Zaten genel olarak soruların temelinde verimli algoritmayı bulmak vardır. Rekabetçi programcıların algoritmalar hakkında teorik bilgiye sahip olması gerekir. Tipik bir soru çözümü genelde bilinen tekniklerle yeni gözlemlerin birleşimidir. Rekabetçi programlamada çıkan teknikler aynı zamanda algoritmaların araştırma bazlı kısmının da temelini oluşturur.

Algoritmaların koda geçirilmesi (implementasyon) içinse iyi kodlama bilgisi gerekir. Rekabetçi programlamada çözümler belirli test caseler kullanılarak puanlanır. Bu yüzden sadece algoritmayı düşünerek bulmak yetmez, aynı zamanda bunun koda doğru bir şekilde geçirilmesi önemlidir.

Yarışmalarda yazılan kodların kısa ama aynı zamanda anlaşılabilir olması gerekir. Yarışmalarda verilen zamanın kısıtlı olması nedeniyle çözümlerin hızlı yazılması gerekir. Klasik yazılım mühendisliğinin aksine, çözümler kısa olup (çoğunlukla en fazla birkaç yüz satır kod) yarışma sonrası geliştirilmesi gerekmemektedir.

1.1 Kodlama Dilleri

Şu anda rekabetçi programlamada en çok kullanılan kodlama dilleri C++, Python ve Java’dır. Örneğin Google Code Jam 2017’de yarışmacıların ilk 3000’ünün 79%’u C++, 16%’sı Python ve 8%’i Java kullanmıştır. Bazı yarışmacılar birden çok kodlama dilini kullandılar.

Çoğu yarışmacı C++ dilini rekabetçi programlama için en iyi dil olarak görüyor ve C++ neredeyse her yarışma sisteminde bulunmaktadır¹. C++11’in yararları arasında çok hızlı ve verimli bir dil olmasıyla beraber çeşitli veri yapıları ile algoritmaları kapsayan bir kütüphaneye sahip olması yer alır.

Yine de birkaç dilde uzmanlaşıp onların yararlarını bilmekte fayda var. Örneğin soruda çok büyük sayılar gerekiyorsa Python, büyük sayılar için işlemleri halihazırda built-in bulundurmasından dolayı uygun bir seçenek olabilir. Neyse ki yarışmalardaki çoğu soru, herhangi bir kodlama dilinin avantajı olmayacak şekilde hazırlanmaktadır.

Bu kitaptaki örnek çözümler C++ ile yazılmış olup standart kütüphanedeki algoritma ve veri yapıları sıklıkla kullanılmıştır. Çözümler C++11 formatında yazılmıştır ki bu format şu anki çoğu yarışmada kullanılabilmektedir.

C++ Kod Örneği

Klasik bir C++ kodu aşağıdaki gibi görünür.

Rekabetçi Programcı Başlangıç

Rekabetçi programlama iki temel konudan oluşur: uygun algoritmayı bulmak (algoritmanın tasarımı) ve bu algoritmayı doğru biçimde koda geçirmek (implementasyonu).

Algoritma tasarımı için soru çözmek ve matematiksel düşünme gerekir. Soruların analiz edilip yaratıcı bir şekilde çözülmesi önemlidir; algoritmanın hem doğru hem de verimli olması beklenir. Rekabetçi programcıların algoritmalar hakkında teorik bilgiye sahip olması gerekir. Tipik bir soru çözümü genelde bilinen tekniklerle yeni gözlemlerin birleşimidir.

İmplementasyon içinse iyi kodlama bilgisi şarttır. Çözümler belirli test durumlarıyla puanlandığından algoritmayı doğru biçimde koda geçirmek kritik önem taşır. Yarışmalarda kodların kısa ama anlaşılabilir olması, aynı zamanda hızlı yazılması gerekir. Klasik yazılım mühendisliğinin aksine, çözümler genellikle birkaç yüz satırı geçmez ve yarışma sonrası geliştirilmesi gerekmez.

1.1 Kodlama Dilleri

Rekabetçi programlamada en çok kullanılan diller C++, Python ve Java‘dır. Google Code Jam 2017’de ilk 3000 yarışmacının %79’u C++, %16’sı Python, %8’i Java kullanmıştır.

Çoğu yarışmacı C++’ı en iyi seçenek olarak görür; neredeyse her yarışma sisteminde bulunur, çok hızlı ve verimlidir, kapsamlı bir standart kütüphanesi vardır. Yine de birkaç dilde uzmanlaşmakta fayda var. Örneğin çok büyük sayılar gerektiren problemlerde Python’ın yerleşik büyük sayı desteği işe yarayabilir.

Not: TÜBİTAK Bilim Olimpiyatları’nda yalnızca C/C++ kullanılabilmektedir.

Bu kitaptaki örnek çözümler C++11 standardıyla yazılmıştır.

C++ Kod Şablonu

Türkçe Sator Kareleri

Sator kareleri meşhur bir kelime dizilimi programıdır. Örneği şu şekildedir.

Kurallardan anlaşılacağa üzere her satır ve sütunda anlamlı kelimeler bulunuyor ve bunlar bazen birbirinin tersi olabiliyor. Anlamlı sator karelerini bulabilmek için öncelikle elimizde bir kelime veri tabanı olması gerekiyor. 60bin anlamlı kelimelerden oluşan veri tabanını indirmek için: Türkçe Sözcük veritabanı na tıklayabilirsiniz. Ben doğrudan import ettiğim için .py dosyası haline getirdim, siz elinizdeki başka veritabanlarını da kullanabilirsiniz.

Bundan sonra kodumuz bir kaç aşamadan geçiyor. Aşağıda kodlarla sator karelerini bulma girişimlerimiz olmuştur.

Pythonda Karmaşık ve İç İçe Listeleri Düzleştirmek (Flatten)

Python’da programlama yaparken, bazen karşımıza iç içe geçmiş listeler, demetler (tuple), kümeler (set) ve hatta sözlükler (dictionary) gibi farklı veri tiplerini bir arada barındıran karmaşık veri yapıları çıkabilir. Bu tür bir yapıyı analiz etmek veya üzerinde işlem yapmak için genellikle onu “düzleştirmek”, yani tek bir liste haline getirmek isteriz.

Bu yazıda, karmaşık bir listedeki tüm sayısal değerleri ayıklayıp tek ve düz bir liste oluşturmanın farklı yollarını inceleyeceğiz.

Zorlu Bir Örnek: Karışık Veri Yapısı

İşe, üzerinde çalışacağımız karmaşık listeyi tanımlayarak başlayalım. Bu liste, içinde tam sayılar, listeler, demetler, kümeler ve sözlükler barındırıyor.

Karıncaların yön bulma yeteneklerini inceleyen program

C# programlama dili ve Unity oyun motoru kullanılarak hazırlanan simülasyon aracılığıyla karıncaların koloni ve besin kaynağı arasında feromon izlerini takip etmesi incelenmiştir.

Giriş

Karıncalar, tek başlarına hayatta kalamayan, basit görevleri üstlenen canlılardır. Ancak pek çok adedi bir araya geldiğinde bir bütün olarak organizma gibi davranırlar. Karıncalar, feromon adı verilen kimyasallar aracılığıyla yönlerini bulurlar. Hem feromon salgılarlar, hem de feromona duyarlı canlılardır.

Karıncalar her an az miktarda feromon salgılarlar ve etrafta rastgele hareket ederek yiyecek ararlar. Karıncalar feromon algılamaları halinde, feromonun yoğunluğuna bağlı olarak feromona yönelebilir veya rastgele gezmeye devam edebilir. Yiyecek bulan bir karıncanın feromon salgılaması artar. Bu durum yiyeceğe ulaşmış karıncaların dönüş yolundayken feromon izini güçlendirmesine ve daha çok karıncanın izi takip ederek yiyeceğe ulaşmasına sebep olur.

Bir iz, en çok karıncanın en kısa sürede geçişiyle en verimli haline ulaşır. Dolayısıyla zaman içerisinde besin kaynağı ve koloni arasındaki yol, iki nokta arasındaki en kısa yol haline gelecektir.

Amaç

Projenin amacı, karıncaların yol bulma yeteneklerini simüle etmek, bu simülasyona bağlı olarak bireylerin, ilaçlama şirketlerinin karınca istilasına karşı uygulayabilecekleri çözümler üzerine kolaylaştırmalar sağlamaktır.

Yöntem

Simülasyon, Unity oyun motoru ve C# dili kullanılarak hazırlanmıştır.

Simülasyon; karınca, besin, feromon objelerinin prefabrikleri ve karınca oluşma noktası, besin oluşma noktası, engel çerçevesinde çalışmaktadır. Feromonun kaybolma süresi simülasyonu kullanan kişi tarafından değiştirilebilmektedir.

Karınca, sonlu durum makinesi (finite-state machine) modeline göre hazırlanmıştır.

Mavi yarıçap : içerisindeki feromonlar karınca tarafından algılanamaz. Kırmızı yarıçap : mesafesindeki feromonlar karınca tarafından algılanabilir. Sarı doğru parçaları arasında kalan açı (yeşil yay) : karıncanın feromon ve besin algılayabileceği açıklığı gösterir. Bu üç parametre de simülasyonu kullanan kişi tarafından değiştirilebilmektedir.

Simülasyon içerisindeki maksimum feromon sayısı, besin sayısı, karınca sayısı belirlenir. Karıncalara ve feromonlara ait parametreler ayarlanır (simülasyon başlangıç halinde referans değerlere sahiptir). Simülasyon başlatılır ve sonuçlar gözlemlenir.

Gözlem ve Sonuç

Karıncalar simülasyonun başlamasıyla rastgele biçimde etrafa yayıldılar. Besine ulaşan ilk karınca koloniye dönerek besin kaynağı-koloni arasındaki feromon izini oluşturdu. Onu takip eden diğer karıncalar izin güçlenmesini sağladı.

Zaman içerisinde, izden saparak besine daha kısa yoldan ulaşan karıncalar oldu. Başka karıncaların da eşlik etmesiyle birlikte kısa olan feromon izi daha da güçlendi. İlk ve uzun olan iz kayboldu.

Farklı bir engel eklenerek oluşturulan başka bir simülasyonda karşılaşılan sonuç

Öneriler

• Karınca kolonisini oluşturan kraliçenin ve erkek karıncanın genetik faktörü eklenebilir.
• Evlerin detaylı modellenebilmesi için tırmanılabilir, altından geçilebilir, geçilemez olacak şekilde mobilya-eşya eklemeleri yapılabilir.
• Simülasyon 3 boyutlu hazırlanabilir.
• Karıncaların karakteristikleri yaşlanmayla beraber değişim göstermektedir. Karıncalar için yaşam döngüsü eklenebilir.
• Karıncalar için tehditler eklenebilir (başka koloniler, zehir madde…)

Kurbağanın Talihsiz Zıplamaları Kırık Basamak ve Olasılıkların Dansı

Bir kurbağa düşünelim: her sıçrayışında ya bir ya da iki basamak yukarı çıkıyor. Amacı 75. basamağa ulaşmak. Ancak ortada bir tehlike var: 38. basamak kırık ve kurbağa o basamağa basarsa düşüyor. Bu yazıda, bu eğlenceli ama çetin problemi hem simülasyonla hem de matematiksel yöntemlerle ele alacağız.

🎯 Problemin Özeti

• Kurbağa 1. basamaktan başlıyor.
• Her adımda %50 olasılıkla 1 veya 2 basamak yukarı çıkıyor.
• Ve 38. basamak kırık: kurbağa oraya basarsa oyun biter.
• Amacı 75. basamağa ulaşmak.

Cevaplamak istediğimiz iki soru:

1. Kurbağanın 38. basamağa basma olasılığı nedir?
2. Kurbağa 38. basamağa hiç basmadan 75. basamağa basabilir mi? Olasılığı nedir?

🎲 Monte Carlo Simülasyonu ile Yaklaşım

Simülasyon yöntemiyle bu soruları yaklaşık olarak cevaplayabiliriz. Aşağıdaki Python kodu bu yaklaşımı uygular:

Kibrit Oyunu Projesi

Seçilen bir p asal sayısı ve n doğal sayısı sonrası sırayla oynanan ve 1.000.000 kibrit çöpünden en son kim yerde kalanları toplayacak şeklinde olan bir programlama oyunu. Oyunumuz bilgisayar veya cep telefonu gibi dijital bir ortamda oynanacaktır. İnsan-insan seçeneği olduğu gibi İnsan-Yapayzeka seçeneği de olacaktır. Oyunumuz sanal olarak 1 milyon kibrit çöpü ile başlayacaktır. Sırası gelen oyuncu p bir asal sayı ve n bir doğal sayı olmak üzere iki sayı girecektir (program ikisini de kontrol edecektir). Bilgisayar ortada kalan kibrit çöplerinden p^n adedini çıkaracaktır. Tam olarak yerdeki kibrit çöplerini bir asalın üssü olarak söyleyen kişi oyunu kazanacaktır. (örneğin yerde 125 kibrit çöpü kaldıysa p = 5 ve n = 3 diyen kişi oyunu kazanacaktır. veya 16 kibrit çöpü kaldıysa 2^4 diyen kişi oyunu kazanır. 4^2 diyemez çünkü 4 bir asal sayı değildir) İki insan oynarken hakemlik yapacak programımızın insana karşı yapay zeka modülü de olacaktır. Program görsel olarak windows ve linux tabanlı sistemlerde sorunsuz çalışacaktır. Python tk kütüphanesi kullanılacaktır.

Projemizin amacı, asal sayılar ve özellikleri hakkında bilgileri bir bilgisayar oyunu aracılığıyla kullanıcıya aktarmaktır. Oyun, kullanıcıların asal sayılarla ilgili işlemleri yapma, problem çözme ve birkaç hamle sonrasını düşünme becerilerini geliştirmeyi hedeflemektedir. Ayrıca, yapay zeka destekli bir modül ile insan ve yapay zeka düşünme biçimlerini karşılaştırma imkanı sunulacaktır. Bu modül, kullanıcıların stratejik düşünme becerilerini analiz ederken, yapay zekanın farklı yaklaşımlarını anlamalarına da olanak tanıyacaktır. Oyun, hem eğitici hem de eğlenceli bir platform sunarak matematiksel düşünme ve teknolojik farkındalık oluşturmayı amaçlar.

Oyunu oynayanların asal sayılar hakkında bilgi edinmesini sağlamak ve asal sayı işlemleri konusunda temel beceri kazandırmak.

Oyunu oynayan kişilerin bir kaç hamle ilerisini hesaplamasını sağlamak ve mantık , düşünme becerilerini arttırmak.

Kodlamaya veya programlamaya meraklı kişilerin “basit bir yapay zeka sistemi nasıl oluşturulur” konusunda ilgisini çekmek.

Büyük asalları bulma ve kullanma konusunda beceriler kazandırmak beklediğimiz sonuçlardandır.

Aynı zamanda oyunla matematikteki asal sayların birleştirilmesi oyunu oynayan kişiler açısından bir farkındalık yaratacağı beklenen sonuçlar arasındadır.

Projenin kodu aşağıdadır.

C++ Programlama Dilinde Vektör Kullanımı

Bu yazıda, C++ Standart Kütüphanesi’nin (STL - Standard Template Library) en güçlü ve sık kullanılan veri yapılarından biri olan vektörleri (vectors) detaylı bir şekilde inceleyeceğiz. Vektörler, C++ programcılarına dinamik boyutlu dizilerle çalışma imkanı sunarak bellek yönetimi ve veri depolama konularında büyük kolaylık sağlar. Gelin, vektörlerin ne olduğuna, nasıl kullanıldığına ve geleneksel C-stili dizilere göre avantajlarına birlikte göz atalım.

Vektör Nedir?

C++’ta std::vector, elemanları aynı türden olan ve dinamik olarak yeniden boyutlandırılabilen bir dizi konteyneridir. Geleneksel C dizilerinin aksine, bir vektörün boyutu çalışma zamanında (runtime) artırılabilir veya azaltılabilir. Bu, programın ihtiyaçlarına göre esnek bir şekilde veri saklamamıza olanak tanır. Vektörler, bellek yönetimini kendileri üstlenirler, bu da programcıyı manuel bellek ayırma ve serbest bırakma zahmetinden kurtarır.

Vektörler, vector başlık dosyası (#include <vector>) altında tanımlanmıştır ve std isim alanı (namespace) içinde bulunurlar.

Neden Vektör Kullanmalıyız?

Geleneksel C-stili dizilere kıyasla vektörlerin birçok avantajı vardır:

Dinamik Boyutlandırma: En önemli avantajıdır. Dizilerin boyutu derleme zamanında sabitken, vektörlerin boyutu çalışma zamanında değişebilir.

Otomatik Bellek Yönetimi: Vektörler, elemanlar eklendikçe veya çıkarıldıkça belleği otomatik olarak yönetir. Bu, new ve delete (veya malloc ve free) ile manuel bellek yönetimi ihtiyacını azaltır ve bellek sızıntıları (memory leaks) gibi hataların önüne geçer.

Zengin Fonksiyon Seti: Vektörler, eleman ekleme, silme, boyut sorgulama, kapasite yönetimi gibi birçok kullanışlı üye fonksiyona sahiptir.

Güvenlik: at() fonksiyonu ile sınırlı erişim kontrolü sağlayarak dizi sınırlarının aşılması (out-of-bounds access) durumunda istisna fırlatır.

STL Algoritmaları ile Uyumluluk: Vektörler, STL’deki sıralama, arama, dönüştürme gibi birçok algoritma ile sorunsuz bir şekilde kullanılabilir.

Vektörlerin Temel Kullanımı

Şimdi vektörlerin C++ kodunda nasıl kullanıldığına dair temel adımlara bakalım.

1. Vektör Kütüphanesini Dahil Etme ve İsim Alanı

Bir vektör kullanmadan önce, programınıza vector başlık dosyasını dahil etmeniz gerekir:

C++ İşaretçiler (Pointers)

İşaretçiler, C++ programlamada bellekteki diğer değişkenlerin adreslerini tutan özel değişkenlerdir. Bellek yönetimi, dinamik veri yapıları oluşturma ve fonksiyonlara argümanları referans yoluyla geçirme gibi birçok güçlü programlama tekniği için temel teşkil ederler.

İşaretçi Nedir?

Bir işaretçi, bir veri türünün bellekteki konumunu (adresini) saklar. Bir değişkenin adresini bir işaretçide sakladığınızda, o işaretçi o değişkene “işaret eder”.

İşaretçi Tanımlama

Bir işaretçi, işaret edeceği veri türü ve ardından bir yıldız işareti (*) ile tanımlanır.

Kaç Tane Var

Elimizde bir problem var. Bir sayı dizisi. Öncelikle bu bir ilişki bulma sorusu. Ama bu soruyu bir programlama veya algoritma sorusuna da çevirebiliriz. Soru aşağıdaki gibi.

• 1
• 11
• 21
• 1211
• 111221

Sırada ki sayı kaçtır?