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

## [16 – 17] Sorular için Açıklama
Aşağıda yedi düğüm ve bu düğümleri birbirine bağlayan, uzunlukları yanlarında yazılı kenarlardan oluşan bir çizge görülmektedir. Bu çizgede birbirine doğrudan bir kenarla bağlı düğümlere birbirlerinin komşusu denir.
[GÖRSEL]
Bir bilgisayar tarafından çizge üzerindeki bütün düğümlerin tespit edilmesi için arama işlemi gerçekleştirilir.
Derinlik-öncelikli arama yönteminde, çizge üzerinden bir başlangıç düğümü seçilir ve tüm düğümler keşfedilinceye kadar (çizgedeki her düğüm en az bir kez ziyaret edilinceye kadar) arama işlemi yapılır. Arama işleminin herhangi bir adımında x düğümünden y düğümüne geldiğimizi ve bir sonraki adımda da y düğümünden z düğümüne geçmemiz gerektiğini kabul edelim. Buna göre z düğümünün, y düğümünün daha önce ziyaret edilmemiş komşularından kendisine en yakını olması gerekir. Eğer y düğümünün bütün komşuları daha önceden ziyaret edilmişse bir çıkmaz durumu oluşur. Çıkmaz durumunda y düğümünden bir adım geri gidilerek x düğümüne dönülür ve x düğümünün daha önce ziyaret edilmemiş komşularından kendisine en yakın olan düğüme geçilir. Çıkmaz durumu oluştuğu sürece geri gitme işlemi yapılır. Arama, çizgedeki tüm düğümler en az bir kez ziyaret edilinceye kadar sürdürülür.
Genişlik-öncelikli arama yönteminde de tıpkı derinlik-öncelikli arama yönteminde olduğu gibi çizge üzerinden seçilen bir başlangıç düğümünden yola çıkılır ve tüm düğümler keşfedilinceye kadar arama işlemi yapılır. Bu yöntemde, başlangıç düğümü olan x düğümünün daha önce ziyaret edilmemiş komșuları kendisine en yakın olandan en uzak olana doğru sırayla ziyaret edilir (her ziyaretten sonra x düğümüne geri dönülür). Bütün bu süreç boyunca ziyaret edilen düğümlerin sırası (x'e geri dönüşler hariç) S dizisine kaydedilir. İlk ziyaret edilen düğüm x düğümü olduğundan S dizisinin ilk elemanı x'dir. x düğümünün ziyaret edilebilecek başka bir komşusu kalmadığında S dizisinde x'den sonra bulunan y düğümüne atlanır ve anlatılan süreç y düğümünden başlanarak tekrarlanır. Ancak y düğümü S dizisine daha önceden yazılmış olduğu için tekrar yazılmaz. Yani, S dizisi tekrarsız elemanlardan oluşur. Arama, çizgedeki tüm düğümler en az bir keş ziyaret edilinceye kadar sürdürülür. Arama sonunda çizgedeki tüm düğümler ziyaret sıralamasına göre S dizisinde görülür.

---

Çizgede verilen aşağıdaki düğümlerden hangisinden başlanarak yapılan derinlik-öncelikli aramada en fazla sayıda çıkmaz durumuyla karşılaşılır?

Şıklar:
A) P7 | B) P5 | C) P4 | D) P3 | E) P1

Cevap: A P7

Çözüm:
Her şikçin derinlik-öncelikli arama başlatalım. Önceden ziyaret edilmiş her düğüm geri dönmeyi temsil edeceğinden en uzun gezme dizisine sahip olan en fazla geri çıkmaza girmiş demektir:
A) P7 - P6 - P2 - P1 - P4 - P5 - P4 - P1 - P2 - P3
B) P5 - P4 - P1 - P2 - P6 - P7 - P3
C) P4 - P5 - P1 - P2 - P6 - P7 - P3

text<|/ref|>TYPE=PICTUREURLTYPE=PICTUREURLTYPE=PICTUREURLTYPE=PICTUREURLTYPE=PICTUREUR
D) P3 - P7 - P6 - P2 - P1 - P4 - P5
E) P1 - P2 - P6 - P7 - P3 - P7 - P5 - P4
Açıkça görüldüğü gibi A şıkkı en uzun.
Bilgisayar Olimpiyatı 2017, 1. Aşama, Soru 17

