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

## [11-13 soruları için açıklama]
Ali, Bartu, Can ve Deniz top sektirme oyunu oynamışlar. Oyunun sonucunda bir tanesi birinci, bir tanesi ikinci, bir tanesi üçüncü, bir tanesi de dördüncü olmuş. Oyun bittikten sonra yanlarına gelen arkadaşları Enes oyunu kimin kaçıncı bitirdiğini merak etmiş. Ali, Bartu ve Can'ın herbiri Enes'e oyunun sonucu hakkında bir tanesi doğru ve bir tanesi yanlış olan iki bilgi vermiş.
Ali, "Can birinci oldu, Bartu ikinci oldu" demiş.
Bartu, "Can ikinci oldu, Deniz üçüncü oldu" demiş.
Can, "Deniz dördüncü oldu, Ali ikinci oldu" demiş.
Üç arkadaşının kendisine bir doğru ve bir yanlış bilgi verdiğini bilen Enes oyunu kimin kaçıncı sırada bitirdiğini bulmaya çalışmış.

---

Oyun sonunda kim ikinci olmuştur?

Şıklar:
A) Ali | B) Bartu | C) Can | D) Deniz | E) Kesin cevap vermek için yeterli veri yoktur

Cevap: A Ali

Çözüm:
Ali'nin söylediği iki önermeyi sırasıyla \(a_1\) ve \(a_2\) olarak isimlendirelim. Benzer şekilde Bartu ve Can'ın söylediği önermeleri de \(b_1, b_2, c_1, c_2\) olarak isimlendirelim. Bir önerme doğru ise değeri 1, yanlış ise değeri 0 olsun. Örneğin Can gerçekten birinci ise \(a_1 = 1\) ve \(b_1 = 0\) olacaktır.
Aşağıdaki eşitliğin sol tarafı Ali'nin söylediği iki önermenin ikisinin de doğru yada ikisinin de yanlış olduğu durumlarda 0, iki önermenin bir tanesinin doğru ve bir tanesinin yanlış olduğu durumda ise 1 yapmaktadır. Ali'nin söylediği önermelerden bir tanesi doğru bir tanesi yanlış olduğuna göre bu eşitlik sağlanmaktadır.
\[a_1 + a_2 - 2 a_1 a_2 = 1\]
Bartu ve Can'ın söylediği önermelerden bir tanesi doğru ve bir tanesi yanlış olduğundan aşağıdaki eşitlikler de sağlanır.
\[b_1 + b_2 - 2 b_1 b_2 = 1\]
\[c_1 + c_2 - 2 c_1 c_2 = 1\]
Bunlara ek olarak \(a_1\) ve \(b_1\) birbiriyle çeliştiğinden \(a_1 b_1 = 0\) eşitliği, \(a_2\) ve \(b_1\) birbiriyle çeliştiğinden \(a_{2} b_{1} = 0\) eşitliği, \(b_{2}\) ve \(c_{1}\) birbiriyle çeliştiğinden \(b_{2} c_{1} = 0\) eşitliği, \(a_{2}\) ve \(c_{2}\) birbiriyle çeliştiğinden \(a_{2} c_{2} = 0\) eşitliği ve \(b_{1}\) ve \(c_{2}\) birbiriyle çeliştiğinden \(b_{1} c_{2} = 0\) eşitliği sağlanır.
\(b_1 = 1\) olduğunu (Can'ın ikinci olduğunu) varsayalım. Hem \(a_1 b_1 = 0\), hem de \(a_2 b_1 = 0\) olduğuna göre \(a_1 = a_2 = 0\)'dır. Ancak bu \(a_1 + a_2 - 2 a_1 a_2 = 1\) eşitliğiyle çelişmektedir. Öyleyse \(b_1 = 0\)'dır. Bartu'nun söylediği önermelerden tam olarak bir tanesi doğru olduğundan \(b_2 = 1\)'dir yani Deniz üçüncü olmuştur.
\(b_2 c_1 = 0\) eşitliğinin sağlandığı bilinmektedir. \(b_2 = 1\) olduğu için \(c_1 = 0\)'dır ve dolayısıyla \(c_2 = 1\)'dir. Yani Ali ikinci olmuştur.
\(a_2 c_2 = 0\) eşitliğinin sağlandığı bilinmekte. \(c_2 = 1\) olduğu için \(a_2 = 0\)'dır ve dolayısıyla \(a_1 = 1\)'dir. Yani Can birinci olmuştur.
Can birinci, Ali ikinci, Deniz üçüncü olduğuna göre Bartu dördüncü olmuştur.
Bilgisayar Olimpiyatı 2022, 1. Aşama, Soru 13

## [11-13 soruları için açıklama]
Ali, Bartu, Can ve Deniz top sektirme oyunu oynamışlar. Oyunun sonucunda bir tanesi birinci, bir tanesi ikinci, bir tanesi üçüncü, bir tanesi de dördüncü olmuş. Oyun bittikten sonra yanlarına gelen arkadaşları Enes oyunu kimin kaçıncı bitirdiğini merak etmiş. Ali, Bartu ve Can'ın herbiri Enes'e oyunun sonucu hakkında bir tanesi doğru ve bir tanesi yanlış olan iki bilgi vermiş.
Ali, "Can birinci oldu, Bartu ikinci oldu" demiş.
Bartu, "Can ikinci oldu, Deniz üçüncü oldu" demiş.
Can, "Deniz dördüncü oldu, Ali ikinci oldu" demiş.
Üç arkadaşının kendisine bir doğru ve bir yanlış bilgi verdiğini bilen Enes oyunu kimin kaçıncı sırada bitirdiğini bulmaya çalışmış.

---

Oyun sonunda kim dördüncü olmuştur?

Şıklar:
A) Ali | B) Bartu | C) Can | D) Deniz | E) Kesin cevap vermek için yeterli veri yoktur

