alpsahin/tubitak-olimpiyat-dataset-v2 huggingface dataset:
Bilgisayar Olimpiyatı 2014, 1. Aşama, Soru 18

## [18 – 20] Sorular için Açıklama
Elemanları tamsayılar olan sıralı ikililerden oluşmuş kümeler düşünelim. Bunlara ilinti diyeceğiz. Örnek olarak, R ve S şu şekilde tanımlanmış iki ilinti olsun:
\[ R=\{(14,3),(121,22),(45,123)\},\quad S=\{(111,131),(3,86),(21,1241),(1,9)\} \]
İki ilinti arasında tanımlanan • işlemi, birinci ilintinin bütün ikilileriyle ikinci ilintinin bütün ikililerini karşılaştırmakta, birinci ikilinin ilk elemanı ikinci ikilinin ikinci elemanından daha fazla basamağa sahip ise, ilk elemanı birinci ikilinin ikinci elemanı ve ikinci elemanı ikinci ikilinin birinci elemanı olan yeni bir ikili oluşturmaktadır. Bu şekilde oluşturulan tüm ikililer sonuç ilintisini meydana getirmektedir. Örneğin, yukarıda verilen R ve S için,
\[ R \bullet S = \{(3, 1), (22, 3), (22, 1), (123, 1)\} \]

---

\( R = \{(1234,21), (23,145), (4,12)\} \)  ve  \( S = \{(4321,1), (1,324), (12,34)\} \)  olduğuna göre  \( R \bullet S \)  aşağıdakilerden hangisidir?

Şıklar:
A) \( \{(21,1),(21,324),(21,34),(145,1),(145,34)\} \) | B) \( \{(23,1),(23,12),(12,1),(12,12)\} \) | C) \( \{(23,4321),(23,1),(21,4321),(21,1)\} \) | D) \( \{(21,4321),(21,1),(21,12),(145,4321)\} \) | E) Hiçbiri

Cevap: D \( \{(21,4321),(21,1),(21,12),(145,4321)\} \)

Çözüm:
R ilintisindeki ikililerin ilk elemanlarının basamak sayıları sırasıyla 4, 2 ve 1'dir.
S ilintisindeki ikililerin ikinci elemanlarının basamak sayılarıysa sırasıyla 1, 3 ve 2'dir.
O zaman (1234,21) ile S kümesindeki her ikili eşleşerek (21, 4321), (21, 1) ve (21, 12) ikililerini oluşturur.
(23, 145) ikilisi ise S kümesinde sadece (4321, 1) ikilisiyle eşleşerek (145, 4321) ikilisini oluşturur.
Başka ikili oluşturulamaz.
Bilgisayar Olimpiyatı 2014, 1. Aşama, Soru 19

## [18 – 20] Sorular için Açıklama
Elemanları tamsayılar olan sıralı ikililerden oluşmuş kümeler düşünelim. Bunlara ilinti diyeceğiz. Örnek olarak, R ve S şu şekilde tanımlanmış iki ilinti olsun:
\[ R=\{(14,3),(121,22),(45,123)\},\quad S=\{(111,131),(3,86),(21,1241),(1,9)\} \]
İki ilinti arasında tanımlanan • işlemi, birinci ilintinin bütün ikilileriyle ikinci ilintinin bütün ikililerini karşılaştırmakta, birinci ikilinin ilk elemanı ikinci ikilinin ikinci elemanından daha fazla basamağa sahip ise, ilk elemanı birinci ikilinin ikinci elemanı ve ikinci elemanı ikinci ikilinin birinci elemanı olan yeni bir ikili oluşturmaktadır. Bu şekilde oluşturulan tüm ikililer sonuç ilintisini meydana getirmektedir. Örneğin, yukarıda verilen R ve S için,
\[ R \bullet S = \{(3, 1), (22, 3), (22, 1), (123, 1)\} \]

---

\( R \bullet S = \{(222, 111), (22, 111), (2, 111), (2, 111)\} \)  olduğuna göre R ve S ilintileri aşağıdakilerden hangisi olabilir?