## [16 – 17] Sorular için Açıklama
Aşağıda yedi düğüm ve bu düğümleri birbirine bağlayan, uzunlukları yanlarında yazılı kenarlardan oluşan bir çizge görülmektedir. Bu çizgede birbirine doğrudan bir kenarla bağlı düğümlere birbirlerinin komşusu denir.
[GÖRSEL]
Bir bilgisayar tarafından çizge üzerindeki bütün düğümlerin tespit edilmesi için arama işlemi gerçekleştirilir.
Derinlik-öncelikli arama yönteminde, çizge üzerinden bir başlangıç düğümü seçilir ve tüm düğümler keşfedilinceye kadar (çizgedeki her düğüm en az bir kez ziyaret edilinceye kadar) arama işlemi yapılır. Arama işleminin herhangi bir adımında x düğümünden y düğümüne geldiğimizi ve bir sonraki adımda da y düğümünden z düğümüne geçmemiz gerektiğini kabul edelim. Buna göre z düğümünün, y düğümünün daha önce ziyaret edilmemiş komşularından kendisine en yakını olması gerekir. Eğer y düğümünün bütün komşuları daha önceden ziyaret edilmişse bir çıkmaz durumu oluşur. Çıkmaz durumunda y düğümünden bir adım geri gidilerek x düğümüne dönülür ve x düğümünün daha önce ziyaret edilmemiş komşularından kendisine en yakın olan düğüme geçilir. Çıkmaz durumu oluştuğu sürece geri gitme işlemi yapılır. Arama, çizgedeki tüm düğümler en az bir kez ziyaret edilinceye kadar sürdürülür.
Genişlik-öncelikli arama yönteminde de tıpkı derinlik-öncelikli arama yönteminde olduğu gibi çizge üzerinden seçilen bir başlangıç düğümünden yola çıkılır ve tüm düğümler keşfedilinceye kadar arama işlemi yapılır. Bu yöntemde, başlangıç düğümü olan x düğümünün daha önce ziyaret edilmemiş komșuları kendisine en yakın olandan en uzak olana doğru sırayla ziyaret edilir (her ziyaretten sonra x düğümüne geri dönülür). Bütün bu süreç boyunca ziyaret edilen düğümlerin sırası (x'e geri dönüşler hariç) S dizisine kaydedilir. İlk ziyaret edilen düğüm x düğümü olduğundan S dizisinin ilk elemanı x'dir. x düğümünün ziyaret edilebilecek başka bir komşusu kalmadığında S dizisinde x'den sonra bulunan y düğümüne atlanır ve anlatılan süreç y düğümünden başlanarak tekrarlanır. Ancak y düğümü S dizisine daha önceden yazılmış olduğu için tekrar yazılmaz. Yani, S dizisi tekrarsız elemanlardan oluşur. Arama, çizgedeki tüm düğümler en az bir keş ziyaret edilinceye kadar sürdürülür. Arama sonunda çizgedeki tüm düğümler ziyaret sıralamasına göre S dizisinde görülür.

---

Çizgede verilen aşağıdaki düğümlerden hangisinden başlanarak yapılan genişlik-öncelikli aramada P4 düğümü en son ziyaret edilen düğüm (S dizisinin son elemanı) olur?

Şıklar:
A) P1 | B) P2 | C) P3 | D) P5 | E) P6

Cevap: C P3

Çözüm:
Her şık için genişlik-öncelikli arama başlatalım ve S dizisini yazalım:
A) P1 - P2 - P4 - P5 - P6 - P3 - P7
B) P2 - P1 - P6 - P3 - P4 - P5 - P7
C) P3 - P7 - P2 - P6 - P5 - P1 - P4
D) P5 - P4 - P1 - P6 - P2 - P7 - P3
E) P6 - P7 - P2 - P4 - P3 - P5 - P1
Açıkça görüldüğü gibi P3 ile başlayan arama en son P4 düğümünü ziyaret ediyor.
Bilgisayar Olimpiyatı 2017, 1. Aşama, Soru 18