Cevap: B Bartu

Çözüm:
Ali'nin söylediği iki önermeyi sırasıyla \(a_1\) ve \(a_2\) olarak isimlendirelim. Benzer şekilde Bartu ve Can'ın söylediği önermeleri de \(b_1, b_2, c_1, c_2\) olarak isimlendirelim. Bir önerme doğru ise değeri 1, yanlış ise değeri 0 olsun. Örneğin Can gerçekten birinci ise \(a_1 = 1\) ve \(b_1 = 0\) olacaktır.
Aşağıdaki eşitliğin sol tarafı Ali'nin söylediği iki önermenin ikisinin de doğru yada ikisinin de yanlış olduğu durumlarda 0, iki önermenin bir tanesinin doğru ve bir tanesinin yanlış olduğu durumda ise 1 yapmaktadır. Ali'nin söylediği önermelerden bir tanesi doğru bir tanesi yanlış olduğuna göre bu eşitlik sağlanmaktadır.
\[a_1 + a_2 - 2 a_1 a_2 = 1\]
Bartu ve Can'ın söylediği önermelerden bir tanesi doğru ve bir tanesi yanlış olduğundan aşağıdaki eşitlikler de sağlanır.
\[b_1 + b_2 - 2 b_1 b_2 = 1\]
\[c_1 + c_2 - 2 c_1 c_2 = 1\]
Bunlara ek olarak \(a_1\) ve \(b_1\) birbiriyle çeliştiğinden \(a_1 b_1 = 0\) eşitliği, \(a_2\) ve \(b_1\) birbiriyle çeliştiğinden \(a_{2} b_{1} = 0\) eşitliği, \(b_{2}\) ve \(c_{1}\) birbiriyle çeliştiğinden \(b_{2} c_{1} = 0\) eşitliği, \(a_{2}\) ve \(c_{2}\) birbiriyle çeliştiğinden \(a_{2} c_{2} = 0\) eşitliği ve \(b_{1}\) ve \(c_{2}\) birbiriyle çeliştiğinden \(b_{1} c_{2} = 0\) eşitliği sağlanır.
\(b_1 = 1\) olduğunu (Can'ın ikinci olduğunu) varsayalım. Hem \(a_1 b_1 = 0\), hem de \(a_2 b_1 = 0\) olduğuna göre \(a_1 = a_2 = 0\)'dır. Ancak bu \(a_1 + a_2 - 2 a_1 a_2 = 1\) eşitliğiyle çelişmektedir. Öyleyse \(b_1 = 0\)'dır. Bartu'nun söylediği önermelerden tam olarak bir tanesi doğru olduğundan \(b_2 = 1\)'dir yani Deniz üçüncü olmuştur.
\(b_2 c_1 = 0\) eşitliğinin sağlandığı bilinmektedir. \(b_2 = 1\) olduğu için \(c_1 = 0\)'dır ve dolayısıyla \(c_2 = 1\)'dir. Yani Ali ikinci olmuştur.
\(a_2 c_2 = 0\) eşitliğinin sağlandığı bilinmekte. \(c_2 = 1\) olduğu için \(a_2 = 0\)'dır ve dolayısıyla \(a_1 = 1\)'dir. Yani Can birinci olmuştur.
Can birinci, Ali ikinci, Deniz üçüncü olduğuna göre Bartu dördüncü olmuştur.
Bilgisayar Olimpiyatı 2022, 1. Aşama, Soru 14

[14-15 soruları için açıklama]
9 satır ve 9 sütünden oluşan 9 × 9 = 81 kareli bir satranç tahtası verilmiş olsun. Bu satranç tahtasının her bir karesini \(x \in \{0, 1, 2, ..., 8\}\) ve \(y \in \{0, 1, 2, ..., 8\}\) olmak üzere bir \((x, y)\) ikilisi ile gösteriyoruz.
Satranç tahtası üzerinde verilen \((x_1, y_1)\) ve \((x_2, y_2)\) kareleri arasındaki Manhattan uzaklığını \(|x_1 - x_2| + |y_1 - y_2|\) olarak tanımlıyoruz. Örneğin, (3,1) ve (2,4) kareleri arasındaki Manhattan uzaklığı \(|3 - 2| + |1 - 4| = 4\)'tür.
Satranç tahtası üzerinde bulunan bir at bir adımda bulunduğu kareden bir yönde (yukarı, aşağı, sağa veya sola) 2 birim ve o yöne dik bir yönde 1 birim uzaklıktaki bir kareye gidebilmektedir. Örneğin (4,6) karesinde bulunan bir at bir adımda (2,5), (2,7), (3,4), (3,8), (5,4), (5,8), (6,5) ve (6,7) karelerinden herhangi birine gidebilir. (0,0) karesinde bulunan bir at ise sadece (1,2) ve (2,1) karelerine gidebilir.
Satranç tahtası üzerinde sadece bir at olsun ve bu atın başlangıç karesi (2, 6) olsun.

---

At başlangıç karesine Manhattan uzaklığı 1 olan bir kareye en az kaç adımda gidebilir?

Şıklar:
A) 1 | B) 2 | C) 3 | D) 4 | E) 5