Şıklar:
A) \( R = \{(11, 222), (1, 2), (222, 1)\} \)  ve  \( S = \{(11, 222), (1, 22)\} \) | B) \( R = \{(111, 222), (11, 22), (1111, 2)\} \)  ve  \( S = \{(11, 222), (111, 2)\} \) | C) \( R = \{(111, 22), (1, 222), (1111, 2)\} \)  ve  \( S = \{(1, 2), (11, 22), (111, 222)\} \) | D) \( R = \{(111, 2), (1111, 22)\} \)  ve  \( S = \{(1, 2), (11,22), (1, 222)\} \) | E) Hiçbiri

Cevap: B \( R = \{(111, 222), (11, 22), (1111, 2)\} \)  ve  \( S = \{(11, 222), (111, 2)\} \)

Çözüm:
S kümesinde ilk elemanı 111 olan ve ikinci elemanının basamak sayısı R kümesinde tam olarak 3 tane ikilinin ilk elemanının basamak sayısından az olan bir ikili bulunmaktadır. Sadece bu gözlem ile A, C ve D şıklarının sağlamadığını görürüz. B şıkkında bu şartı sağlayan (111, 2) ikilisi bulunmaktadır.
R kümesinde ikinci elemanı 2 olan ve ilk elemanının basamak sayısı, S kümesinde tam olarak 2 tane ikilinin ikinci elemanının basamak sayısından fazla olan bir ikili bulunmaktadır. B şıkkında bu şartı sağlayan (111, 2), ikilisi bulunmaktadır ve daha farklı bir ikili oluşturacak iki tane ikili bulunmamaktadır.
Bilgisayar Olimpiyatı 2014, 1. Aşama, Soru 20

## [18 – 20] Sorular için Açıklama
Elemanları tamsayılar olan sıralı ikililerden oluşmuş kümeler düşünelim. Bunlara ilinti diyeceğiz. Örnek olarak, R ve S şu şekilde tanımlanmış iki ilinti olsun:
\[ R=\{(14,3),(121,22),(45,123)\},\quad S=\{(111,131),(3,86),(21,1241),(1,9)\} \]
İki ilinti arasında tanımlanan • işlemi, birinci ilintinin bütün ikilileriyle ikinci ilintinin bütün ikililerini karşılaştırmakta, birinci ikilinin ilk elemanı ikinci ikilinin ikinci elemanından daha fazla basamağa sahip ise, ilk elemanı birinci ikilinin ikinci elemanı ve ikinci elemanı ikinci ikilinin birinci elemanı olan yeni bir ikili oluşturmaktadır. Bu şekilde oluşturulan tüm ikililer sonuç ilintisini meydana getirmektedir. Örneğin, yukarıda verilen R ve S için,
\[ R \bullet S = \{(3, 1), (22, 3), (22, 1), (123, 1)\} \]

---

R = ((111, 2), (11, 22), (111, 222)) ve R • S = ((2, 11), (2, 111), (22, 11), (222, 11), (222, 111)) olduğuna göre S aşağıdakilerden hangisi olabilir?

Şıklar:
A) \( S = \{(11, 2), (11, 22), (1, 222), (11, 2222)\} \) | B) \( S = \{(11, 2), (111, 222), (11, 22)\} \) | C) \( S = \{(111, 2), (11, 22), (1111, 222)\} \) | D) \( S = \{(1, 2), (11, 22)\} \) | E) Hiçbiri

Cevap: A \( S = \{(11, 2), (11, 22), (1, 222), (11, 2222)\} \)

Çözüm:
S kümesinde ikinci elemanın basamak sayısı 2'den küçük, ilk elemanı 11 olan bir ikili bulunmalıdır. Şıklardaki düzene göre bu eleman (11, 2) olur. (C ve D olamaz.)
Aynı zamanda S kümesinde ikinci elemanın basamak sayısı 2 olan ve ilk elemanı 111 olan bir ikili daha bulunmalıdır. Şıklardaki düzene göre bu elema (111, 22) olur. (B olamaz.)
S ikinci ikilisinin basamak sayısı 2'den büyük sınırsız sayıda eleman olabilir. Bu elemanlar cevabı değiştirmez. (A olabilir.)
Bilgisayar Olimpiyatı 2014, 1. Aşama, Soru 21