Bir algoritma girdi olarak aldığı n adet sayıdan oluşturulan tekrarsız ve elemanları birbirinden farklı her bir ikili üzerine X işlemini uygulamaktadır. X işleminin de [1...log₂n] aralığındaki 2'nin kuvveti olan tam-sayılardan her biri için bir kez Y işlemi yaptığı bilinmektedir. Buna göre bu algoritma toplamda kaç tane Y işlemi yapar?

Şıklar:
A) \(n^2 \log_2(2^n)\) | B) \(\lfloor(n^2+n)/2\rfloor + \log_2 n\) | C) \(\lfloor(n2+n)/2\rfloor \log_2 n\) | D) \(\lfloor n \cdot (n-1)/2 \log_2(\log_2 n) \rfloor\) | E) \(\lfloor n \cdot (n-1)/2 \log_2(2^n) \rfloor\)

Cevap: D \(\lfloor n \cdot (n-1)/2 \log_2(\log_2 n) \rfloor\)

Çözüm:
Farklı ikiliğin sayısı \(n \cdot (n-1)/2\) kere X işlemi yapılır. [1, a) aralığındaki 2'nin katlarının sayısı \(\log_2\) (a) olduğundan her X işleminde \(\log_2(\log_2 n)\) kere Y işlemi yapılır.
Bilgisayar Olimpiyatı 2017, 1. Aşama, Soru 19

## [19 – 20] Sorular için Açıklama
Asimptotik alt sınırı ifade etmede kullanılan büyük-α gösterimi şöyle tanımlanır. c, pozitif bir reel sabit ve \(n_0\) da negatif olmayan bir tamsayı olmak üzere \(n \ge n_0\) şartını sağlayan tüm n sayıları için \(t(n) \ge c \cdot g(n)\) ise \(t(n)\) fonksiyonunun, \(g(n)\) fonksiyonunun büyük-α sınıfında olduğu söylenir. Bu durum \(t(n) \in \alpha(g(n))\) şeklinde gösterilir.
Örneğin \(t(n)=2^n\) ve \(g(n)=n^3\) olmak üzere \(t(n) \in \alpha(g(n))\) olarak kabul edilir. Çünkü \(c=1\) ve \(n_0=10\) değerleri için \(2^n \ge 1 \cdot n^3\), \(n \ge n_0=10\) sağlanır. Bunun aksine, \(n=5000n^2\) ve \(g(n)=n^3\) için \(t(n) \in \alpha(g(n))\) olarak kabul edilir, Çünkü \(c=5001\) ve \(n_0=1\) değerleri için \(5000n^2 < 5001n^3\) olacaktır.
Asimptotik alt sınırı ifadesinde dikkat edilmesi gereken bir nokta c sabitinin n sayısıyla kıyaslanamayacak kadar küçük bir sayı olmasıdır. n sayısı istenildiği kadar büyütülebilir.

---

Aşağıdaki ifadelerden hangisi ya da hangileri doğrudur?
(I) \(n^{\log_5} + \log_5 \in \alpha(n)\)
(II) \(\log \sqrt{\frac{1}{1000}} \in \alpha(n)\)
(III) \(\log 5^n + 4 \in \alpha(n)\)

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

Cevap: E II ve III

Çözüm:
n, değerini çok büyük seçebileceğimizden n'ye bağlı olmayan ifadelerin bir önemi kalmaz. Bu yüzden sadece n cinsinden ifadeleri dikkate alırız. c sayısı sayesinde bu ifadelerin katsayılarını da dikkate almayız. Eşitsizliğin sağ ile solu kolunu n'in sonsuza yakın değerleri için karşılaştırıp sol tarafın büyük veya yaklaşık eşit(c'yi artırabildiğimizden dolayı) olduğu durumlarda büyük-α gösterimini kullanabiliriz.
I) n sonsuz giderken \(\log_n 0\)'a yaklaşır. \(n^{\log_5}\)'te yaklaşır. Yani \(1 < n\). Yanlış
II) Logaritma kuralına göre üs dışarı çıkabilir. Yani ifade \(\frac{1}{n} \cdot \log_{100} 0\) şeklinde yazılırsa sol tarafta n sayısı kalır. Yani \(n \approx n\). Doğru.(c'yi ayarlayabiliriz.)
III) 2.seçenekteki kurala göre ifade \(n \cdot \log 5 + 4\) olur. Yani \(n \approx n\). Doğru.
Bilgisayar Olimpiyatı 2017, 1. Aşama, Soru 20