Cevap: C 3

Çözüm:
Başlangıç karesine Manhattan uzaklığı 1 olan 4 tane kare vardır ve bunlar başlangıç karesinin sağındaki, solundaki, altındaki ve üstündeki karelerdir. Bu soruda bu karelerden hiçbirine atın 2 adımda ulaşamadığının ancak başlangıç karesinin çaprazındaki her kareye 2 adımda ulaşabildiğinin gözlemlenmesi beklenmektedir. Bu noktalardan ulaşılmak istenen noktalara ise ilave bir adımla ulaşılabilir. Dolayısıyla başlangıç noktasına Manhattan uzaklığı 1 olan bütün noktalara 3 adımda ulaşılabilir.
Bilgisayar Olimpiyatı 2022, 1. Aşama, Soru 15

[14-15 soruları için açıklama]
9 satır ve 9 sütünden oluşan 9 × 9 = 81 kareli bir satranç tahtası verilmiş olsun. Bu satranç tahtasının her bir karesini \(x \in \{0, 1, 2, ..., 8\}\) ve \(y \in \{0, 1, 2, ..., 8\}\) olmak üzere bir \((x, y)\) ikilisi ile gösteriyoruz.
Satranç tahtası üzerinde verilen \((x_1, y_1)\) ve \((x_2, y_2)\) kareleri arasındaki Manhattan uzaklığını \(|x_1 - x_2| + |y_1 - y_2|\) olarak tanımlıyoruz. Örneğin, (3,1) ve (2,4) kareleri arasındaki Manhattan uzaklığı \(|3 - 2| + |1 - 4| = 4\)'tür.
Satranç tahtası üzerinde bulunan bir at bir adımda bulunduğu kareden bir yönde (yukarı, aşağı, sağa veya sola) 2 birim ve o yöne dik bir yönde 1 birim uzaklıktaki bir kareye gidebilmektedir. Örneğin (4,6) karesinde bulunan bir at bir adımda (2,5), (2,7), (3,4), (3,8), (5,4), (5,8), (6,5) ve (6,7) karelerinden herhangi birine gidebilir. (0,0) karesinde bulunan bir at ise sadece (1,2) ve (2,1) karelerine gidebilir.
Satranç tahtası üzerinde sadece bir at olsun ve bu atın başlangıç karesi (2, 6) olsun.