## [21 – 23] Sorular için açıklama
Hanoi kuleleri probleminde 3 tane direk (A, B ve C) vardır. Başlangıçta, A direğinde aşağıdan yukarıya büyükten küçüğe doğru dizilmiş n tane disk vardır, diğer iki direk ise boştur
(Şekli inceleyiniz, şekilde n = 3). Diskler 1 den n'ye kadar en üstten başlanarak numaralandırılır.
Problemde amaç A direğinden B direğine bütün diskleri her seferinde en fazla bir diskin yerini değiştirerek taşımaktır. Taşıma sırasında hiçbir zaman büyük bir disk kendisinden daha küçük bir diskin üzerine ya da direk harici başka bir yere konulamaz. C direği işlem sırasında yardımcı direk olarak rol oynar.
Problemin bir çözümü aşağıda verilen özyineli algoritma ile yapılabilir. Algoritmada, Hanoi (n, A, B, C), A'daki n diski B'ye taşımayı C'yi yardımcı direk olarak kullanarak çöz olarak okunur. 2. ve 5. satırlarda gerçek taşıma işlemleri yapılmaktadır ve bunların her biri bir adım olarak sayılmaktadır. Örnek olarak n = 2 için çalıştırdığımızda problem 3 adımda çözülecek ve çıktı sırayla şu adımlardan oluşacaktır: (1) Disk 1'yi A'dan C'ye taşı, (2) Disk 2'yi A'dan B'ye taşı, (3) Disk 1'yi C'den B'ye taşı.
**Algorithm 1 Hanoi(n, A, B, C):**
1: if n == 1 then
2:    Disk n'yi A'dan B'ye taşı
3: else if n > 1 then
4:    Hanoi(n - 1, A, C, B)
5:    Disk n'yi A'dan B'ye taşı
6:    Hanoi(n - 1, C, B, A)
7: end if
## AÇIKLAMA
N tane diski A'dan B'ye taşıma algoritması şu şekildedir. (B ve C boş kabul edilir.)
• A'da üstteki n-1 diski C'ye taşı
• En alttaki diski A'dan B'ye taşı
• Kalan n-1 diski C'den B'ye taşı
Bu şekilde n disk A'dan B'ye taşınmış olur. Buradaki A ve B soruda verilen 3 direğin ismi değildir. Yani A değişkeni 3.direği (C direğini), B değişkeni 1.direği (A direğini) ifade edebilir.

---

n = 3 disk için verilen algoritma toplam kaç adımda bütün diskleri A'dan B'ye taşır?

Şıklar:
A) 3 | B) 4 | C) 5 | D) 6 | E) 7

Cevap: E 

Çözüm:
f(n) fonksiyonuna, n diski A'dan B'ye taşımak için gerekli adım sayısı diyelim. Algoritmadan anlaşılacağı üzere f(n) = 2*f(n-1) + 1 diyebiliriz. O zaman:
•  \( f(1)=1 \)
•  \( f(2)=2*f(1)+1=2*1+1=3 \)
•  \( f(3)=2*f(2)+1=2*3+1=7 \)
olur.
Bilgisayar Olimpiyatı 2014, 1. Aşama, Soru 22

## [21 – 23] Sorular için açıklama
Hanoi kuleleri probleminde 3 tane direk (A, B ve C) vardır. Başlangıçta, A direğinde aşağıdan yukarıya büyükten küçüğe doğru dizilmiş n tane disk vardır, diğer iki direk ise boştur
(Şekli inceleyiniz, şekilde n = 3). Diskler 1 den n'ye kadar en üstten başlanarak numaralandırılır.
Problemde amaç A direğinden B direğine bütün diskleri her seferinde en fazla bir diskin yerini değiştirerek taşımaktır. Taşıma sırasında hiçbir zaman büyük bir disk kendisinden daha küçük bir diskin üzerine ya da direk harici başka bir yere konulamaz. C direği işlem sırasında yardımcı direk olarak rol oynar.
Problemin bir çözümü aşağıda verilen özyineli algoritma ile yapılabilir. Algoritmada, Hanoi (n, A, B, C), A'daki n diski B'ye taşımayı C'yi yardımcı direk olarak kullanarak çöz olarak okunur. 2. ve 5. satırlarda gerçek taşıma işlemleri yapılmaktadır ve bunların her biri bir adım olarak sayılmaktadır. Örnek olarak n = 2 için çalıştırdığımızda problem 3 adımda çözülecek ve çıktı sırayla şu adımlardan oluşacaktır: (1) Disk 1'yi A'dan C'ye taşı, (2) Disk 2'yi A'dan B'ye taşı, (3) Disk 1'yi C'den B'ye taşı.
**Algorithm 1 Hanoi(n, A, B, C):**
1: if n == 1 then
2:    Disk n'yi A'dan B'ye taşı
3: else if n > 1 then
4:    Hanoi(n - 1, A, C, B)
5:    Disk n'yi A'dan B'ye taşı
6:    Hanoi(n - 1, C, B, A)
7: end if
## AÇIKLAMA
N tane diski A'dan B'ye taşıma algoritması şu şekildedir. (B ve C boş kabul edilir.)
• A'da üstteki n-1 diski C'ye taşı
• En alttaki diski A'dan B'ye taşı
• Kalan n-1 diski C'den B'ye taşı
Bu şekilde n disk A'dan B'ye taşınmış olur. Buradaki A ve B soruda verilen 3 direğin ismi değildir. Yani A değişkeni 3.direği (C direğini), B değişkeni 1.direği (A direğini) ifade edebilir.