## [19 – 20] Sorular için Açıklama
Asimptotik alt sınırı ifade etmede kullanılan büyük-α gösterimi şöyle tanımlanır. c, pozitif bir reel sabit ve \(n_0\) da negatif olmayan bir tamsayı olmak üzere \(n \ge n_0\) şartını sağlayan tüm n sayıları için \(t(n) \ge c \cdot g(n)\) ise \(t(n)\) fonksiyonunun, \(g(n)\) fonksiyonunun büyük-α sınıfında olduğu söylenir. Bu durum \(t(n) \in \alpha(g(n))\) şeklinde gösterilir.
Örneğin \(t(n)=2^n\) ve \(g(n)=n^3\) olmak üzere \(t(n) \in \alpha(g(n))\) olarak kabul edilir. Çünkü \(c=1\) ve \(n_0=10\) değerleri için \(2^n \ge 1 \cdot n^3\), \(n \ge n_0=10\) sağlanır. Bunun aksine, \(n=5000n^2\) ve \(g(n)=n^3\) için \(t(n) \in \alpha(g(n))\) olarak kabul edilir, Çünkü \(c=5001\) ve \(n_0=1\) değerleri için \(5000n^2 < 5001n^3\) olacaktır.
Asimptotik alt sınırı ifadesinde dikkat edilmesi gereken bir nokta c sabitinin n sayısıyla kıyaslanamayacak kadar küçük bir sayı olmasıdır. n sayısı istenildiği kadar büyütülebilir.

---

Aşağıdaki ifadelerden hangisi ya da hangileri yanlıştır?
(I) \(5^{n+1000} \in \alpha(6^n)\)
(II) \(\frac{\sqrt{n}}{100} \in \alpha(\log n)\)
(III) \((\log^3 \sqrt{n})^2 \in \alpha(\log 3n)\)

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

Cevap: A Yalnız I

Çözüm:
19.sorudaki mantığı kullanarak:
I) \(5^{n+1000}, 5^n, 5^{1000}\) şeklinde yazılabilir katsayı önemsiz olduğundan: \(5^n < 6^n\). Yanlış.
II) Sonsuzda \(n > \log n\). Doğru.
III) Katsayı sildiğimizde \((\log n)^2 > \log n\). Doğru.
Bilgisayar Olimpiyatı 2017, 1. Aşama, Soru 21

[1 ... N] aralığındaki tamsayılarla oynanan bir oyun şu şekilde tanımlanıyor: Sayılar artan sırada olacak şekilde yan yana dizilir. İlk sayı olan 1'den başlayarak bu dizilimdeki sayılar birer atlanarak silinir. Dizinin dairesel olduğu düşünülerek dizi sonuna gelindiğinde koruma/silme işlemine dizinin başından itibaren geriye kalan sayılarla devam edilir. Bu oyun, geriye sadece bir sayı kalana kadar oynanır. İlk geçiş, 1'in korunmasıyla başlar.
Örnek:
N = 7 için dizimiz 1 2 3 4 5 6 7 şeklindedir.
İlk geçiş: 1 korunur, 2 silinir, 3 korunur, 4 silinir, 5 korunur, 6 silinir, 7 korunur.
(Dizinin son hali: 13 57)
İkinci geçiş: 1 silinir, 3 korunur, 5 silinir, 7 korunur.
(Dizinin son hali: 37)
Üçüncü geçiş: 3 silinir, 7 korunur.
(Dizinin son hali: 7)
Geriye kalan son sayı 7'dir.
Buna göre oyunda N = 160 için geriye kalan son sayı kaçtır?

Şıklar:
A) 65 | B) 83 | C) 101 | D) 129 | E) 157

Cevap: A 65