---

At satranç tahtasının köşe karelerinden birine ((0,0), (0,8), (8,0), (8,8)) en az kaç adımda ulaşabilir?

Şıklar:
A) 1 | B) 2 | C) 3 | D) 4 | E) 5

Cevap: D 4

Çözüm:
(0,0) ya da (8,0) karelerine 3 adımda ulaşılabilmesi için her adımda aşağı yönde iki birim gidilmesi gerekmektedir. Bu durumda her adımda sola veya sağa bir birim gidilecektir. Her adımda sola ya da sağa bir birim giderek 3 adımda sola 2 birim ya da sağa 6 birim gitmek mümkün değildir. Bu yüzden bu karelere 3 adımda ulaşılamaz.
(8,8) karesine 3 adımda gitmek için her adımda sağa 2 birim gitmek gerekmektedir. Bu durumda her adımda yukarı ve aşağı bir birim gidilecektir. Her adımda yukarı ya da aşağı bir birim giderek 3 adımda yukarı 2 birim gitmek mümkün değildir. Bu yüzden bu kAREYE 3 adımda ulaşılamaz.
(0,8) karesine 1 adımda ulaşılabilecek 2 kare vardır ve bunlar (1,6) ve (2,7) kareleridir. Bu iki karenin de başlangıç karesine Manhattan uzaklığı 1 olduğu için bu karelere en az 3 adımda ulaşılabileceğini iki önceki sorunun çözümünden biliyoruz. Öyleyse (0,8) karesine 4 adımda ulaşılabilir. Bu yüzden cevap 4'tür.
Bilgisayar Olimpiyatı 2022, 1. Aşama, Soru 16

[16-20 soruları için açıklama]
Bir çember şeklinde dizilmiş N tane kutu bulunmaktadır ve bu kutular saat yönünde 0'dan N-1'e numaralandırılmışlardır. Her bir kutunun "üst" kutusu saat yönü tersi yönünde hemen yanındaki kutu olarak tanımlanmıştır. Her bir kutuda bir karakter (tek bir rakam ya da küçük ya da büyük bir harf) bulunmaktadır. Bu kutularda o anda var olan karakterlere göre bir kural kümesindeki kuralları tüm kutular için eş zamanlı uygulayarak kutulardaki karakterleri başka karakterler ile değiştirmemiz mümkün olmaktadır. Bu kuralların genel ifadesi şu şekildedir:
\[
\ddot{U}_t K_t \rightarrow K_{t+1}
\]
Burada \(\ddot{U}\), üst kutudaki karakteri ve K de o kutudaki karakteri simgeleyen genel değişkenlerdir. Kuralın sol tarafı, t anında kutulardaki değerler ile eşleşiyorsa t+1 anında o kutudaki değer kuralın sağında gösterilen karaktere dönüşmüş olur. Örnek olarak \(\{b^* \rightarrow b, a^* \rightarrow *\}\) kural kümesi verildiğinde (*, herhangi bir karakter anlamına gelen joker semboldür), başlangıçta kutulardaki karakterlerin 0 numaralı kutudan 4 numaralı kutuya bbbaa olduğu 5 kutu içeren çemberde bir sonraki adımda kutulardaki değerler bbbba olacaktır ve sonra da bbbbb olup sonraki bütün adımlarda bu şekilde kalacaktır.

---

4 kutu içeren bir çember için {ba → b, bb → a, a* → *} kuralları verildiğinde ve başlangıç (t=0) anında kutulardaki karakterler baa aldığında, 5. adım sonunda yani t=5'te kutulardaki karakterler ne olur?

Şıklar:
A) baaa | B) aaab | C) bbbb | D) aaaa | E) baba

Cevap: D aaaa

Çözüm:
Sırayla kuralları uyguladığımızda baaa → bbaa → baba → bbbb → aaaa → aaaa elde ederiz.
Bilgisayar Olimpiyatı 2022, 1. Aşama, Soru 17