---

n = 4 disk için diskleri A'dan B'ye taşımak istersek verilen algoritma çalıştırıldığında çözümün 3. adımı aşağıdakilerden hangisidir?

Şıklar:
A) Disk 1'yi C'den B'ye taşı D) Disk 1'yi B'den A'ye taşı | B) Disk 1'yi A'den B'ye taşı E) Hiçbiri | C) Disk 1'yi A'den C'ye taşı

Cevap: A Disk 1'yi C'den B'ye taşı D) Disk 1'yi B'den A'ye taşı

Çözüm:
Algoritmayı işletirsek şu işlemler sırayla yapılır:
•	 Hanoi (4,A,B,C) fonksiyonu çağırılır.
•	 Hanoi (3,A,C,B) fonksiyonu çağırılır.
•	 Hanoi (2,A,B,C) fonksiyonu çağırılır.
•	 Hanoi (1,A,C,B) fonksiyonu çağırılır.
•	 Disk 1 A'dan C'ye taşınır.
•	 Hanoi (2,A,B,C) fonksiyonuna dönülür.
•	 Disk 2 A'dan B'ye taşınır.
•	 Hanoi (1,C,B,A) fonksiyonu çağırılır.
22. n = 4 disk için diskleri A'dan B'ye taşımaksıtersek verilen algoritma çalıştırıldığında çözümün3. adımı aşağıdakilerden hangisidir?
Algoritmayı işletirsek şu işlemler sınayla yapılır:
•	 Hanoi (5,A,B,C) fonksiyonu çağırılır.
•	 Hanoi (4,A,C,B) fonksiyonu çağırılır.
•	 Hanoi (3,A,B,C) fonksiyonu çağırılır.
•	 Hanoi (2,A,C,B) fonksiyonu çağırılır.
•	 Hanoi (2,A,C,B) fonksiyonu çağırılır. •	 Hanoi (1,A,B,C) fonksiyonu çağırılır.
•	 Disk 1 A'dan B'ye taşınır.
•	 Hanoi (2,A,C,B) fonksiyonuna dönülür.
•	 Disk 2 A'dan C'ye taşınır.
Bilgisayar Olimpiyatı 2014, 1. Aşama, Soru 23

