Kart Oyunu

Soru: Bir oyunda toplam 10 tane oyun kartı vardır ve kartların her birinin ön yüzüne 1 ile 10
arasında farklı bir sayı yazılmıştır. 3 tane kart (yerine konmadan) ardışık olarak rastgele
seçildiğinde bu seçilen kartların küçükten büyüğe sıralı olma ihtimali kaçtır?

 

Cevap: Bu bir permütasyon sorusudur. Öncelikle 10 kartı nasıl sıralayabileceğimizi hesaplarız daha sonra sıralı halde kaç tane olduğunu hesaplarız.
P(10,3) = 10!/3! = 10.9.8=720
Sıralı halde olanlar ise şöyledir:
8+7+…..+1 (1 ve 2 seçersem 8 ihtimal var 1 ve 3 seçersem 7 ihtimal var…)
7+6+…..+1 (2 ve 3 seçersem 7 ihtimal var 2 ve 4 seçersem 6 ihtimal var…)
1 (8,9,10)
Toplam 120 yapıyor.
Sonuç = 120 / 720 = 1/6

yeniden dfa :)

Soru: Alfabemiz Σ={0,1,2} den oluşsun. L1={ w € Σ*: w 0 ile başlıyor veya 0 ile bitiyor fakat her iki durum söz konusu değil }

Buna göre L1 dilini tanıyan DFA’yı oluşturun. Açıklayınız.

Not = € (elemanıdır manasına geliyor)

Çözüm:

L1 diline ait  dfa yukaridaki gibidir.

5 tane durumumuz var : q0,q1,q2,q3,q4. Eğer O ile başladıysak O ile DFA yı bitiremeyiz. Bu yüzden O ile q3 durumuna ulaşmayız. Yukardaki gibi  q1 durumuna O ları götürebiliriz. Eğer 1 veya 2 ile başladıysak O ile bitirmemiz gerek. Aksi taktirde şartımız şağlanmaz.

chomsky hiyerarşisi

en basit şekilde chomsky hiyerarşisi aşağıdaki gibidir.

Tip 0: yinelemeli sıralı diller (kısıtlamasız dilbilgisi)
Tip 1: context-sensitive diller (context-sensitive dilbilgisi)
Tip 2: context-free diller (context-free dilbilgisi)
Tip 3: düzenli (regüler) diller (sağ-doğrusal ve sol-doğrusal dilbilgileri)

Dileri tanıyan modeller ise şöyle:

Tip 0: Turing Makinesi
Tip 1: Doğrusal Sınırlandırılmış Otomat (Linear Bounded Automata)
Tip 2: Pushdown Otomat
Tip 3: Sonlu Otomat(NFA,DFA)

programlama

Soru:

int a[3][4]={{1, 2, 3, 3}, {4, 5, 6, 6}, {7, 8, 9, 9}};

short b[4][2]={{1, 1}, {1, 0}, {0, 0}, {0, 1}}, i;

void main() {

for (i=0; 2*b[i][1]+b[i][0]; i++)

printf(“%d %d “, a[b[i][0]][i], a[i+1][i]);

}

Yukarıda verilen programın çıktısı ne olur?

(Not:Bilgisayar kullanmadan çözmeye çalışın)

Çözüm:

Çıktı Şöyle olur:
4 4 5 8

turing

Soru: n ≥ 1 olmak üzere

  

işlemini gerçekleştiren Turing makinasını tasarlayın. Biçimsel tanımını verin.

Çözüm:

1- Önce 0 yerine T koyulur.

2- Sağdaki 1 ler T nin solundaki B lerin yerine taşınır. 1 sayısı kadar 2 T lerin soluna eklenir.

3- 1 lerin 2 katı alınıp tekrar eski yere getirilir. (2 katı alınıdığı zaman sonuç sağa kayıyor. Bunun için sola öteleme yapıyoruz.)

 4. 1. adıma dönülür taki 0 lar bitene kadar. En sonunda 1 tane 2 eklenir.

şifreler

Soru:4 adet rakamdan oluşan ve içinde çift sayıda 0 bulunan kaç farklı şifre oluşturulabilir?

 

Çözüm:

  Şifremiz 4 haneli olacak     X X X X ve çift sayıda 0 olacak.

 

  Şimdi bütün ihtimalleri göz önüne alalım:

 

  0 sayısı 0 olabilir:

 

  Böyle  bir durumda; 9 x 9 x 9 x 9 = 6561 tane şifre üretebiliriz.

 

  0 sayısı 2 olabilir:

 

  Böyle bir durumda ise 0’ların konumuna göre elde edeceğimiz şifre sayısı değişir.

 

 00XX

 0X0X

 0XX0

 XX00

 X00X

 X0X0

 

 

C(4,2) x 9 x 9 = 6 x 9 x 9 = 486

 

 0 sayısı 4 olabilir:

 

 Böyle durumda oluşan şifre sadece 1 tanedir.

 

 0000                               

 

 6561 + 486 + 1  =  7048

 

askerlik bitti

uzun bir aradan sonra tekrar merhaba 🙂
vatani görevimi bitirdikten sonra tekrar sanal alemdeyim.
ayrık matematikle ilgili ders notları, sorular paylaşmaya devam edeceğim.
açılışı bir kombinasyon sorusu ile yapmayı düşünüyorum.