[16-20 soruları için açıklama]
Bir çember şeklinde dizilmiş N tane kutu bulunmaktadır ve bu kutular saat yönünde 0'dan N-1'e numaralandırılmışlardır. Her bir kutunun "üst" kutusu saat yönü tersi yönünde hemen yanındaki kutu olarak tanımlanmıştır. Her bir kutuda bir karakter (tek bir rakam ya da küçük ya da büyük bir harf) bulunmaktadır. Bu kutularda o anda var olan karakterlere göre bir kural kümesindeki kuralları tüm kutular için eş zamanlı uygulayarak kutulardaki karakterleri başka karakterler ile değiştirmemiz mümkün olmaktadır. Bu kuralların genel ifadesi şu şekildedir:
\[
\ddot{U}_t K_t \rightarrow K_{t+1}
\]
Burada \(\ddot{U}\), üst kutudaki karakteri ve K de o kutudaki karakteri simgeleyen genel değişkenlerdir. Kuralın sol tarafı, t anında kutulardaki değerler ile eşleşiyorsa t+1 anında o kutudaki değer kuralın sağında gösterilen karaktere dönüşmüş olur. Örnek olarak \(\{b^* \rightarrow b, a^* \rightarrow *\}\) kural kümesi verildiğinde (*, herhangi bir karakter anlamına gelen joker semboldür), başlangıçta kutulardaki karakterlerin 0 numaralı kutudan 4 numaralı kutuya bbbaa olduğu 5 kutu içeren çemberde bir sonraki adımda kutulardaki değerler bbbba olacaktır ve sonra da bbbbb olup sonraki bütün adımlarda bu şekilde kalacaktır.

---

N kutu içeren bir çember için {a* -> A, b* -> B, *A -> a, *B -> b} kuralları verilmiş olsun. 
Sadece a ve b karakterlerinden oluşan bir başlangıç durumunun tekrarlanması için en çok 
kaç adım gerekir?

Şıklar:
A) N 
B) N+1 
C) 2N – 1  
D) 2N 
E) Hiçbiri

Cevap: D 2N

Çözüm:
Kuralları incelediğimizde küçük harflerin saat yönünde bir kaydırılıp büyük harfe dönüştürüldüğü, büyük harflerin ise küçük harflere dönüştürüldüğü görülmektedir. Yani her 2 adımda bir küçük harf olarak başlangıç durumu bir kaydırılmış olmaktadır. N tane karakter içeren bir dizinin başlangıç durumuna gelmesi için N kere kayması gerekmektedir ve 2 adımda 1 kayma işlemi olduğundan toplam gereken adım sayısı 2N'dir.
Bilgisayar Olimpiyatı 2022, 1. Aşama, Soru 18

[16-20 soruları için açıklama]
Bir çember şeklinde dizilmiş N tane kutu bulunmaktadır ve bu kutular saat yönünde 0'dan N-1'e numaralandırılmışlardır. Her bir kutunun "üst" kutusu saat yönü tersi yönünde hemen yanındaki kutu olarak tanımlanmıştır. Her bir kutuda bir karakter (tek bir rakam ya da küçük ya da büyük bir harf) bulunmaktadır. Bu kutularda o anda var olan karakterlere göre bir kural kümesindeki kuralları tüm kutular için eş zamanlı uygulayarak kutulardaki karakterleri başka karakterler ile değiştirmemiz mümkün olmaktadır. Bu kuralların genel ifadesi şu şekildedir:
\[
\ddot{U}_t K_t \rightarrow K_{t+1}
\]
Burada \(\ddot{U}\), üst kutudaki karakteri ve K de o kutudaki karakteri simgeleyen genel değişkenlerdir. Kuralın sol tarafı, t anında kutulardaki değerler ile eşleşiyorsa t+1 anında o kutudaki değer kuralın sağında gösterilen karaktere dönüşmüş olur. Örnek olarak \(\{b^* \rightarrow b, a^* \rightarrow *\}\) kural kümesi verildiğinde (*, herhangi bir karakter anlamına gelen joker semboldür), başlangıçta kutulardaki karakterlerin 0 numaralı kutudan 4 numaralı kutuya bbbaa olduğu 5 kutu içeren çemberde bir sonraki adımda kutulardaki değerler bbbba olacaktır ve sonra da bbbbb olup sonraki bütün adımlarda bu şekilde kalacaktır.

---

5 kutu içeren bir çemberin kutularında yalnızca 0 ve 1 karakterleri bulunduğunu varsayalım. Verilen kural kümesi {00 → 0, 01 → 1, 10 → 1, 11 → 0} ise aşağıda verilen başlangıç durumlarından hangisi değişmeyen bir durumda kalınmasına neden olur?