## [21 – 23] Sorular için açıklama
Hanoi kuleleri probleminde 3 tane direk (A, B ve C) vardır. Başlangıçta, A direğinde aşağıdan yukarıya büyükten küçüğe doğru dizilmiş n tane disk vardır, diğer iki direk ise boştur
(Şekli inceleyiniz, şekilde n = 3). Diskler 1 den n'ye kadar en üstten başlanarak numaralandırılır.
Problemde amaç A direğinden B direğine bütün diskleri her seferinde en fazla bir diskin yerini değiştirerek taşımaktır. Taşıma sırasında hiçbir zaman büyük bir disk kendisinden daha küçük bir diskin üzerine ya da direk harici başka bir yere konulamaz. C direği işlem sırasında yardımcı direk olarak rol oynar.
Problemin bir çözümü aşağıda verilen özyineli algoritma ile yapılabilir. Algoritmada, Hanoi (n, A, B, C), A'daki n diski B'ye taşımayı C'yi yardımcı direk olarak kullanarak çöz olarak okunur. 2. ve 5. satırlarda gerçek taşıma işlemleri yapılmaktadır ve bunların her biri bir adım olarak sayılmaktadır. Örnek olarak n = 2 için çalıştırdığımızda problem 3 adımda çözülecek ve çıktı sırayla şu adımlardan oluşacaktır: (1) Disk 1'yi A'dan C'ye taşı, (2) Disk 2'yi A'dan B'ye taşı, (3) Disk 1'yi C'den B'ye taşı.
**Algorithm 1 Hanoi(n, A, B, C):**
1: if n == 1 then
2:    Disk n'yi A'dan B'ye taşı
3: else if n > 1 then
4:    Hanoi(n - 1, A, C, B)
5:    Disk n'yi A'dan B'ye taşı
6:    Hanoi(n - 1, C, B, A)
7: end if
## AÇIKLAMA
N tane diski A'dan B'ye taşıma algoritması şu şekildedir. (B ve C boş kabul edilir.)
• A'da üstteki n-1 diski C'ye taşı
• En alttaki diski A'dan B'ye taşı
• Kalan n-1 diski C'den B'ye taşı
Bu şekilde n disk A'dan B'ye taşınmış olur. Buradaki A ve B soruda verilen 3 direğin ismi değildir. Yani A değişkeni 3.direği (C direğini), B değişkeni 1.direği (A direğini) ifade edebilir.

---

n = 5 disk için diskleri A'dan B'ye taşımaksıtersek verilen algoritma çalıştırıldığında çözümün 2. adımı aşağıdakilerden hangisidir?

Şıklar:
A) Disk 1'yi A'den B'ye taşı B) Disk 1'yi A'den C'ye taşı C) Disk 1'yi B'den C'ye taşı D) Disk 1'yi C'den B'ye taşı E) Hiçbiri | B) Disk 1'yi A'den C'ye taşı E) Hiçbiri

Cevap: E Hiçbiri

Çözüm:
Algoritmayı işletirsek şu işlemler sırayla yapılır:
• Hanoi (5,A,B,C) fonksiyonu çağırılır.
• Hanoi (4,A,C,B) fonksiyonu çağırılır.
• Hanoi (3,A,B,C) fonksiyonu çağırılır.
• Hanoi (2,A,C,B) fonksiyonu çağırılır.
• Hanoi (1,A,B,C) fonksiyonu çağırılır.
• Disk 1 A’dan B’ye taşınır.
• Hanoi (2,A,C,B) fonksiyonuna dönülür.
• Disk 2 A’dan C’ye taşınır.
Bilgisayar Olimpiyatı 2014, 1. Aşama, Soru 24

## [24 – 25] Sorular için açıklama
Bir problemin çözümü için iki algoritma geliştirilmiştir: bunlara *Algoritmal* ve *Algoritma2* diyelim. Tek çekirdekli bir işlemcide *Algoritmal*'ın çalışma zamanı \(t_1 = 2n^2C + 10OT\) saniye,
Algoritma2'nin çalışma zamanı ise \(t_2 = 3nC + nT\) saniyedir. Formüllerde \(n =\) problemin girdi boyu, \(C =\) işlemcinin bir çarpma işlemini saniye biriminden yapma süresi, \(T =\) işlemcinin bir toplama işlemini saniye biriminden yapma süresidir.
Bahsedilen işlemci saniyede 1 milyar çarpma işlemi veya 2 milyar toplama işlemi yapabilmektedir.

---

Bu işlemcide *Algoritmal*'ın 1 saniyede çözebileceği maksimum girdi boyu kaçtır?

Şıklar:
A) 256 | B) 3.452 | C) 13.253 | D) 22.360 | E) 128.645

Cevap: D 22.360

Çözüm:
\(C = 2T = 10^9\) saniye diyelim. \(t_1 = 2n^2C + 50C\) olur. Soruda \(t_1 = 1\) durumunu sağlayacak \(n\) değeri isteniyor. Yani \(\sqrt{\frac{t_1}{2C} - 25} = n\) denklemindeki değeri isteniyor.
\[n = \sqrt{\frac{t_1}{2C} - 25} = \sqrt{(5 * 10^8 - 25) = 22.360 + c \text{ ve } 0 < c < 1}\]
Bilgisayar Olimpiyatı 2014, 1. Aşama, Soru 25