Çözüm:
Her geçiş durumunu ve ilk sayısının korunma durumunu takip edelim:
- İlk seferde bütün çift sayılar silinir. Son sayı da silindiğinden sonraki adımın ilk sayısı korunur. Dizi: 1, 3, ..., 159
- Aynı şekilde mod 4'te 3 olanlar silinir. Sonraki adım korunarak başlar.
Dizi: 1, 5, ..., 157
- Sonra mod 8'de 5 olanlar silinir. Dizi: 1, 9, ..., 153
- mod x'te x+1 olanlar silinir ta ki dizinin eleman sayısı tek olsun. Diziler: 1, 17, ..., 1, 33, ..., (tek sayıda)
- Sonra ilk sayının korunma durumu değişir.
Diziler: 1, 33, 65, 97, 129(korunur) → 1, 65, 129(silinir) → 65
Bilgisayar Olimpiyatı 2017, 1. Aşama, Soru 22

## [22 – 24] Sorular için Açıklama
Ülke politikası olarak faizin düşürülmesi hedeflenmektedir. Ancak faizi düşürebilmek için onunla bağlantılı pek çok parametrenin arasındaki dengenin de gözetilmesi gerekmektedir. Bu parametreler arasındaki ilişkiyi açıklayacak olursak:
- Faiz düşerse dolar yükselmektedir.
- Dolar yükselirse büyüme azalmaktadır.
- Büyüme azalırsa alım gücü azalmaktadır.
- Alım gücü azalırsa faiz arttırılmaktadır.

---

Tanımlanan ilişkilerden yola çıkarak ikili sepet oluşturulmak istenirse hangi parametreler arasındaki ko-relasyon (ilişki) doğru orantılıdır?

Şıklar:
A) Faiz - Dolar | B) Büyüme - Faiz | C) Dolar - Alım gücü | D) Dolar - Büyüme | E) Hiçbiri

Cevap: B Büyüme - Faiz

Çözüm:
Her parametrenin yanına artar azalır yazarsak aynı olan herhangi bir ikili cevap olur:
• Faiz — azalır → Dolar — artar → Büyüme — azalır → Alım — azalır.
Büyüme ve Faiz aynı artma-azalma değerine sahiptir.
Bilgisayar Olimpiyatı 2017, 1. Aşama, Soru 23

## [22 – 24] Sorular için Açıklama
Ülke politikası olarak faizin düşürülmesi hedeflenmektedir. Ancak faizi düşürebilmek için onunla bağlantılı pek çok parametrenin arasındaki dengenin de gözetilmesi gerekmektedir. Bu parametreler arasındaki ilişkiyi açıklayacak olursak:
- Faiz düşerse dolar yükselmektedir.
- Dolar yükselirse büyüme azalmaktadır.
- Büyüme azalırsa alım gücü azalmaktadır.
- Alım gücü azalırsa faiz arttırılmaktadır.

---

Tanımlanan ilişkilere aşağıdaki iki ilişkinin de eklendiğini düşünelim.
- Alım gücü azalırsa altın fiyatları artmaktadır.
- TL değeri azalırsa faiz artmaktadır.
Buna göre altın fiyatlarını düşürmek için ülkenin nasıl bir karar alması gerekmektedir?

Şıklar:
A) Faizi düşürmeli | B) Faizi sabit tutmalı | C) TL değerini artırmalı | D) TL değerini sabit tutmalı | E) Hiçbiri

Cevap: A Faizi düşürmeli

Çözüm:
4. ilişkiye bakacak olursak:
• ‘Alım gücü’ ile ‘Faiz’ ters orantılıdır.
• Aynı şekilde ‘Alım gücü’ ile ‘altın fiyatları’ da ters orantılıdır.
- Yani altın fiyatları ile faiz doğru orantılıdır.
O zaman altın fiyatlarını düşürmek için faizi düşürmek yeterlidir.
Bilgisayar Olimpiyatı 2017, 1. Aşama, Soru 24

## [22 – 24] Sorular için Açıklama
Ülke politikası olarak faizin düşürülmesi hedeflenmektedir. Ancak faizi düşürebilmek için onunla bağlantılı pek çok parametrenin arasındaki dengenin de gözetilmesi gerekmektedir. Bu parametreler arasındaki ilişkiyi açıklayacak olursak:
- Faiz düşerse dolar yükselmektedir.
- Dolar yükselirse büyüme azalmaktadır.
- Büyüme azalırsa alım gücü azalmaktadır.
- Alım gücü azalırsa faiz arttırılmaktadır.

---

Tanımlanan ilişkilere aşağıdaki ilişkilerin de eklendiğini düşünelim.