Şıklar:
A) 01010 | B) 10011 | C) 11010 | D) 10111 | E) 11111

Cevap: E 11111

Çözüm:
Kutularda 1 ve 0 var ise sürekli değişim olacaktır. Ancak 00000 durumunda hiçbir değişikli olmadan 
kalınacaktır. Bu duruma başlangıç durumu 11111 ise 1 adımda erişilecektir.
Bilgisayar Olimpiyatı 2022, 1. Aşama, Soru 19

[16-20 soruları için açıklama]
Bir çember şeklinde dizilmiş N tane kutu bulunmaktadır ve bu kutular saat yönünde 0'dan N-1'e numaralandırılmışlardır. Her bir kutunun "üst" kutusu saat yönü tersi yönünde hemen yanındaki kutu olarak tanımlanmıştır. Her bir kutuda bir karakter (tek bir rakam ya da küçük ya da büyük bir harf) bulunmaktadır. Bu kutularda o anda var olan karakterlere göre bir kural kümesindeki kuralları tüm kutular için eş zamanlı uygulayarak kutulardaki karakterleri başka karakterler ile değiştirmemiz mümkün olmaktadır. Bu kuralların genel ifadesi şu şekildedir:
\[
\ddot{U}_t K_t \rightarrow K_{t+1}
\]
Burada \(\ddot{U}\), üst kutudaki karakteri ve K de o kutudaki karakteri simgeleyen genel değişkenlerdir. Kuralın sol tarafı, t anında kutulardaki değerler ile eşleşiyorsa t+1 anında o kutudaki değer kuralın sağında gösterilen karaktere dönüşmüş olur. Örnek olarak \(\{b^* \rightarrow b, a^* \rightarrow *\}\) kural kümesi verildiğinde (*, herhangi bir karakter anlamına gelen joker semboldür), başlangıçta kutulardaki karakterlerin 0 numaralı kutudan 4 numaralı kutuya bbbaa olduğu 5 kutu içeren çemberde bir sonraki adımda kutulardaki değerler bbbba olacaktır ve sonra da bbbbb olup sonraki bütün adımlarda bu şekilde kalacaktır.

---

6 kutu içeren bir çemberde bulunabilen karakterler a, b, ve c karakterleri olsun. 1000 adım sonrasındaki durum için aşağıdakilerden hangisi söylenebilir?

Şıklar:
A) Başlangıç durumu ile aynıdır | B) Başlangıç durumunun 1000 mod 6 kez saat yönünde dönmüş halidir | C) Değişmez bir durumdur | D) Daha önceki bir adımda oluşmuş bir durumdur | E) Hiçbiri

Cevap: D Daha önceki bir adımda oluşmuş bir durumdur

Çözüm:
6 kutu içeren bir çember için her kutuya en fazla 3 karakter gerebildiğinden  \( 3^{*}3^{*}3^{*}3^{*}3^{*}3 = 729 \)  farklı başlangıç durumu mümkündür ve değişmez bir durumla karşılaşılmadı ise t=1000 anındaki durum daha önce mutlaka karşılaşılmış olmak zorundadır. Eğer değişmez bir durumla karşılaşıldı ise de yine t=1000 anındaki durum t=999 anındaki durum ile aynıdır ve D şıkkındaki ifade yine doğrudur.
Bilgisayar Olimpiyatı 2022, 1. Aşama, Soru 20

[16-20 soruları için açıklama]
Bir çember şeklinde dizilmiş N tane kutu bulunmaktadır ve bu kutular saat yönünde 0'dan N-1'e numaralandırılmışlardır. Her bir kutunun "üst" kutusu saat yönü tersi yönünde hemen yanındaki kutu olarak tanımlanmıştır. Her bir kutuda bir karakter (tek bir rakam ya da küçük ya da büyük bir harf) bulunmaktadır. Bu kutularda o anda var olan karakterlere göre bir kural kümesindeki kuralları tüm kutular için eş zamanlı uygulayarak kutulardaki karakterleri başka karakterler ile değiştirmemiz mümkün olmaktadır. Bu kuralların genel ifadesi şu şekildedir:
\[
\ddot{U}_t K_t \rightarrow K_{t+1}
\]
Burada \(\ddot{U}\), üst kutudaki karakteri ve K de o kutudaki karakteri simgeleyen genel değişkenlerdir. Kuralın sol tarafı, t anında kutulardaki değerler ile eşleşiyorsa t+1 anında o kutudaki değer kuralın sağında gösterilen karaktere dönüşmüş olur. Örnek olarak \(\{b^* \rightarrow b, a^* \rightarrow *\}\) kural kümesi verildiğinde (*, herhangi bir karakter anlamına gelen joker semboldür), başlangıçta kutulardaki karakterlerin 0 numaralı kutudan 4 numaralı kutuya bbbaa olduğu 5 kutu içeren çemberde bir sonraki adımda kutulardaki değerler bbbba olacaktır ve sonra da bbbbb olup sonraki bütün adımlarda bu şekilde kalacaktır.