## [24 – 25] Sorular için açıklama
Bir problemin çözümü için iki algoritma geliştirilmiştir: bunlara *Algoritmal* ve *Algoritma2* diyelim. Tek çekirdekli bir işlemcide *Algoritmal*'ın çalışma zamanı \(t_1 = 2n^2C + 10OT\) saniye,
Algoritma2'nin çalışma zamanı ise \(t_2 = 3nC + nT\) saniyedir. Formüllerde \(n =\) problemin girdi boyu, \(C =\) işlemcinin bir çarpma işlemini saniye biriminden yapma süresi, \(T =\) işlemcinin bir toplama işlemini saniye biriminden yapma süresidir.
Bahsedilen işlemci saniyede 1 milyar çarpma işlemi veya 2 milyar toplama işlemi yapabilmektedir.

---

Bu işlemcide *Algoritma2*'nin 1 saniyede çözebileceği maksimum girdi boyu kaştır?

Şıklar:
A) 3.844.128 | B) 47.435.312 | C) 285.714.285 | D) 333.333.333 | E) 1.000.000.000

Cevap: C 285.714.285

Çözüm:
\[t_2 = 3nC + nT = 6nT + nT = 7nT\]
Soruda \(t_2 = 1\) olmasını gerektiren en büyük \(n\) değeri isteniyor.
\[1 = 7 \cdot n \cdot \frac{10^9}{2} \rightarrow n = \frac{2 * 10^9}{7} = 285.714.285 + c \text{ ve } 0 < c < 1\]
Bilgisayar Olimpiyatı 2014, 1. Aşama, Soru 26

## [26 – 27] Sorular için Açıklama
Asimtotik üst sınırı ifade etmede kullanılan büyük-O notasyonu şöyle tanımlanır. \(f(n)\) ve
\(g(n)\) negatif olmayan tamsayılardan pozitif reel sayılara tanımlı birer fonksiyon ve \(O(g(n))\)
bir fonksiyon kümesi olsun. \(f(n) \in O(g(n))\) dir ancak ve ancak öyle bir pozitif reel \(k\) sabiti ve
bir \(nO \ge O\) tamsayı sabiti için \(f(n) \le kg(n)\), \(\forall n \ge n_0\) eşitsizliği sağlanır.
Tanımı örnekle açıklayalım. \(f(n) = 2n^2 + 5n - 10\), \(h(n) = n^2 \log n - 100n + 1\), \(g(n) = n^2\) için
\(f(n) \in O(g(n))\) (mesela \(n_0 = 1\) ve \(k = 7\) seçilerek \(f(n) = 2n^2 + 5n - 10 \le 7n^2\), \(\forall n \le n_0 = 1\) sağlanır), fakat \(h(n) = \xi g(n)\) dir (çünkü \(k\) sabiti ne kadar büyük seçilirse seçilsin \(\log n\) değeri sonsuzda \(k\) dan daha büyüktür, yani eşitsizliği sağlayan \(n_0\) ve \(k\) değerleri bulunamaz).

---

Aşağıdaki ifadelerden hangileri yanlıştır?
(I) \(2 \log n^2 + 5 \in O(\log n)\)
(II) \(8 \log \sqrt{n} + 3O \in O(\log n)\)
(III) \(\sqrt{\log n} - 3 \in O(\log n)\)

Şıklar:
A) Yalnız I | B) Yalnız II | C) Yalnız III | D) I ve II | E) Hiçbiri

Cevap: E Hiçbiri

Çözüm:
İfadelerin doğruluğunu inceleyelim:

(I) \( 2^{\log_7 n} + (2n)^{1/2} = n^{\log_7 2} + \sqrt{2} \cdot n^{1/2} < k \cdot n \). 
Burada \( \log_7 2 \approx 0.35 \) olduğu için sol taraf yaklaşık \( n^{0.35} + 1.41n^{0.5} \) şeklindedir. 
Sağ taraf ise doğrusal büyüme \( O(n) \) sergiler. Dolayısıyla k=2 için ifade doğru olur.