- Alım gücü azalırsa altın fiyatlari artmaktadır.
- TL değeri azalırsa faiz artmaktadı.
- Faiz düşerse ve büyüme artarsa borsa endeksi artmaktadır.
- Borsa endeksi ve TL değeri artarsa o zaman alım gücü artmaktadır.
Buna göre ülkedeki alım gücünün en yüksek haline ulaşabilmesi için ne yapılmalıdır?

Şıklar:
A) TL değeri arttırılıp faiz düşürülmeli | B) Faiz arttırılıp dolar düşürülmeli | C) Borsa arttırılıp dolar arttırılmalı

Cevap: A TL değeri arttırılıp faiz düşürülmeli

Çözüm:
Ülkedeki alım gücünü en yüksek haline getirebilmek için alım gücünü artıran her bağımsız durum birlikte gerçekleşmelidir.
• Faiz ile alım gücü ters orantılı olduğundan faizi azaltmak alım gücünü artırır ve aynı zamanda borsa endeksini de artırır.
• Borsa endeksi arttığından dolayı TL'yi de artırmak alım gücünün artışına sebep olur.
Diğer bütün olumlu etken bu ikisine bağlanabilir.
Bilgisayar Olimpiyatı 2017, 1. Aşama, Soru 25

## [25 – 26] Sorular için Açıklama
**Tanım 1:** a ve b gibi iki tamsayıyı tam olarak bölen en büyük tamsayıya Ortak Bölenlerin En Büyüğü (OBEB) denir. OBEB (a, b) hesabı için aşağıda verilen bilgilerden yararlanılır:
- Eğer \(a = 0\) ise OBEB(0, b) = b veya \(b = 0\) ise OBEB(a, 0) = a olur.
- a sayısı bölüm ve kalan formunda modüler aritmetik formunda yazılır.
\((a = q \cdot b + r; 0 \le r < b)\) (\(q: bölüm, r: kalan\)) a \(\in\) r (mod b)
Örnek: \(a = 6, b = 4\) olsun. \(6 = 1 \cdot 4 + 2\) olduğu için \(6 \equiv 2\) (mod 4)
- \(a = r_0, b = r_1, r = r_2\) olsun.
\[r_0 = q_1 \cdot r_1 + r_2 \quad 0 \le r_2 < r_1\]
\[r_1 = q_2 \cdot r_2 + r_3 \quad 0 \le r_3 < r_2\]
\[r_2 = q_3 \cdot r_3 + r_4 \quad 0 \le r_4 < r_3\]
..................................................
\[r_{n-2} = q_{n-1} \cdot r_{n-1} + r_n \quad 0 \le r_n < r_{n-1}\]
\[r_{n-1} = q_n \cdot r_n + O\]
\[OBEB(a, b) = OBEB(r_0, r_1) = OBEB(r_1, r_2) = OBEB(r_2, r_3) = \dots = OBEB(r_{n-1}, r_n) = OBEB(r_n, O) = r_n\]
Örnek: OBEB(28, 16) = ?
\[28 = 1 \cdot 16 + 12\]
\[16 = 1 \cdot 12 + 4\]
\[12 = 3 \cdot 4 + O\]
\[OBEB(28, 16) = OBEB(16, 12) = OBEB(12, 4) = OBEB(4, O) = 4\]
**Tanım 2:** OBEB(a, b) = (t.a + s.b) formunda yazmaya "Cebirin Temel Teoremi" adı verilir. Eğer OBEB(a, b) = 1 yani a ile b aralarında asal ise \(b^{-1} \equiv s \pmod{a}\) 'dir. Hatırlatma: \(b \cdot b^{-1} \equiv 1 \pmod{a}\).
Eğer OBEB(a, b) \(\neq 1\) ise \(b-1 \equiv 0 \pmod{a}\)

---

OBEB(14820, 8320) aşağıdakilerden hangisine eşittir?

Şıklar:
A) 1 | B) 2 | C) 20 | D) 260 | E) 280

Cevap: D 260