---

5 kutu içeren bir çember için  \( \{00 \rightarrow 1, 01 \rightarrow 1, 10 \rightarrow 0, 11 \rightarrow 1\} \)  kuralları verilmiş olsun. Aşağıdaki durumlardan hangisi başlangıç durumu dışında hiçbir zaman karşılaşılamayacak bir durumdur?

Şıklar:
A) 01111 | B) 11111 | C) 01010 | D) 10101 | E) 11110

Cevap: C 01010

Çözüm:
Kuralları incelediğimizde üst kutuda eğer 0 karakteri varsa o kutudaki karakterin 1 karakterine dönüştürüldüğünü, üst kutuda 1 varsa da kutudaki karakterin değişmediğini görürüz. Yani art arda iki tane 1 karakteri içermeyen bir durum kurallar uygulanması sonucu ulaşılamaz. D şıkkında sanki art arda 1 yokmuş gibi görünse de çember üzerinde ilk kutu ve son kutu ardışıktır ve ikisi de 1 içermektedir yani kurallar sonucu elde edilmiş olabilir. Ama C şıkkındaki durum ardışık 1 karakteri içermemektedir ve bir kural sonucu elde edilmesi mümkün değildir. C şıkkındaki durum ancak başlangıç durumunda karşılaşılabilir.
Bilgisayar Olimpiyatı 2022, 1. Aşama, Soru 21

[21-26 soruları için açıklama]
Genetik çalışmalar yürüten bir ekip DNA kodlamasının dilbilimi ile araştırılmasına yönelik hazırlık yapmaya başlıyor. Bildiğiniz üzere DNA’da alfabe olarak A, T, C, ve G bulunmaktadır. Araştırmayı yürüten ekip birbirini tekrar eden bazı dizilimler buluyor. Bunları ifade edebilmek için de kendi aralarında yeni bir dil formülü geliştiriyorlar. Buna göre;
- Her bir harf A, T, G, C’den birini ifade ediyor
- () : parantez içinde yer alan dizi tek bir harfmiş gibi davranır
- * : kendinden önceki harf/dizi 0 veya çok defa tekrar edilebilir
- + : kendinden önceki harf/dizi en az bir defa veya çok defa tekrar edilebilir
- ? : kendinden önceki harf/dizi 0 veya 1 defa tekrar edebilir
- . : bu karakterin olduğu yere alfabede yer alan herhangi bir harf gelebilir
• Her bir harf A, T, G, C’den birini ifade ediyorsun:
• () : parantez içinde yer alan dizi tek bir harfmiş gibi davanır
• * : kendinden önceki harf/dizi 0 veya çok defak tekrar edilebilir
• + : kendinden önceki harf/dizi en az bir defa veyaçok defa tekrar edilebilir
• ? : kendinden önceki harf/dizi 0 veya 1 defak tekrar edebilir
• . : bu karakterin olduğu yere alfabede yer alan herhange bir harf gelebilir
Örneğin, çıkarılan dil formülü A*(T.)+ olarak verilmişse, bazı geçerli diziler şunlardır:
ATG → A bir defa tekrar etmiş sonrasında (T.) ifadesi en az bir defa tekrar etmiş
AATCTC → A iki defa tekrarlamış, . yerine C gelmiş ve iki defa tekrar etmiş
TG → A sıfır defa tekrarlamış, . yerine G gelmiş ve bir defa tekrar etmiş
Fakat A dizisi geçerli bir dizi değildir, çünkü (T.) ifadesi en az bir defa yer almamaktadır. ATCC dizisi de ATC’den sonra T gelmeden C geldiği için geçerli değildir.