(II) \( 2^{n+1} + n^3 = 2 \cdot 2^n + n^3 < k \cdot 2^n \). 
Üstel fonksiyon \( 2^n \), polinomsal \( n^3 \) terimini domine eder. 
k=3 gibi bir değer için \( 2 \cdot 2^n + n^3 < 3 \cdot 2^n \) eşitsizliği yeterince büyük n'ler için doğru olur.

(III) \( 2^{\log_7 n} + (2n)^{1/2} < n \). 
Sol tarafın en yüksek dereceli terimi \( \sqrt{n} \) (yani \( n^{0.5} \)) iken sağ taraf \( n^{1} \)'dir. 
Derecesi küçük olan fonksiyon sonsuza giderken her zaman \( n \)'den küçük kalacağı için, 
bu ifade herhangi bir k katsayısına gerek duymadan tüm büyük n değerleri için doğru olur.
Bilgisayar Olimpiyatı 2014, 1. Aşama, Soru 27

## [26 – 27] Sorular için Açıklama
Asimtotik üst sınırı ifade etmede kullanılan büyük-O notasyonu şöyle tanımlanır. \(f(n)\) ve
\(g(n)\) negatif olmayan tamsayılardan pozitif reel sayılara tanımlı birer fonksiyon ve \(O(g(n))\)
bir fonksiyon kümesi olsun. \(f(n) \in O(g(n))\) dir ancak ve ancak öyle bir pozitif reel \(k\) sabiti ve
bir \(nO \ge O\) tamsayı sabiti için \(f(n) \le kg(n)\), \(\forall n \ge n_0\) eşitsizliği sağlanır.
Tanımı örnekle açıklayalım. \(f(n) = 2n^2 + 5n - 10\), \(h(n) = n^2 \log n - 100n + 1\), \(g(n) = n^2\) için
\(f(n) \in O(g(n))\) (mesela \(n_0 = 1\) ve \(k = 7\) seçilerek \(f(n) = 2n^2 + 5n - 10 \le 7n^2\), \(\forall n \le n_0 = 1\) sağlanır), fakat \(h(n) = \xi g(n)\) dir (çünkü \(k\) sabiti ne kadar büyük seçilirse seçilsin \(\log n\) değeri sonsuzda \(k\) dan daha büyüktür, yani eşitsizliği sağlayan \(n_0\) ve \(k\) değerleri bulunamaz).

---

Aşağıdaki ifadelerden hangileri doğrudur?
(I) \(2^{\log_7 n} + \sqrt{2n} \in O(n)\)
(II) \(2^{n+1} + n^3 \in O(2^n)\)
(III) \(3^{2n-1} + 2^n \in O(4^n)\)

Şıklar:
A) Yalnız I | B) Yalnız II | C) Yalnız III | D) I ve II | E) Hiçbiri

Cevap: D I ve II

Çözüm:
İfadelerin doğruluğunu inceleyelim:

(I) 2^log_7 n + (2n)^1/2 < k x n. 

(II) 2^n+1 + n^3 = 2 x 2^n + n^3 < k x 2^n. 

(III) 2^log_7 n + (2n)^1/2 < n. 

I ve II’de verilen ifadeler yeterince büyük k değerleri için doğru olurken III. İfade ise hiçbir k değeri ve tüm n büyük eşit n_0 için doğru olmaz.
Bilgisayar Olimpiyatı 2014, 1. Aşama, Soru 29

Aşağıdaki ifadelerden hangileri doğrudur?
(I) Bst olduğu bilinen her A[1..2n] dizisinde \(\sum_{i=1}^{n} A[i] \cdot \sum_{j=n+1}^{2n} A[j]\).
(II) Bst olmayan bir A[1..n] dizisi elemanlarının yerleri değiştirilerek bst haline getirilebilir.
(III) Bst olduğu bilinen A[1..2n] dizisinin bir altdizisi olan A[n..2n] dizisi de bir bst dir.

Şıklar:
A) Yalnız 1 | B) Yalnız 11 | C) Yalnız 111 | D) 1 ve 11 | E) 11 ve 111

Cevap: B Yalnız 11