Çözüm:
OBEB(14820, 8320) değerini örnekte olduğu gibi her \(r_{i \in \mathbb{N}}\) gösterelim:
- \(14380 = 1 \cdot 8320 + 6500\)
- \(8320 = 1 \cdot 6500 + 1820\)
- \(6500 = 3 \cdot 1820 + 1040\)
- \(1820 = 1 \cdot 1040 + 780\)
- \(1040 = 1 \cdot 780 + 260\)
- \(780 = 3 \cdot 260 + O\)
Bilgisayar Olimpiyatı 2017, 1. Aşama, Soru 26

## [25 – 26] Sorular için Açıklama
**Tanım 1:** a ve b gibi iki tamsayıyı tam olarak bölen en büyük tamsayıya Ortak Bölenlerin En Büyüğü (OBEB) denir. OBEB (a, b) hesabı için aşağıda verilen bilgilerden yararlanılır:
- Eğer \(a = 0\) ise OBEB(0, b) = b veya \(b = 0\) ise OBEB(a, 0) = a olur.
- a sayısı bölüm ve kalan formunda modüler aritmetik formunda yazılır.
\((a = q \cdot b + r; 0 \le r < b)\) (\(q: bölüm, r: kalan\)) a \(\in\) r (mod b)
Örnek: \(a = 6, b = 4\) olsun. \(6 = 1 \cdot 4 + 2\) olduğu için \(6 \equiv 2\) (mod 4)
- \(a = r_0, b = r_1, r = r_2\) olsun.
\[r_0 = q_1 \cdot r_1 + r_2 \quad 0 \le r_2 < r_1\]
\[r_1 = q_2 \cdot r_2 + r_3 \quad 0 \le r_3 < r_2\]
\[r_2 = q_3 \cdot r_3 + r_4 \quad 0 \le r_4 < r_3\]
..................................................
\[r_{n-2} = q_{n-1} \cdot r_{n-1} + r_n \quad 0 \le r_n < r_{n-1}\]
\[r_{n-1} = q_n \cdot r_n + O\]
\[OBEB(a, b) = OBEB(r_0, r_1) = OBEB(r_1, r_2) = OBEB(r_2, r_3) = \dots = OBEB(r_{n-1}, r_n) = OBEB(r_n, O) = r_n\]
Örnek: OBEB(28, 16) = ?
\[28 = 1 \cdot 16 + 12\]
\[16 = 1 \cdot 12 + 4\]
\[12 = 3 \cdot 4 + O\]
\[OBEB(28, 16) = OBEB(16, 12) = OBEB(12, 4) = OBEB(4, O) = 4\]
**Tanım 2:** OBEB(a, b) = (t.a + s.b) formunda yazmaya "Cebirin Temel Teoremi" adı verilir. Eğer OBEB(a, b) = 1 yani a ile b aralarında asal ise \(b^{-1} \equiv s \pmod{a}\) 'dir. Hatırlatma: \(b \cdot b^{-1} \equiv 1 \pmod{a}\).
Eğer OBEB(a, b) \(\neq 1\) ise \(b-1 \equiv 0 \pmod{a}\)

---

Aşağıdakilerden hangisi 55⁻¹ ≡ ? (mod 87) ve 12⁻¹ ≡ ? (mod 18) işlemlerinin çözüm kümesidir?

Şıklar:
A) {1, 6} | B) {-12, 19} | C) {Ø, 6} | D) {Ø, Ø} | E) {19, Ø}

Cevap: E {19, Ø}

Çözüm:
OBEB(a, b) = 1 ise b⁻¹ ≡ s (mod a) yani a=55, b=87 dersek OBEB(55, 87) = 1 olduğundan ilk ?' yerine s gelir. Aynı şekilde a=12, b=18 dersek OBEB(12, 18) = 6 ≠ 1 olduğundan ikinci ?' yerine Ø gelir. Çözüm kümemiz {s, Ø} şeklinde olacağını biliyoruz. Modda bölme yaparak s = 19 ve çözüm kümesinin {19, Ø} olduğunu bulabilirsiniz. Fakat soruda asıl istenen şey format olduğundan {s, Ø} formatına uyan tek şıkkın E olduğunu anlayıp 19 hesaplanmadan da geçilebilir.
Bilgisayar Olimpiyatı 2017, 1. Aşama, Soru 28