---

T+G(A+T)* dil formülü verildiyse, aşağıdaki ifadelerden hangisi geçerli bir diziyi belirtmemektedir?

Şıklar:
A) TGAAAAAT | B) TGAAT | C) TTGTGA | D) TTGATAT | E) TG

Cevap: C TTGTGA

Çözüm:
Verilen dil formülünde en başta en az bir tane T olmak zorundadır. Onu takip eden bir G bulunması mecburdur. Sonrasın (A+T) ifadesinden sıfır veya çok tane olması gerekir. Eğer bu ifadeden olacaksa A ile başlamalı ve T ile bitmelidir.
Bilgisayar Olimpiyatı 2022, 1. Aşama, Soru 23

I. A* ile A?A+ aynı dil formülüdür
II. (T.)+C formülünün ürettiği dizilerin tamamı tek sayıda harf içerecektir
III. (A*T)+GC* formülünün ürettiği diziler A ile başlayıp C ile bitmek zorundadır
Yukarıda verilen ifadeler için aşağıdakilerden hangisi doğrudur?

Şıklar:
A) I ve II yanlıştır | B) Sadece III doğrudur | C) I ve II doğrudur | D) Hepsi yanlıştır | E) I ve III yanlıştır

Cevap: E I ve III yanlıştır

Çözüm:
I ifadesinde A* boş küme olabilecekken A?A+ boş küme içeremeyecektir. II ifadesinde yer alan (T.) her zaman iki harf içermek zorundadır ve bu tekrarlı yapıda olsa da her seferinde çift sayıda harf içermiş olacaktır. C ile bitmesi nedeniyle de ürettiği tüm diziler tek sayıda harf içermelidir. III ifadesinde yer alan A ile başlama zorunluluğu doğru değildir, dizi T ile de başlayabilir.
Bilgisayar Olimpiyatı 2022, 1. Aşama, Soru 24

[24-26 soruları için ek açıklama]
Verilen dil formülü için çok büyük formüllerde zorluk yaşayan ekip görselleştirme kullanmaya karar verir. İşlerini kolaylaştırmak için durum makinesi tasarlamaya karar verirler. Bu makine durumlar ve durumlar arasındaki geçişlerden oluşmaktadır. Yeni gelen her bir harf bir durumdan başka bir duruma geçişi sağlayacaktır. Tabi ki başlangıç ve bitiş durumlarımız olmalıdır. Her bir durumu bir yuvarlak ile ifade eden ekip, bitiş durumlarını iki yuvarlak ile göstermeye karar verirler. Örneğin A+(TC)* dili için aşağıdaki durum makinesi oluşmalıdır:
[GÖRSEL]
Dil formülümüzde (TC) ifadesi * ile verildiğinden 1 ve 3 numaraları durumlarımız bitiş durumlarıdır. Makine başlangıç durumu kalın ok ile gösterilmektedir, yukarıda verilen örnekte boşluktan 0 durumuna giden ok olarak verilmiştir. Başlangıçta hiç harf yokken, A gelince 1 numaralı duruma geçiş yaparız. A'dan birçok defa gelebileceği için 1 durumundayken A geldiğinde tekrar aynı duruma geçiş yapmalıyız. (TC) gelmezse 1 numaralı durum bitiş durumumuz olabilir, ancak T harfi gelirse 2 numaralı duruma geçiş yapıp mutlaka C gelmesini beklemeliyiz. T'yi takip eden C harfi geldiğinde 3 numaralı duruma geçiş yapabiliriz. 3 numaralı durum da bitiş durumumuz olacaktır ve (TC) ifadesinin birden çok gelmesine müsaade etmektedir.

---

(T+C)*G(A+T)* dili verildiğinde, aşağıdaki seçeneklerden hangisi durum makinesi olarak çıkarılabilir?

Şıklar:
A) [GÖRSEL] | B) [GÖRSEL] | C) [GÖRSEL] | D) [GÖRSEL] | E) [GÖRSEL]

Cevap: B [GÖRSEL]

Çözüm:
A seçeneği : (T+C)*G(A+T)*
B seçeneği : (T+C)*G(A+T)*
C seçeneği : (T+C)*G(A*T)*
D seçeneği : (T+C)*G*(A+T)*
E seçeneği : (T+C)G(A+T)
Seçeneklerde verilen durum makinelerinin dil formülü karşılıklarına göre