Çözüm:
İfadeleri inceleyelim:
- A[n] ≥ A[2n] olduğundan ve A[n] değeri aşırı büyük bir sayı olabileceğinden ifade yanlıştır.
- Bst tanımına göre çelişen büyüklük sıralamaları bulunmuyor. Yani herhangi bir dizi uygun bir sırada bst olabilir. Doğru.
- A[n..2n] dizisinin bst olabilmesi için A[n] ≤ A[n+2] olması gerekir çünkü A[1] bu dizinin 1..A[n+2] bu dizinin 3.elemanıdır. A[1..2n] dizisinde bu şart sağlamayabilir. Yanlış.
Bilgisayar Olimpiyatı 2014, 1. Aşama, Soru 33

[32 – 35] Sorular için Açıklama
X, Y ve Z aşağıda verildiği gibi tanımlanmış karşılıklı özyineli nesnelerdir. Tanımlarda toplam dört farklı (atomik) sembol (a, b, c ve ●) vardır. X, Y ya da Z ile tanımlanamayan tüm nesneler geçersizdir.
\[
X = \begin{bmatrix} a & ya da; \\ b \cdot X' \cdot a & ya da; \\ b \cdot Y' \cdot b & ya da; \\ b \cdot Z' \cdot c & ya da; \end{bmatrix} \quad Y = \begin{bmatrix} \cdot \cdot \cdot X' \cdot a & ya da; \\ \cdot \cdot \cdot Y' \cdot b & ya da; \\ \cdot \cdot \cdot Z' \cdot a & ya da; \end{bmatrix} \quad Z = \begin{bmatrix} a \cdot b & ya da; \\ c \cdot X' \cdot X'' & ya da; \\ b \cdot Y' \cdot Y'' & ya da; \\ a \cdot Z' \cdot Z'' & ya da; \end{bmatrix}
\]
İfadelerdeki X' ve X'' nesneleri X; Y' ve Y'' nesneleri Y; Z' ve Z'' nesneleri Z cinsinden nesnelerdir. Sırasıyla X, Y ve Z tipinden nesneleri girdi olarak alan f, g ve h fonksiyonları aşağıda tanımlanmıştır. Bu fonksiyonlar karşılıklı özyineli fonksiyonlar olup tamsayı değerler döndürürler.
\[
\begin{array}{l@{\quad}l@{\quad}l}
\text{ff(X)} = \begin{cases} -1 & \text{eğer } X = a \\ -4 + \text{f(X')} & \text{eğer } X = b \cdot X' \cdot a \\ -2 + \text{g(Y')} & \text{eğer } X = b \cdot Y' \cdot b \\ -1 + \text{h(Z')} & \text{eğer } X = b \cdot Z' \cdot c \end{cases} & \text{g(Y)} = \begin{cases} -2 & \text{eğer } Y = \cdot \\ \text{f(X')} & \text{eğer } Y = X' \cdot cX'' \\ -1 + 2\text{g(Y')} & \text{eğer } Y = Y' \cdot bY'' \\ -3 + 3\text{h(Z')} & \text{eğer } Y = Z' \cdot aZ'' \end{cases}
\end{array}
\]
AÇIKLAMA
Her nesnenin yukarıda belirtilen durumlarını yukarıdan aşağı numaralandıralım (X nesnesinin 1.durumu a, 2.durumu b • X' • a ...) ve soruları ona göre çözelim. Aynı zamanda çözümü hızlandırmak için X, Y ve Z nesnelerinin ● durumları sayısını artıralım.
\[
X: a, a \cdot b, b \cdot a, a, b \cdot \cdot \cdot \cdot b, b \cdot a \cdot b \cdot c
\]
\[
Y: \cdot, a \cdot c, a, \cdot \cdot b, \cdot a \cdot b \cdot a \cdot a \cdot b
\]
\[
Z: a \cdot b, c \cdot a, b \cdot \cdot \cdot \cdot a, a \cdot a \cdot b \cdot a \cdot b
\]

---

h (b \(\bullet a \bullet caa \bullet ca\)) işleminin sonucu kaçtır?

Şıklar:
A) -6 | B) -4 | C) -2 | D) -1 | E) O

Cevap: E O

Çözüm:
h fonksiyonu Z nesnesi alır. O zaman ifademiz b \(\bullet Y' \bullet Y''\) formatındadır. Y'ler ise \(a \bullet c\) a formatındadır. G(\(a \bullet c \bullet a\)) = f(a) = -1 olduğundan h(z) = 2 + 2 * (-1) = O olur.