### [27 – 29] Sorular İçin Açıklama
Şifreleme Algoritması:
Şifrelenecek metin ve şifrelenmiş metin uzaylarının (mod 26)'da tanımlı olduğunu düşünelim. (mod 26) uzayı, elemanları aşağıdaki harflerin sayısal karşılığı olacak şekilde verilsin.
<table><tr><td>A</td><td>B</td><td>C</td><td>D</td><td>E</td><td>F</td><td>G</td><td>H</td><td>I</td><td>J</td><td>K</td><td>L</td><td>M</td></tr><tr><td>0</td><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>6</td><td>7</td><td>8</td><td>9</td><td>10</td><td>11</td><td>12</td></tr></table>
<table><tr><td>N</td><td>O</td><td>P</td><td>Q</td><td>R</td><td>S</td><td>T</td><td>U</td><td>V</td><td>W</td><td>X</td><td>Y</td><td>Z</td></tr><tr><td>13</td><td>14</td><td>15</td><td>16</td><td>17</td><td>18</td><td>19</td><td>20</td><td>21</td><td>22</td><td>23</td><td>24</td><td>25</td></tr></table>
Şifreleme işleminde kullanılacak anahtar kümemiz de (mod 26)'da tanımlı K = (a, b) olsun. b değeri (mod 26)'da tüm değerleri alabilirken, a ise sadece OBEB(a, 26) = 1 sonucunu sağlayan değerleri alabilmektedir. x; şifrelenecek değer, y de şifreleme sonucunda elde ettiğimiz değer olsun.
Şifreleme kuralımız: y = e<sub>k</sub>(x) ≡ (a·x + b) (mod 26).
Şifre çözme kuralımız ise: x = d<sub>k</sub>(y) ≡ a<sup>-1</sup>·(y - b) (mod 26).
Örneğin; Şifrelenecek metin "AD" olsun. Yukarıda verilen koşullara bağlı olarak K = (7, 3) olsun. A'nın sayısal karşılığı O, D'nin sayısal karşılığı 3'tür. Bu durumda Şifreli metin şifreleme kuralına bağlı olarak:
\[y_1 = e_k(x) \equiv (a \cdot x + b) \pmod{26}, y_1 = e_k(A) = e_k(O) = (7 \cdot O + 3) \equiv 3 \pmod{26} (3 = D),\]
\[y_2 = e_k(x_2) \equiv (a \cdot x_2 + b) \pmod{26}, y_2 = e_k(D) = e_k(S) = (7 \cdot 3 + 3) \equiv 24 \pmod{26} (24 = Y) \text{ çıkar.}\]
Böylece Şifreli metin: "DY" olarak hesaplanmış olur. Şifreli metni alan kişi de anahtar kümesine sahiptir ve bu anahtar kümesini kullanarak şifre çözme kuralına bağlı olarak "AD" elde edecektir. 7-1 ≡ 15 (mod 26).
\[x_1 = d_k(y_1) \equiv a^{-1} \cdot (y_1 - b) \pmod{26}, x_1 = d_k(D) = d_k(3) = 7^{-1} \cdot (3 - 3) \pmod{26} = 15 \cdot O \equiv O \pmod{26} (O = A),\]
\[x_2 = d_k(y_2) \equiv a^{-1} \cdot (y_2 - b) \pmod{26}, x_2 = d_k(Y) = d_k(24) = 7^{-1} \cdot (24 - 3) \pmod{26} = 15 \cdot 21 \equiv 3 \pmod{26} (3 = D).\]

---

Çalışma uzayımız (mod 88) olarak tanımlanacak olur ise anahtar uzayı boyutumuz aşağıdakilerden han-gisi olur?

Şıklar:
A) 352O | B) 7744 | C) 160O | D) 616O | E) 490O

Cevap: A 352O

Çözüm:
Önceki soruda belirttiğim sebepten dolayı a ile 88 in aralarında asal olması gerekir. b'nin 88 farklı sayı alabileceğini biliyoruz. Bizim aradığımız şey olan a'nın kaç farklı sayı değeri alabileceği ise 88'den küçük 88 ile aralarında asal sayıların sayısıdır. Yani Ø(88). Önceki hesaplama yöntemlerine bakarsak, 88'in asal çarpanları 2 ve 11 olduğundan Ø(88) = 88. (1/2). (1O/11) = 40 olur. Cevap ise 88. 40 = 352O olur.