Font size
S
M
L
XL
WorksheetsAT 2025 Örnek Sınav
Total questions: 100
Worksheet time: 2hrs 40mins
Name
Class
Date
1.
Bir Deterministik Sonlu Otomat (DFA) resmi olarak kaçlı bir demet (tuple) ile tanımlanır?
a)
3
b)
4
c)
5
d)
6
e)
7
2.
DFA'nın geçiş fonksiyonu (δ) aşağıdakilerden hangisi ile ifade edilir?
a)
Q×Σ→Q
b)
Q×Σ→Σ
c)
Q×Q→Σ
d)
Σ×Σ→Q
e)
Q×Σ→2Q
3.
Bir alfabedeki sembollerin sonlu dizisine ne ad verilir?
a)
Dil (Language)
b)
Alfabe (Alphabet)
c)
Dizi (String)
d)
Geçiş (Transition)
e)
Durum (State)
4.
Uzunluğu sıfır olan diziye ne ad verilir ve nasıl gösterilir?
a)
Sıfır dizisi, 0
b)
Boş küme, ∅
c)
Boş dizi, ε (epsilon)
d)
Null, N
e)
Hiçlik, λ
5.
NFA (Nondeterministic Finite Automaton) ile DFA arasındaki temel farklardan biri nedir?
a)
NFA'nın sonlu durumu yoktur.
b)
NFA, bir sembol okumadan (ε-geçişi) durum değiştirebilir.
c)
NFA'nın kabul durumları olamaz.
d)
DFA'nın başlangıç durumu yoktur.
e)
NFA daha az güce sahiptir.
6.
Bir NFA'nın geçiş fonksiyonu (δ) çıktı olarak ne üretir?
a)
Tek bir durum
b)
Bir sembol
c)
Bir durum kümesi (2Q)
d)
Boş küme
e)
Kabul veya Ret
7.
"Hesaplamanın her adımında bir sonraki durumun tek bir şekilde belirlendiği" makine türü hangisidir?
a)
NFA
b)
PDA
c)
Turing Makinesi
d)
DFA
e)
GNFA
8.
Aşağıdakilerden hangisi Düzenli Dillerin (Regular Languages) kapalı olduğu işlemlerden biri değildir?
a)
Birleşim (Union)
b)
Kesişim (Intersection)
c)
Yıldız (Star)
d)
Birleştirme (Concatenation)
e)
Alt Küme (Subset)
9.
"Nondeterminism" kavramı, hesaplama açısından nasıl düşünülebilir?
a)
Rastgele hesaplama
b)
Paralel hesaplama (makinenin dallanması)
c)
Sonsuz döngü
d)
Hatalı hesaplama
e)
Geriye dönük hesaplama
10.
Her NFA'nın eşdeğer bir DFA'sı var mıdır?
a)
Hayır, NFA'lar daha güçlüdür.
b)
Evet, her zaman vardır.
c)
Sadece sonlu diller için vardır.
d)
Sadece alfabesi {0,1} olanlar için vardır.
e)
Hayır, DFA'lar daha güçlüdür.
11.
n duruma sahip bir NFA, eşdeğer bir DFA'ya dönüştürüldüğünde, DFA en fazla kaç duruma sahip olabilir?
a)
n
b)
n2
c)
2n
d)
n!
e)
n+1
12.
Düzenli ifadelerde (Regular Expressions) ∅ ile ε arasındaki fark nedir?
a)
Fark yoktur.
b)
∅ boş dili (hiçbir dizi içermeyen), ε ise içinde sadece boş dizi bulunan dili temsil eder.
c)
∅ sonlu, ε sonsuzdur.
d)
ε bir semboldür, ∅ bir işlemdir.
e)
∅ kabul durumu, ε başlangıç durumudur.
13.
Bir dilin düzenli (regular) olduğunu kanıtlamak için aşağıdakilerden hangisi kullanılamaz?
a)
O dili tanıyan bir DFA çizmek.
b)
O dili tanıyan bir NFA çizmek.
c)
O dili üreten bir düzenli ifade yazmak.
d)
Pumping Lemma kullanmak.
e)
Düzenli dillerin kapalılık özelliklerini kullanmak.
14.
Pumping Lemma'ya göre, düzenli bir dildeki yeterince uzun bir s dizisi s=xyz şeklinde bölündüğünde, aşağıdakilerden hangisi kesinlikle doğrudur?
a)
∣y∣>0
b)
∣xy∣>p
c)
x,y,z eşit uzunluktadır.
d)
y sadece 0'lardan oluşur.
e)
s dizisi sonludur.
15.
L={0n1n∣n≥0} dili neden düzenli değildir?
a)
Alfabesi çok büyüktür.
b)
Sonsuz sayıda durumu hatırlaması gerekir (hafıza sınırlaması).
c)
ε içerdiği için.
d)
DFA ile çizilebilir ancak NFA ile çizilemez.
e)
Düzenli ifadelerle gösterilebilir.
16.
Pumping Lemma kullanılarak L={0n1n∣n≥0} dilinin düzenli olmadığı kanıtlanırken seçilen test dizisi (s) hangisi olabilir?
a)
1
b)
0p1p
c)
(01)p
d)
01∗
e)
0p
17.
Aşağıdaki dillerden hangisi düzenli bir dildir?
a)
{w∣w eşit sayıda 0 ve 1 içerir}
b)
{w∣w bir palindromdur (tersi kendisine eşit)}
c)
{w∣w çift sayıda 1 içerir}
d)
{0n1n∣n≥0}
e)
{1p∣p bir asal sayıdır}
18.
(a∪b)∗ düzenli ifadesi hangi dili tanımlar?
a)
Sadece a içeren diziler
b)
Sadece b içeren diziler
c)
a ve b ile oluşturulabilecek tüm diziler
d)
Boş küme
e)
Sadece ab dizisi
19.
Bir DFA'nın kabul ettiği diziler kümesine ne ad verilir?
a)
Alfabesi
b)
Geçiş tablosu
c)
Dili
d)
Durum uzayı
e)
Pumping uzunluğu
20.
Beş duruma sahip bir DFA'nın tanıdığı dildeki, uzunluğu 5 veya daha fazla olan bir dizi kabul ediliyorsa, bu durum neyi garanti eder?
a)
Dilin sonsuz olduğunu
b)
Hesaplama sırasında bir döngü (loop) oluştuğunu
c)
Dilin düzenli olmadığını
d)
Makinenin deterministik olmadığını
e)
Start durumunun aynı zamanda kabul durumu olduğunu
21.
Bağlamdan Bağımsız Dilbilgisi (CFG) kaçlı bir yapı ile tanımlanır?
a)
3
b)
4 (V,Σ,R,S)
c)
5
d)
6
e)
7
22.
CFG'de V ve Σ neyi temsil eder?
a)
Vektörler ve Sayılar
b)
Değişkenler (Variables) ve Terminaller
c)
Değerler ve Sonuçlar
d)
Vertices (Köşeler) ve Kenarlar
e)
Hacim ve Yüzey
23.
Bir dizinin bir gramerde birden fazla en sol türetime (leftmost derivation) sahip olması ne anlama gelir?
a)
Gramerin hatalı olduğu
b)
Dilin düzenli olduğu
c)
Gramerin belirsiz (ambiguous) olduğu
d)
Dilin sonsuz olduğu
e)
Gramerin Chomsky Normal Formda olduğu
24.
Chomsky Normal Form'da (CNF) kurallar hangi formatta olmalıdır?
a)
A→BC veya A→a
b)
A→B veya A→ε
c)
A→aB veya A→ε
d)
A→BcD
e)
S→SS
25.
Aşağığa İtmeli Otomat (Pushdown Automaton - PDA) ile NFA arasındaki temel donanım farkı nedir?
a)
PDA'nın iki okuma kafası vardır.
b)
PDA'nın bir yığıtı (stack) vardır.
c)
PDA deterministiktir.
d)
PDA'nın sonsuz bandı vardır.
e)
Fark yoktur.
26.
PDA'nın yığıtı (stack) hangi prensiple çalışır?
a)
FIFO (First In First Out)
b)
LIFO (Last In First Out)
c)
Rastgele Erişim
d)
Sadece Yazılabilir
e)
Sadece Okunabilir
27.
Aşağıdaki dillerden hangisi Bağlamdan Bağımsızdır (CFL) ancak Düzenli (Regular) değildir?
a)
{anbm∣n,m≥0}
b)
{w∣w çift sayıda 0 içerir}
c)
{anbn∣n≥0}
d)
{anbncn∣n≥0}
e)
Σ∗
28.
Bir PDA'nın geçiş fonksiyonu δ şu şekilde tanımlanır:
a)
Q×Σ→Q
b)
Q×Σε×Γε→P(Q×Γε)
c)
Q×Γ→Q×Γ×{L,R}
d)
Σ×Γ→Q
e)
Q×Σ→Γ
29.
Her Bağlamdan Bağımsız Dil (CFL) için aşağıdakilerden hangisi doğrudur?
a)
Kesinlikle düzenli bir dildir.
b)
Bir PDA tarafından tanınabilir.
c)
Bir DFA tarafından tanınabilir.
d)
Bir NFA tarafından tanınabilir.
e)
Her zaman sonludur.
30.
L={anbncn∣n≥0} dili neden Bağlamdan Bağımsız (Context-Free) değildir?
a)
Yığıt (stack) sadece iki öğeyi karşılaştırabilir, üçünü aynı anda sayamaz.
b)
Dil sonludur.
c)
ε içerir.
d)
Düzenli olduğu için.
e)
Alfabesi 3 sembollü olduğu için.
31.
Deterministik PDA (DPDA) ile standart (Nondeterministik) PDA arasındaki güç ilişkisi nasıldır?
a)
Eşittirler.
b)
DPDA daha güçlüdür.
c)
PDA (Nondeterministik) daha güçlüdür.
d)
Kıyaslanamazlar.
e)
DPDA sadece düzenli dilleri tanır.
32.
Bağlamdan Bağımsız Diller (CFL) hangi işlem altında kapalı değildir?
a)
Birleşim (Union)
b)
Birleştirme (Concatenation)
c)
Yıldız (Star)
d)
Kesişim (Intersection)
e)
Tersini Alma (Reversal)
33.
Chomsky Normal Form'da (CNF) verilen bir gramer ile uzunluğu n olan bir diziyi türetmek kaç adım sürer?
a)
n
b)
2n
c)
2n−1
d)
n2
e)
logn
34.
Bir CFG'deki "kullanışsız semboller" (useless symbols) nelerdir?
a)
Alfabede olmayan semboller.
b)
Başlangıç değişkeninden ulaşılamayan veya terminal dizisi üretemeyen değişkenler.
c)
Sadece ε üretenler.
d)
Büyük harfle yazılanlar.
e)
Sağ tarafta hiç bulunmayanlar.
35.
Aşağıdaki gramer hangi dili üretir? S→0S1∣ε
a)
{0n1m∣n,m≥0}
b)
{0n1n∣n≥0}
c)
(0∪1)∗
d)
{01}∗
e)
Boş küme
36.
Palindromların dili (w=wR) için aşağıdakilerden hangisi doğrudur?
a)
Düzenli bir dildir.
b)
Bağlamdan bağımsızdır (Context-Free).
c)
Turing-tanınabilir değildir.
d)
Sonlu bir dildir.
e)
Sadece deterministik PDA ile tanınabilir.
37.
Bir gramerin "belirsiz" (ambiguous) olması ne demektir?
a)
Bir dizi için birden fazla ayrıştırma ağacı (parse tree) oluşturulabilmesi.
b)
Gramerin hiçbir dizi üretmemesi.
c)
Gramerin sonsuz döngüye girmesi.
d)
Gramerin CNF formunda olmaması.
e)
Dilin düzenli olması.
38.
L={aibjck∣i<j<k} dili için ne söylenebilir?
a)
Düzenlidir.
b)
Bağlamdan bağımsızdır.
c)
Bağlamdan bağımsız değildir (Pumping Lemma ile gösterilebilir).
d)
Sonludur.
e)
Bir DFA ile tanınabilir.
39.
Yığıt (Stack) yapısı hangi veri yapısına benzer?
a)
Kuyruk (Queue)
b)
Ağaç (Tree)
c)
Tabak yığını (LIFO)
d)
Dizi (Array)
e)
Hash Tablosu
40.
Bir PDA'nın anlık tanımı (konfigürasyonu) neleri içerir?
a)
Sadece mevcut durum.
b)
Mevcut durum, okunan girdi, yığıt içeriği.
c)
Sadece yığıt içeriği.
d)
Geçmiş durumlar.
e)
Gelecek girdiler.
41.
Turing Makinesi'nin (TM) sonlu otomatlardan en büyük farkı nedir?
a)
Durumlarının olması.
b)
Alfabesinin olması.
c)
Sonsuz ve yazılabilir bir banda (tape) sahip olması.
d)
Deterministik olması.
e)
Kabul durumunun olması.
42.
Church-Turing Tezi neyi ifade eder?
a)
Her algoritma bir Turing Makinesi ile ifade edilebilir.
b)
Turing makineleri insanlardan daha zekidir.
c)
Turing makineleri her problemi çözebilir.
d)
DFA ve NFA eşdeğerdir.
e)
P = NP.
43.
Bir Turing Makinesinin "karar verici" (decider) olması ne demektir?
a)
Her girdiyi kabul etmesi.
b)
Her girdiyi reddetmesi.
c)
Her girdi için mutlaka durması (halt) (kabul veya ret ile).
d)
Asla durmaması.
e)
Sadece düzenli dilleri tanıması.
44.
ATM={⟨M,w⟩∣M bir TM ve M,w'yi kabul eder} dili için hangisi doğrudur?
a)
Karar verilebilir (Decidable).
b)
Turing-tanınabilir (Turing-recognizable) fakat karar verilemez (Undecidable).
c)
Düzenlidir.
d)
Bağlamdan bağımsızdır.
e)
Tanınamaz.
45.
Durma Problemi (Halting Problem) neyi sorar?
a)
Bir TM'nin sonsuz döngüye girip girmediğini.
b)
Bir TM'nin belirli bir girdide durup durmayacağını.
c)
Bir TM'nin kaç adımda duracağını.
d)
Bir TM'nin boş dili kabul edip etmediğini.
e)
İki TM'nin aynı olup olmadığını.
46.
Durma Problemi (HALTTM) için aşağıdakilerden hangisi doğrudur?
a)
Çözülebilirdir.
b)
Karar verilemezdir (Undecidable).
c)
Polinom zamanda çözülebilir.
d)
DFA ile çözülebilir.
e)
NP-Complete'tir.
47.
Köşegenleştirme (Diagonalization) yöntemi kim tarafından ve ne için geliştirilmiştir?
a)
Alan Turing, TM'leri saymak için.
b)
Georg Cantor, kümelerin büyüklüklerini karşılaştırmak ve sayılamaz kümeleri göstermek için.
c)
Noam Chomsky, dilleri sınıflandırmak için.
d)
Stephen Cook, NP problemleri için.
e)
Hilbert, polinom kökleri için.
48.
Turing makineleri tarafından tanınabilen (recognizable) ancak karar verilemeyen (decidable) diller var mıdır?
a)
Hayır, yoktur.
b)
Evet, ATM buna bir örnektir.
c)
Sadece sonlu diller böyledir.
d)
Sadece düzenli diller böyledir.
e)
Bilinmiyor.
49.
Evrensel Turing Makinesi (Universal Turing Machine - UTM) nedir?
a)
Sadece boş dili tanıyan makine.
b)
Başka bir TM'nin açıklamasını ve girdisini alıp onu simüle edebilen TM.
c)
Her problemi çözebilen sihirli makine.
d)
Sonsuz sayıda durumu olan makine.
e)
Sadece matematiksel işlemleri yapan makine.
50.
"Turing-tanınabilir" (Turing-recognizable) ne demektir?
a)
Dilin bir TM tarafından kabul edilmesi (kabul edilenler için durur, edilmeyenler için durmayabilir).
b)
Dilin bir TM tarafından her zaman durarak kabul veya reddedilmesi.
c)
Dilin bir DFA tarafından tanınması.
d)
Dilin bir CFG ile üretilmesi.
e)
Dilin sonlu olması.
51.
Hilbert'in 10. Problemi ne ile ilgilidir?
a)
Asal sayıların dağılımı.
b)
Bir polinomun tamsayı köklerinin olup olmadığının algoritmik olarak bulunması.
c)
Turing makinelerinin eşdeğerliği.
d)
P vs NP problemi.
e)
Satranç oyununun çözümü.
52.
Turing makinelerinin "konfigürasyonu" neleri içerir?
a)
Sadece bant içeriği.
b)
Mevcut durum, bant içeriği ve kafa pozisyonu.
c)
Sadece kafa pozisyonu.
d)
Geçiş fonksiyonu.
e)
Girdi alfabesi.
53.
Bir dil hem Turing-tanınabilir (recognizable) hem de tümleyeni (co-Turing-recognizable) Turing-tanınabilir ise, bu dil nedir?
a)
Düzenlidir.
b)
Karar verilebilir (Decidable).
c)
Karar verilemez.
d)
Bağlamdan bağımsızdır.
e)
Boş kümedir.
54.
Sayılabilir (Countable) küme ne demektir?
a)
Eleman sayısı sonlu olan küme.
b)
Elemanları Doğal Sayılar (N) kümesi ile birebir eşlenebilen küme.
c)
Reel sayılar kümesi.
d)
Elemanları sayılamayacak kadar çok olan küme.
e)
Hiçbir elemanı olmayan küme.
55.
Reel Sayılar (R) kümesi sayılabilir mi?
a)
Evet.
b)
Hayır, sayılamaz (Uncountable).
c)
Sadece pozitif olanlar sayılabilir.
d)
Rasyonel sayılarla aynı büyüklüktedir.
e)
Sonludur.
56.
İki Turing Makinesinin eşdeğerliği (EQTM) problemi nasıldır?
a)
Karar verilebilir.
b)
Karar verilemez.
c)
Düzenlidir.
d)
NFA ile çözülebilir.
e)
Polinom zamanda çözülebilir.
57.
Rice Teoremi neyi ifade eder?
a)
Turing makinelerinin dilleriyle ilgili her "nontrivial" (aşikar olmayan) özellik karar verilemezdir.
b)
Her TM durur.
c)
P = NP.
d)
Düzenli diller sonsuzdur.
e)
Turing makineleri pirinç sever.
58.
Bir TM'nin dilinin boş olup olmadığı problemi (ETM) nasıldır?
a)
Karar verilebilir.
b)
Karar verilemez.
c)
Düzenlidir.
d)
Basittir.
e)
Çözülebilir.
59.
İndirgeme (Reduction) yöntemi ne için kullanılır?
a)
Bir problemi basitleştirmek için.
b)
Bir problemin çözülemez olduğunu, onu bilinen başka bir çözülemez probleme bağlayarak göstermek için.
c)
Makineyi küçültmek için.
d)
Bellek tasarrufu için.
e)
Hızlandırma için.
60.
Doğrusal Sınırlı Otomat (LBA - Linear Bounded Automaton) nedir?
a)
Bandı sonsuz olmayan, sadece girdi boyutu kadar (veya doğrusal oranda) alan kullanan TM.
b)
Sonsuz banda sahip TM.
c)
Stack kullanan makine.
d)
Sadece sağa gidebilen TM.
e)
Deterministik olmayan PDA.
61.
Zaman Karmaşıklığı (Time Complexity) analizi genellikle hangi notasyonla yapılır?
a)
Küçük-o
b)
Big-O (O(n))
c)
Türev
d)
İntegral
e)
Logaritma
62.
P sınıfı (Class P) neyi temsil eder?
a)
Polinom zamanda çözülebilen problemleri.
b)
Çözülemeyen problemleri.
c)
Olasılıksal problemleri.
d)
Sadece asal sayı problemlerini.
e)
Paralel problemleri.
63.
NP sınıfı (Class NP) neyi temsil eder?
a)
Çözümü polinom zamanda bulunamayan problemleri.
b)
Nondeterministik Polinom zamanda çözülebilen (veya çözümü polinom zamanda doğrulanabilen) problemleri.
c)
Asla çözülemeyen problemleri.
d)
Negatif Polinom problemleri.
e)
Sadece deterministik problemleri.
64.
P vs NP problemi nedir?
a)
Polinom zamanda doğrulanabilen her problemin, aynı zamanda polinom zamanda çözülüp çözülemediği sorusudur.
b)
Bilgisayarların insanlardan hızlı olup olmadığıdır.
c)
Turing makinelerinin durup durmayacağıdır.
d)
Sonsuzluğun boyutu problemidir.
e)
Şifreleme problemidir.
65.
Bir problemin NP-Complete olması ne demektir?
a)
Problemin çözülemez olduğu anlamına gelir.
b)
Problemin NP'deki en zor problemlerden biri olduğu ve NP'deki her problemin ona indirgenebildiği anlamına gelir.
c)
Problemin P sınıfında olduğu anlamına gelir.
d)
Problemin çok kolay olduğu anlamına gelir.
e)
Problemin matematiksel olmadığı anlamına gelir.
66.
Aşağıdakilerden hangisi bilinen ilk NP-Complete problemdir?
a)
SAT (Satisfiability)
b)
Hamilton Yolu
c)
Gezgin Satıcı Problemi (TSP)
d)
Clique
e)
Vertex Cover
67.
Eğer bir NP-Complete problem için polinom zamanda çalışan bir algoritma bulunursa ne olur?
a)
Sadece o problem hızlı çözülür.
b)
P = NP olduğu kanıtlanmış olur.
c)
Bilgisayarlar çöker.
d)
Hiçbir şey değişmez.
e)
Turing makineleri geçersiz olur.
68.
3SAT problemi nedir?
a)
3 değişkenli formüllerin çözümü.
b)
Her tümceciğinde (clause) tam olarak 3 literal bulunan mantıksal formüllerin tatmin edilebilirliği.
c)
3 boyutlu satranç.
d)
3 işlemcili hesaplama.
e)
3. dereceden denklemler.
69.
CLIQUE (Klik) problemi nedir?
a)
Bir grafın köşelerini boyama.
b)
Bir grafta, her düğümün birbirine bağlı olduğu k büyüklüğünde bir alt graf bulma.
c)
En kısa yolu bulma.
d)
Grafı ikiye bölme.
e)
Graftaki döngüleri sayma.
70.
Vertex Cover (Tepe Örtüsü) problemi hangi sınıfa aittir?
a)
P
b)
NP-Complete
c)
Decidable but Exponential
d)
L (Logarithmic Space)
e)
Regular
71.
Hamilton Yolu (Hamiltonian Path) problemi nedir?
a)
En kısa yol problemi.
b)
Bir graftaki her düğümden tam olarak bir kez geçen bir yol bulma problemi.
c)
Her kenardan bir kez geçen yol bulma (Euler).
d)
Grafın merkezini bulma.
e)
Ağaç oluşturma.
72.
Gezgin Satıcı Problemi (Traveling Salesman Problem - TSP) ile Hamilton Döngüsü arasındaki ilişki nedir?
a)
İlişki yoktur.
b)
TSP, Hamilton Döngüsü'nün ağırlıklı graflardaki genelleştirilmiş halidir.
c)
Hamilton döngüsü P'dedir, TSP NP'dedir.
d)
Biri graf, diğeri sayı problemidir.
e)
TSP çözülebilir, Hamilton çözülemez.
73.
Subset Sum (Alt Küme Toplamı) problemi nedir?
a)
Bir sayı kümesindeki elemanların toplamının belirli bir t sayısına eşit olan bir alt kümesini bulma.
b)
Tüm sayıları toplama.
c)
Kümeyi sıralama.
d)
En büyük sayıyı bulma.
e)
Sayıları çarpma.
74.
Uzay Karmaşıklığı (Space Complexity) neyi ölçer?
a)
Algoritmanın kaç adımda bittiğini.
b)
Algoritmanın çalışırken bant üzerinde kullandığı maksimum hücre sayısını.
c)
Algoritmanın kod satır sayısını.
d)
Diskte kapladığı yeri.
e)
Elektrik tüketimini.
75.
Savitch Teoremi neyi ifade eder?
a)
P = NP.
b)
Deterministik ve Nondeterministik uzay karmaşıklığı arasında NSPACE(f(n))⊆SPACE(f2(n)) ilişkisi vardır.
c)
Zaman ve uzay eşittir.
d)
Her problem logaritmik uzayda çözülebilir.
e)
Uzay sonsuzdur.
76.
PSPACE sınıfı nedir?
a)
Polinom zamanda çözülenler.
b)
Polinom miktarda yer (bellek) kullanılarak çözülebilen problemler sınıfı.
c)
Paralel uzay.
d)
Olasılıksal uzay.
e)
Sonsuz uzay.
77.
TQBF (Totally Quantified Boolean Formula) problemi hangi sınıfın tam (complete) problemidir?
a)
NP
b)
P
c)
PSPACE
d)
EXPTIME
e)
L
78.
Bir problemin "intractable" (zor/çetin) olması ne demektir?
a)
Çözülemez (undecidable) olması.
b)
Çözülebilir (decidable) olması ancak pratikte makul sürede (polinom zaman) çözülememesi (örn. üstel zaman gerektirmesi).
c)
Yanlış tanımlanmış olması.
d)
Donanım hatası vermesi.
e)
Sadece kuantum bilgisayarla çözülmesi.
79.
SAT problemi polinom zamanda çözülebilirse ne olur?
a)
P = NP olur.
b)
Dünya durur.
c)
P != NP kesinleşir.
d)
Şifreleme daha güvenli olur.
e)
İnternet çöker.
80.
O(nlogn) karmaşıklığı genellikle hangi algoritmalar için geçerlidir?
a)
Arama algoritmaları.
b)
Verimli sıralama (sorting) algoritmaları (örn. Merge Sort).
c)
Matris çarpımı.
d)
Gezgin satıcı.
e)
Alt küme toplamı.
81.
Aşağıdakilerden hangisi bir "Tek Yönlü Fonksiyon" (One-Way Function) özelliğidir?
a)
Hesaplanması ve tersini alması kolaydır.
b)
Hesaplanması kolay, tersini alması çok zordur.
c)
Tersini alması kolay, hesaplanması zordur.
d)
Ne hesaplanabilir ne de tersi alınabilir.
e)
Sadece tek sayılarla çalışır.
82.
RSA şifreleme algoritması neye dayanır?
a)
Sıralama zorluğuna.
b)
Büyük sayıları çarpanlarına ayırmanın (factorization) zorluğuna.
c)
En kısa yolu bulmaya.
d)
Graf boyamaya.
e)
Diferansiyel denklemlere.
83.
İnteraktif İspat Sistemleri (Interactive Proof Systems) hangi sınıf ile ilişkilidir?
a)
IP
b)
P
c)
Regular
d)
Context-Free
e)
None
84.
IP = PSPACE teoremi neyi gösterir?
a)
İnteraktif ispat sistemlerinin gücünün PSPACE'e eşit olduğunu.
b)
P = NP olduğunu.
c)
Uzay ve zamanın aynı olduğunu.
d)
Her şeyin kanıtlanabileceğini.
e)
IP'nin çok küçük bir sınıf olduğunu.
85.
L ve NL sınıfları neyi ifade eder?
a)
Lineer Zaman ve Non-lineer Zaman.
b)
Logaritmik Uzay (Logarithmic Space) ve Nondeterministik Logaritmik Uzay.
c)
Large ve Non-Large.
d)
Limited ve Non-Limited.
e)
Loop ve Non-Loop.
86.
PATH (yol bulma) problemi hangi karmaşıklık sınıfında tamdır (complete)?
a)
P
b)
NP
c)
NL
d)
PSPACE
e)
EXPTIME
87.
Olasılıksal Turing Makinesi (Probabilistic TM) nedir?
a)
Rastgele seçimler yapabilen (yazı-tura atabilen) bir Nondeterministik TM türevi.
b)
Her zaman doğru sonucu veren makine.
c)
Kuantum makinesi.
d)
Bozuk makine.
e)
Sadece istatistik hesaplayan makine.
88.
BPP sınıfı (Bounded-error Probabilistic Polynomial time) neyi tanımlar?
a)
Hatasız çalışan algoritmaları.
b)
Polinom zamanda çalışan ve hata olasılığı belirli bir oranın (örn. 1/3) altında olan olasılıksal algoritmaları.
c)
Üstel zamanda çalışan algoritmaları.
d)
Sonsuz sürede çalışanları.
e)
Hiç hata yapmayanları.
89.
Bir dilin "Co-NP" sınıfında olması ne demektir?
a)
Dilin NP'de olması.
b)
Dilin tümleyeninin (complement) NP sınıfında olması.
c)
Dilin P'de olması.
d)
Dilin karar verilemez olması.
e)
Dilin iki işlemcili olması.
90.
Turing İndirgemesi (Turing Reduction - ≤T) ile Haritalama İndirgemesi (≤m) farkı nedir?
a)
Fark yoktur.
b)
Turing indirgemesi "Oracle" (Kahin) kullanımına izin verir, haritalama indirgemesi sadece girdi dönüştürmeye izin verir.
c)
Haritalama daha güçlüdür.
d)
Turing indirgemesi sadece DFA'lar içindir.
e)
Haritalama indirgemesi zaman almaz.
91.
Church-Turing tezine göre "Algoritma" kavramının karşılığı nedir?
a)
C programı.
b)
Turing Makinesi.
c)
Abaküs.
d)
İnsan beyni.
e)
Kuantum bilgisayar.
92.
Bir Turing Makinesinin bandı (tape) nasıldır?
a)
Sonludur.
b)
Tek yönlü sonsuz veya iki yönlü sonsuzdur (sınırsız hafıza).
c)
Daireseldir.
d)
Sadece okunabilirdir.
e)
Yoktur.
93.
Deterministik Olmayan (Nondeterministic) hesaplama gerçek hayatta nasıl simüle edilebilir?
a)
Kuantum bilgisayarlarla.
b)
Paralel işlemcilerle veya "backtracking" (geri izleme) algoritmalarıyla.
c)
Rastgele sayı üreteciyle.
d)
Simüle edilemez.
e)
Sadece kağıt üzerinde.
94.
ADFA (DFA Acceptance Problem) dili nasıldır?
a)
Karar verilebilir (Decidable).
b)
Karar verilemez.
c)
Düzenli değildir.
d)
Tanınamaz.
e)
NP-Complete.
95.
ECFG (CFG Emptiness Problem) dili nasıldır?
a)
Karar verilebilir.
b)
Karar verilemez.
c)
Zordur.
d)
Tanınamaz.
e)
Bilinmiyor.
96.
EQCFG (İki CFG'nin eşdeğerliği) dili nasıldır?
a)
Karar verilebilir.
b)
Karar verilemez (Undecidable).
c)
Düzenlidir.
d)
Basittir.
e)
NP'dedir.
97.
Post Correspondence Problem (PCP) nedir?
a)
Postanede mektup sıralama problemi.
b)
Domino taşlarını üst ve alt diziler eşleşecek şekilde dizme problemi; karar verilemezdir.
c)
En kısa yol problemi.
d)
Ağ analizi problemi.
e)
E-posta şifreleme.
98.
Zaman Hiyerarşisi Teoremi (Time Hierarchy Theorem) genel olarak neyi söyler?
a)
Daha fazla zaman verilirse, daha fazla problem çözülebilir (Turing makinesi için).
b)
Zaman görecelidir.
c)
P = NP.
d)
Tüm problemler O(n) sürede çözülür.
e)
Zamanın önemi yoktur.
99.
Polinom zamanlı indirgeme (A≤PB) ne işe yarar?
a)
A'nın B'den daha zor olmadığını, B'yi çözebilirsek A'yı da hızlıca çözebileceğimizi gösterir.
b)
A ve B'nin eşit olduğunu gösterir.
c)
A'nın B'den daha zor olduğunu gösterir.
d)
A'nın çözülemez olduğunu gösterir.
e)
B'nin çözülemez olduğunu gösterir.
100.
"Sınırlı Hata Olasılıklı" (Bounded-error) ne demektir?
a)
Hata oranının 1/2'den kesinlikle uzak (örn. en fazla 1/3) olması.
b)
Hatanın 0 olması.
c)
Hatanın %50 olması.
d)
Hatanın sonsuz olması.
e)
Hatanın bilinmemesi.
Reset
