Formüller ve kolay yollar

1Bilgisayar: bilgi, donanım ve yazılımBaşlangıç

Bilgi, bilginin türleri ve bilgi süreçleri

Derse git

Bilgisayarın yapısı: işlemci, bellek ve anakart

Derse git

N = f · t

burada:

Nsaat döngüsü sayısı
fsaat frekansı, Hz (1 GHz = 1000 MHz = 10⁹ Hz)
tsüre, saniye

Hertz “saniyede bir kez” demektir: frekans bir saniyede kaç döngü olduğunu gösterir.

N = 2ⁿ

burada:

nadres yolunun genişliği (bit sayısı)
Nadreslenebilen bellek hücrelerinin (baytların) sayısı

Her hücre 1 bayt ise N baytlık belleğe erişilebilir.

Giriş ve çıkış birimleri

Derse git

N = a · b

burada:

Nekrandaki piksel sayısı
a, byatay ve dikey piksel sayıları (çözünürlük a × b)

Piksel sayısı, çözünürlüğün iki sayısının çarpımıdır.

d (cm) = d (inç) · 2,54

burada:

dekran köşegeni

İnçi santimetreye çevirmek için 2,54 ile çarpın.

t = N / vt = N / v

burada:

tyazdırma süresi, dakika
Nsayfa sayısı
vyazıcının hızı, sayfa/dk

İki yazıcı birlikte çalışınca hızları toplanır.

Dosya sistemleri ve diskte kaplanan alan

Derse git

k = ⌈V / c⌉, V_disk = k · ck = ⌈V / c⌉, V_disk = k · c

burada:

Vdosyanın bilgi hacmi (boyutu)
cküme boyutu (V ile aynı birimde)
kdosyanın kapladığı küme sayısı
⌈ ⌉yukarı yuvarlama: kesirli kısım varsa bir sonraki tam sayı alınır
V_diskdosyanın diskte kapladığı alan

Diskteki boyut, dosya boyutundan küçük olmayan en küçük küme katıdır.

ΔV = V_disk − V

burada:

ΔVdosyanın son kümesinde kullanılmadan kalan alan

Her dosya için boş alan 0 ile c − 1 bayt arasındadır; ortalama yarım küme kadardır.

2Kelime işlemciler ve elektronik tablolarBaşlangıç

Kelime işlemciler: düzenleme, biçimlendirme ve klavye işlemleri

Derse git

Elektronik tablo: adresler, aralıklar ve formüller

Derse git

N = (S₂ − S₁ + 1) · (R₂ − R₁ + 1)

burada:

Naralıktaki hücre sayısı
S₁, S₂ilk ve son sütunun sıra numarası (A = 1, B = 2, …)
R₁, R₂ilk ve son satırın numarası

Sütun sayı × satır sayı. “+1”i unutma: B’den F’ye kadar 4 değil, 5 sütun vardır.

Sütun′ = Sütun + Δs, Satır′ = Satır + Δr

burada:

Δsformülün kaç sütun sağa (+) veya sola (−) kopyalandığı
Δrkaç satır aşağı (+) veya yukarı (−) kopyalandığı

Kural adresin her parçasına ayrı ayrı uygulanır. Önünde $ olan parça değişmez. Kesip yapıştırınca (Ctrl+X → Ctrl+V) ise formüldeki adresler hiç değişmez.

Elektronik tabloda fonksiyonlar

Derse git

AVERAGE(D) = SUM(D) / COUNT(D)AVERAGE(D) = SUM(D) / COUNT(D)

burada:

Daralık (veya bağımsız değişken listesi)
COUNT(D)D’deki sayıların adedi; boş ve metin içeren hücreler sayılmaz

Ortalama, toplamın bütün hücrelerin sayısına değil, sayı içeren hücrelerin sayısına bölünmesidir.

TIME(sa; dk; sn) = sa/24 + dk/1440 + sn/86400TIME(sa; dk; sn) = sa/24 + dk/1440 + sn/86400

burada:

sa, dk, snsaat, dakika, saniye
24, 1440, 86400bir gündeki saat, dakika ve saniye sayısı

TIME günün bir kesrini döndürür (0 ile 1 arası). 24 ile çarparsan saat, 24 · 60 ile çarparsan dakika elde edersin.

RADIANS(α) = α · π / 180RADIANS(α) = α · π / 180

burada:

αderece cinsinden açı
π / 180π / 1801°’nin radyan değeri ≈ 0,01745

180° = π radyan. Ters çevirme için Excel’de DEGREES fonksiyonu vardır.

=RAND()*(b − a) + a → a ≤ x < b

burada:

a, baralığın uçları; RAND() · (b − a) uzunluğu ayarlar, + a aralığı kaydırır

Tam sayı gerekirse tam kısım fonksiyonu INT eklenir: =INT(RAND()*6)+1 bir zar gibi 1’den 6’ya kadar sayı verir.

Elektronik tabloda grafikler ve öğeleri

Derse git

p = x / S · 100 (yüzde), α = x / S · 360°p = x / S · 100 (yüzde), α = x / S · 360°

burada:

xdilime karşılık gelen hücrenin değeri
Saralıktaki bütün değerlerin toplamı
pdilimin yüzde payı
αdilimin merkez açısı

Bütün dilimlerin yüzdeleri toplamı %100, açıları toplamı 360° eder. Bir değer değişince S de değişir, bu yüzden bütün yüzdeler değişir.

3Bilginin kodlanması ve ölçülmesiOrta

Bilginin ölçülmesi: bit, bayt ve birimler

Derse git

N = 2ⁱ

burada:

Nkodlanan farklı seçeneklerin sayısı (karakterler, renkler, düzeyler…); alfabe için alfabenin gücü
ibir seçeneğin kodundaki bit sayısı — bir seçeneğin (karakterin) taşıdığı bilgi miktarı

i bitle 2ⁱ farklı kod yazılabilir. N biliniyorsa i = log₂N’dir; N ikinin kuvveti değilse i yukarı yuvarlanır.

1 KB = 2¹³ bit 1 MB = 2²³ bit 1 GB = 2³³ bit

burada:

2³ = 8bayt ile bit arasındaki çarpan
2¹⁰ = 1024komşu birimler arasındaki çarpan (bayt → KB → MB → GB)

Bit cinsinden üsler 3, 13, 23, 33, 43’tür: her sonraki birimde üs 10 artar.

I = K · i

burada:

Iiletinin bilgi hacmi (bit)
Kiletideki karakter sayısı
ibir karakterin bilgi hacmi (bit); N = 2ⁱ

Birkaç sayfalık bir metin için K = sayfa sayısı · sayfadaki satır sayısı · satırdaki karakter sayısı.

I = v · t

burada:

Iiletilen bilginin hacmi (bit)
viletim hızı (bit/s)
tiletim süresi (s)

Buradan t = I / v ve v = I / t. Önce hacmi bite, süreyi saniyeye çevir.

Metin bilgisinin kodlanması

Derse git

I = K · 8 bit (ASCII) I = K · 16 bit (UNICODE)

burada:

Imetnin bilgi hacmi
Kmetindeki bütün karakterlerin sayısı: harfler, rakamlar, boşluklar, noktalama işaretleri

Bu, I = K · i formülünün özel bir durumudur: ASCII’de i = 8, UNICODE’da i = 16. Aynı metin UNICODE’da ASCII’dekinin 2 katı yer kaplar.

i = I / K, N = 2ⁱi = I / K, N = 2ⁱ

burada:

ikarakter başına bit sayısı
Imetin kısmının hacmi (bit); resimlerin hacmi önce çıkarılır
Kkarakter sayısı
Nalfabenin gücü

Ters soruların anahtarı: önce metnin hacmini ayır, sonra karakter sayısına böl.

Bilgisayar grafiği: raster ve vektör görüntülerin kodlanması

Derse git

N = 2ⁱ

burada:

Npaletteki renk (ton) sayısı
irenk derinliği — bir pikselin kodundaki bit sayısı

Palet ikinin kuvveti değilse i yukarı yuvarlanır: 100 renk için 7 bit gerekir (2⁷ = 128). DİM bunu şöyle ifade eder: “her renk mümkün olan en az bit sayısıyla kodlanır”.

V = W · H · i

burada:

Vraster görüntünün bilgi hacmi (bit)
Wendeki piksel sayısı
Hboydaki piksel sayısı
irenk derinliği (bit), N = 2ⁱ

Önce i’yi paletten bul, sonra çarp ve bitleri istenen birime çevir: 2¹³ bit = 1 KB, 2²³ bit = 1 MB.

V₂ / V₁ = (W₂ / W₁) · (H₂ / H₁) · (i₂ / i₁)V₂ / V₁ = (W₂ / W₁) · (H₂ / H₁) · (i₂ / i₁)

burada:

W₂ / W₁, H₂ / H₁W₂ / W₁, H₂ / H₁en ve boyun kaç kat değiştiği
i₂ / i₁i₂ / i₁renk derinliklerinin oranı — paletlerin oranı değil!

Palet 2ᵏ kat küçülünce renk derinliği k bit azalır; boyut ise 2ᵏ kat değil, i₁ / (i₁ − k) kat azalır.

Ses ve video bilgisinin kodlanması

Derse git

V = f · i · t · k

burada:

Vses dosyasının boyutu (bit)
förnekleme frekansı (Hz)
ibit derinliği (bit)
tkaydın süresi (s)
kkanal sayısı: mono 1, stereo 2

Aslında bu, “ölçüm sayısı × bir ölçümün biti” formülüdür: her biri i bit olan f · t · k ölçüm.

V = W · H · i · n · t

burada:

W · H · ibir karenin boyutu (bit), raster görüntüdeki gibi
nkare hızı (kare/s)
tvideonun süresi (s)

Ses kanalı varsa onun f · i · t · k boyutu da eklenir. Formül sıkıştırılmamış videonun boyutunu verir.

k = V₀ / Vk = V₀ / V

burada:

ksıkıştırma oranı — dosya kaç kat küçüldü
V₀sıkıştırmadan önceki boyut
Vsıkıştırılmış dosyanın boyutu

Akışla iletilen ses ve video için boyutlar yerine bit/s cinsinden hızlar da karşılaştırılabilir.

4Sayı sistemleri ve mantıkOrta

Sayı sistemleri: konumsal sistemler ve ikilik sistem

Derse git

N = aₖ·bᵏ + aₖ₋₁·bᵏ⁻¹ + … + a₁·b + a₀

burada:

Nsayının onluk sistemdeki değeri
bsistemin tabanı (b ≥ 2)
aᵢi. basamaktaki rakam, 0 ≤ aᵢ ≤ b − 1
ken yüksek basamağın sırası: basamak sayısı − 1

Sayının çözümlenmesi. Basamaklar sağdan sola 0’dan başlayarak numaralanır. Bu toplamı hesaplamak, herhangi bir tabandan onluk sisteme dönüşüm demektir.

Nₘₐₓ = bᵏ − 1, Nₘᵢₙ = bᵏ⁻¹

burada:

kbasamak sayısı
btaban

b tabanında en büyük ve en küçük k basamaklı sayılar. Bu tür sayıların adedi bᵏ − bᵏ⁻¹ = (b − 1)·bᵏ⁻¹’dir.

N = b·q + r, 0 ≤ r ≤ b − 1

burada:

qtam bölüm
rkalan — sayının b tabanındaki son rakamı

Bölme yöntemi her taban için çalışır: b’ye böleriz. Kısa bir sonuç: 0 ile biten ikilik sayı çift, 1 ile biten tektir.

2ⁿ = 100…0₂ (1 ve n sıfır), 2ⁿ − 1 = 11…1₂ (n tane 1)

burada:

nüs

0’ların sayısı = basamak sayısı − 1’lerin sayısı. Örneğin 2⁹ − 1 = 511 = 111111111₂ — dokuz tane 1.

2ᵏ⁻¹ ≤ N < 2ᵏ

burada:

Nbir doğal sayı
kN’nin ikilik yazılışındaki basamak sayısı

Bu koşul sağlanıyorsa N ikilikte tam k basamaklıdır. Örneğin 512 ≤ 1000 < 1024 olduğu için 1000 = 1111101000₂ on basamaklıdır.

Sekizlik ve on altılık sayı sistemleri

Derse git

N = aₖ·8ᵏ + … + a₂·64 + a₁·8 + a₀, 0 ≤ aᵢ ≤ 7

burada:

Nsayının onluk değeri
aᵢi. basamaktaki sekizlik rakam

Sekizlik sayının çözümlenmesi. Ters yönde 8’e bölünür; kalan son rakamdır.

N = aₖ·16ᵏ + … + a₂·256 + a₁·16 + a₀, 0 ≤ aᵢ ≤ 15

burada:

aᵢon altılık rakam: 0–9 ya da A = 10, …, F = 15

On altılık sayının çözümlenmesi. Onluktan dönüşümde 16’ya bölünür; 10–15 kalanları tek bir harfle yazılır.

b = 2ᵐ ⇒ b tabanında 1 rakam = m bit: 8 = 2³ → 3 bit, 16 = 2⁴ → 4 bit

burada:

mbir rakama düşen bit sayısı

Aynı kural 4 = 2² için de geçerlidir: 4 tabanında bitler ikişer ikişer gruplanır.

n bit → ⌈n/3⌉ sekizlik basamak, ⌈n/4⌉ on altılık basamakn bit → ⌈n/3⌉ sekizlik basamak, ⌈n/4⌉ on altılık basamak

burada:

nikilik basamak sayısı
⌈x⌉x’ten küçük olmayan en küçük tam sayı

n, 4’e (3’e) bölünüyorsa yuvarlamaya gerek yoktur: 2²⁴ bit → 2²⁴ : 2² = 2²² on altılık basamak.

Farklı sayı sistemlerinde aritmetik işlemler

Derse git

s = q·b + r → basamağa r yazılır, q bir sonraki basamağa aktarılır

burada:

sbasamaktaki rakamların ve eldenin toplamı
btaban
ryazılan rakam, 0 ≤ r ≤ b − 1
qelde

Toplamada s ≤ 2(b − 1) + 1 olduğu için elde her zaman 0 ya da 1’dir; çarpmada q daha büyük olabilir.

a < c ise: rakam = a + b − c, soldaki basamak 1 azalır

burada:

aeksilenin rakamı
cçıkanın rakamı
btaban

İkilikte en sık görülen durum: 10₂ − 1₂ = 1₂, yani 2 − 1 = 1.

N·bᵏ: sağa k sıfır eklenir; N : bᵏ: son k rakam atılır ve kalanı gösterir

burada:

Nb tabanında yazılmış bir sayı
kkaydırma (basamak sayısı)

Onluktaki 37·100 = 3700 kuralının genel biçimi. İkilikte 2 ile çarpmak bir basamak sola, 2’ye bölmek bir basamak sağa kaydırmaktır.

saklanan sonuç = (a + c) mod 2ⁿ

burada:

a, ctoplanan sayılar (işaretsiz tam sayılar)
nhücredeki bit sayısı
modbölümden kalan

Toplam 2ⁿ − 1’den büyük değilse taşma olmaz ve sonuç doğrudur.

Sayı sistemleri: tabanı bilinmeyen problemler

Derse git

aₖ…a₁a₀ₓ = aₖ·xᵏ + … + a₁·x + a₀, x > en büyük rakam

burada:

xbilinmeyen taban — bir doğal sayı, x ≥ 2
aᵢsayının rakamları

Rakam koşulu: taban, eşitlikteki bütün rakamlardan büyük olmalıdır. Denklemin bu koşulu sağlamayan kökleri atılır.

N = b·q + r, 0 ≤ r < b ⟹ b | (N − r), b > r

burada:

rN’nin b tabanındaki son rakamı (kalan)
b | MM sayısı b’ye kalansız bölünür

Son rakam = N’nin tabana bölümünden kalan.

bᵏ⁻¹ ≤ N < bᵏ

burada:

kN’nin b tabanındaki basamak sayısı

Bu çift eşitsizliği sağlayan bütün b ≥ 2 doğal tabanları seçilir.

mm…mₙ (k basamak) = nᵏ − 1, m = n − 1

burada:

ntaban
msistemin en büyük rakamı

Örneğin mmₙ = (n − 1)·n + (n − 1) = n² − 1: 77₈ = 63, 66₇ = 48.

2ⁿ − 2ᵐ = 11…1 00…0₂ (n − m tane 1, m tane 0), n > m

burada:

n, müsler

Örneğin 2⁸ − 2³ = 256 − 8 = 248 = 11111000₂: beş tane 1, üç tane 0.

(2ᵃ + 2ᶜ)² = 2²ᵃ + 2ᵃ⁺ᶜ⁺¹ + 2²ᶜ, a − c ≥ 2

burada:

a, cüsler, a > c

a − c ≥ 2 olduğunda üç kuvvet farklıdır; bu yüzden karenin ikilik yazılışında tam üç tane 1 vardır, basamak sayısı 2a + 1’dir.

5ModellemeOrta

Modeller ve modelleme

Derse git

S = S₀ · (1 + p/100)ⁿS = S₀ · (1 + p/100)ⁿ

burada:

S₀başlangıç tutarı (manat)
pbankanın yıllık faiz oranı (%)
nyıl sayısı
Sn yıl sonra hesaptaki tutar

Banka mevduatının matematiksel modeli: tutar her yıl (1 + p/100) katına çıkar.

h = h₀ − g · t² / 2h = h₀ − g · t² / 2

burada:

h₀başlangıç yüksekliği (m)
gyer çekimi ivmesi, ≈ 9,8 m/s²
tdüşme başladıktan sonra geçen süre (s)
ht anındaki yükseklik (m)

Serbest düşmenin dinamik modeli; varsayım: hava direnci ihmal edilir.

Tablo bilgi modeli: mantık problemlerinin tabloyla çözümü

Derse git

n · (n − 1) / 2n · (n − 1) / 2

burada:

nnesne (köy, takım) sayısı

n nesnenin farklı çiftlerinin sayısı: simetrik tabloda tam bu kadar farklı sayı gerekir; sıfırdan farklı hücreler ise iki katıdır, n · (n − 1).

her satırda tam bir «+» · her sütunda tam bir «+»

Bire bir eşleme kuralı: n × n tabloda sonunda n tane «+» ve n · (n − 1) tane «–» olur.

satır toplamlarının toplamı = sütun toplamlarının toplamı = «+» işaretlerinin sayısı

Kontrol toplamı: 6 kişinin her biri 2 eşya aldıysa sütun toplamları da 6 · 2 = 12 etmelidir.

(a₁ + a₂ + … + aₙ) / n(a₁ + a₂ + … + aₙ) / n

burada:

a₁, …, aₙsayılar (sayfa sayıları, puanlar)
nsayıların adedi

Aritmetik ortalama. Onu bulup hangi nesneye ait olduğunu belirlemek, sıralama probleminin çoğu zaman ilk adımıdır.

Ağaç bilgi modeli

Derse git

m = n − 1

burada:

nağacın düğüm sayısı
mkenar (dal) sayısı

Kök dışındaki her düğüm ebeveynine tam bir kenarla bağlanır; bu yüzden kenar sayısı düğüm sayısından bir eksiktir.

disk:\klasör₁\klasör₂\…\ad.uzantı

burada:

disk:\diskin kök klasörü, örneğin C:\
klasör₁ … klasörₖkökten dosyaya giden yoldaki klasörler, yukarıdan aşağıya
ad.uzantıdosyanın adı ve uzantısı

Dosyanın tam adı: kökten dosyaya giden tek yol.

n = 1 + k + k² + … + kʰ, yarpaqlar = kʰ

burada:

kher iç düğümün çocuk sayısı (hepsinde aynı)
hağacın yüksekliği; bütün yapraklar h seviyesinde
ntoplam düğüm sayısı

Dolu ağaç: her seviyede düğüm sayısı k katına çıkar. k = 2 için n = 2ʰ⁺¹ − 1.

Graf bilgi modeli: komşuluk matrisi ve yol sayısı

Derse git

deg(A₁) + deg(A₂) + … + deg(Aₙ) = 2 · m

burada:

deg(Aᵢ)i. köşenin derecesi
mkenar sayısı

«Tokalaşma» kuralı: her kenar iki köşeye aittir ve derecelerin toplamında iki kez sayılır. Demek ki derecelerin toplamı her zaman çifttir.

m = n · (n − 1) / 2m = n · (n − 1) / 2

burada:

nköşe sayısı
mtam grafta kenar sayısı

Tam graf: her iki köşe birbirine bağlıdır (örneğin her takım her takımla bir kez oynar).

yönsüz graf: N₁ = 2 · m yönlü graf: N₁ = m

burada:

N₁komşuluk matrisindeki 1’lerin sayısı
mkenar (ok) sayısı

Yönlü grafta X → Y oku yalnızca tek bir hücrede, X satırı ile Y sütununun kesiştiği yerde 1 verir; böyle bir matris genellikle simetrik değildir.

N(X) = N(Y₁) + N(Y₂) + … + N(Yₖ), N(A) = 1

burada:

N(X)A’dan X’e giden farklı yolların sayısı
Y₁, …, YₖX’e ok (doğrudan yol) gönderen bütün köşeler

Başlangıç köşesine 1 yazılır; her köşenin sayısı, ona gelen okların başladığı köşelerdeki sayıların toplamıdır.

N(A → K, D-dən keçməklə) = N(A → D) · N(D → K)

burada:

N(A → D)A’dan D’ye giden yol sayısı
N(D → K)D’den K’ye giden yol sayısı (D’ye 1 yazıp yeniden sayılır)

Belirli bir köşeden geçen yollar: ilk kısmın her seçeneği ikinci kısmın her seçeneğiyle birleşir, bu yüzden sayılar çarpılır.

6AlgoritmalarOrta

Algoritma, özellikleri ve gösterim biçimleri

Derse git

değişken = ifade

burada:

değişkenyeni değerin yazıldığı yer; eski değer silinir
ifadedeğişkenlerin o anki değerleriyle hesaplanır

Atama kuralı: önce sağ taraf hesaplanır, sonra sonuç soldaki değişkene yazılır

Dallanan algoritmalar

Derse git

D = b² − 4·a·c

burada:

Ddiskriminant: D > 0 — iki kök, D = 0 — bir kök, D < 0 — gerçek kök yok
a, b, ca·x² + b·x + c = 0 denkleminin katsayıları (a ≠ 0)

Üç durumu iki eşkenar dörtgen ayırır: önce D > 0, sonra D = 0

(yıl % 4 = 0 ve yıl % 100 ≠ 0) veya yıl % 400 = 0

burada:

%bölümden kalan; “yıl % 4 = 0”, yılın 4’e bölündüğü anlamına gelir
≠eşit değil

Gregoryen takviminde artık yıl (366 gün) kuralı; bileşik koşulun klasik örneği

Döngülü algoritmalar ve izleme tablosu

Derse git

S = S + x; P = P · x; k = k + 1

burada:

Stoplam; başlangıç değeri 0
Pçarpım; başlangıç değeri 1 (0 olsaydı hep 0 kalırdı)
ksayı (sayaç); başlangıç değeri 0

Döngünün üç “biriktirici” değişkeni ve başlangıç değerleri

r = n % 10, n = n // 10

burada:

n % 10sayının son basamağı (10’a bölümden kalan)
n // 10son basamağı atılmış sayı (tam bölme)

Basamaklar üzerinde döngü: n > 0 olduğu sürece son basamağı al ve at

a₀ + p·k ≥ b₀ − q·k ⇒ k = ⌈(b₀ − a₀) / (p + q)⌉a₀ + p·k ≥ b₀ − q·k ⇒ k = ⌈(b₀ − a₀) / (p + q)⌉

burada:

a₀, b₀değişkenlerin başlangıç değerleri (a₀ < b₀)
p, qher adımda a’nın artışı ve b’nin azalışı
k“a < b” döngüsünün tekrar sayısı
⌈ ⌉yukarı yuvarlama: 10,875 → 11

Döngü ilk kez a ≥ b olunca durur: aradaki fark her adımda p + q kadar azalır

Akış şeması oluşturma: yazılı sorular

Derse git

S = 1 − 1/3 + 1/5 − 1/7 + … , aᵢ = k / (2·i − 1), k = −kS = 1 − 1/3 + 1/5 − 1/7 + … , aᵢ = k / (2·i − 1), k = −k

burada:

iterimin numarası, 1’den N’ye kadar
2·i − 1i. terimin paydası: 1, 3, 5, 7, …
kişaret: 1’den başlar ve her adımda −k olur (1, −1, 1, …)

İşareti değişen dizinin genel terimi: işaret ayrı bir değişkende tutulur

y = 2·x + 5, x < 3 ise; y = x² − 4, x ≥ 3 ise

burada:

xdöngünün her adımında girilen tam sayı
yfonksiyonun değeri: eşkenar dörtgen iki formülden birini seçer

Görev: n sayı için y’leri hesaplayıp 20’den büyük olanların toplamını yazdırın

Sıralama algoritmaları

Derse git

K = n(n − 1) / 2K = n(n − 1) / 2

burada:

Ken kötü durumda karşılaştırma sayısı
nlistedeki eleman sayısı

7Python ile programlama (okul dersi)Orta

Programlama dilleri ve Python: değişkenler, veri girişi ve çıkışı

Derse git

a = b · (a // b) + a % b, 0 ≤ a % b < b

burada:

abölünen (tam sayı)
bbölen, b > 0
a // bbölüm
a % bkalan

Kalanlı bölme: // ve % her zaman birlikte çalışır. Kontrol: bölümü bölenle çarpıp kalanı eklersen bölüneni bulmalısın.

( ) → ** → * / // % → + −2 ** 3 ** 2 = 2 ** 9 = 512

İşlem önceliği (soldan sağa azalır). Aynı düzeydeki * / // % işlemleri soldan sağa, ** ise sağdan sola yapılır: 2 ** 3 ** 2 = 2 ** 9 = 512. **, baştaki eksi işaretinden güçlüdür: -2 ** 2 = −4.

n = 100·a + 10·b + c ⇒ a = n // 100, b = n // 10 % 10, c = n % 10

burada:

nüç basamaklı doğal sayı
ayüzler basamağı
bonlar basamağı
cbirler (son) basamağı

n % 10 her zaman son basamağı, n // 10 ise son basamağı atılmış sayıyı verir. Her uzunluktaki sayının basamakları döngülerle «Sayılar üzerinde işlemler: rakamlar, bölenler ve asal sayılar» dersinde işlenir.

Koşul ifadesi: if, elif, else ve bileşik koşullar

Derse git

aritmetik → == != < > <= >= → not → and → or

Öncelik soldan sağa azalır: önce aritmetik, sonra karşılaştırmalar, ardından not, and ve en son or. Emin değilsen parantez kullan; program hem doğru hem okunaklı olur.

Döngüler: for, while, döngü adımı, break, continue ve iç içe döngüler

Derse git

N = ⌈(b − a) / d⌉N = ⌈(b − a) / d⌉

burada:

Nyineleme sayısı; ifade 0 veya negatifse döngü hiç çalışmaz
abaşlangıç değeri
bbitiş değeri (dâhil değil)
dadım (negatif olabilir)
⌈x⌉x’in yukarıya, en yakın tam sayıya yuvarlanması

range(a, b, d) için yineleme sayısı. Döngü değişkeninin son değeri a + (N − 1) · d’dir. Adım 1 ise kısaca N = b − a; [a, b] aralığındaki tüm tam sayılar için range(a, b + 1) yazılır ve N = b − a + 1 olur.

K = b // m − (a − 1) // m

burada:

K[a, b] aralığında m’ye bölünen doğal sayıların sayısı
a, baralığın uçları (doğal sayılar)
mbölen

Döngüsüz sayma: [1, b] aralığında m’nin b // m katı vardır; [1, a − 1] aralığındakileri çıkarırız. Büyük aralıklardaki döngüleri izlemek yerine tam olarak böyle sayarız.

N = N₁ · N₂

burada:

Niç gövdenin toplam çalışma sayısı
N₁dış döngünün yinelemeleri
N₂iç döngünün bir geçişteki yinelemeleri

İç döngü dıştaki değişkene bağlı değilse çarpım kuralı işler. Bağlıysa her dış yineleme için iç sayıyı ayrı bulup toplarız.

Sayılar üzerinde işlemler: rakamlar, bölenler ve asal sayılar

Derse git

d = n % 10 n = n // 10

burada:

dson rakam (0…9)
%bölümden kalan
//tam bölme: kesirli kısım atılır, sayı bir basamak kısalır

Rakam döngüsünün iki temel komutu. Döngü while n > 0: koşuluyla çalışır.

n // pow(10, k) % 10 n % pow(10, k) n // pow(10, k)

burada:

n // pow(10, k) % 10sağdan k'nci rakam (k = 0 — birler, 1 — onlar, 2 — yüzler)
n % pow(10, k)son k rakamdan oluşan sayı
n // pow(10, k)son k rakam atıldıktan sonra kalan sayı

Herhangi bir rakam döngüsüz de alınabilir: 5682 // 100 % 10 = 6, 5682 % 100 = 82, 5682 // 1000 = 5.

r = r * 10 + n % 10

burada:

rters sayı; başlangıçta r = 0
n % 10sıradaki son rakam

Ters sayı: 5682 için r = 2, 28, 286, 2865. Palindrom testi: döngüden sonra r == m (m, başlangıçtaki sayının kopyası).

a * pow(10, c) + n n * 10 + a

burada:

cn'nin basamak sayısı (rakam döngüsünün sayacı)
aeklenen rakam

a rakamını sayının başına ve sonuna yazmak.

n % i == 0, i = 1, 2, …, n

burada:

idenenen aday bölen
c == 2bölen sayısı 2 ise n asaldır

Bölen döngüsü: for i in range(1, n + 1): ve içinde if n % i == 0:.

pow(a, 0.5) == int(pow(a, 0.5))

burada:

pow(a, 0.5)a'nın karekökü, ondalıklı sayı (49 ** 0.5 → 7.0)
int(…)kesirli kısmı atar

Kök tam sayıysa a tam karedir. DİM çözümlerinde a ** (1/2) yazımı da geçer; ikisi aynıdır.

EBOB(a, b) = EBOB(b, a % b), EBOB(a, 0) = a

burada:

a % ba'nın b'ye bölümünden kalan
b = 0kalan 0 olunca dururuz: cevap a'dır

Öklid algoritması. Ders kitaplarında çıkarma yöntemi de vardır: sayılar eşitlenene kadar büyükten küçüğü çıkar.

EKOK(a, b) = a · b / EBOB(a, b)EKOK(a, b) = a · b / EBOB(a, b)

burada:

a · biki sayının çarpımı

En küçük ortak kat EBOB'dan hemen bulunur.

S = 1 + 1/2 + 1/3 + … + 1/n n! = 1 · 2 · 3 · … · nS = 1 + 1/2 + 1/3 + … + 1/n n! = 1 · 2 · 3 · … · n

burada:

s = s + 1 / is = s + 1 / itoplamın döngüdeki kalıbı
p = p * ifaktöriyelin kalıbı (başlangıçta p = 1)

i döngü değişkenidir: for i in range(1, n + 1):.

Program analizi: çıktıdan girdiye

Derse git

n = n₀ + k · d s = s₀ · qᵏ

burada:

n₀, s₀döngüden önceki değerler
dher adımda eklenen sayı (n = n + d)
qher adımda çarpılan sayı (s = s * q)
ktekrar sayısı

Toplama aritmetik, çarpma ise geometrik dizi verir.

koşul(x₍ₖ₋₁₎) doğru, koşul(xₖ) yanlış

burada:

xₖdöngü değişkeninin k tekrardan sonraki değeri, girdiyle ifade edilir (örneğin s₀ + k · m)

Döngünün tam k kez çalışmasının koşulu.

x // q = y ⇔ q · y ≤ x ≤ q · y + q − 1

burada:

qbölen (a = a // q)
ytam bölmenin sonucu

Tam bölmede geri adım: en küçük x = q · y, en büyük x = q · y + q − 1.

sayı = R − L + 1 1 + 2 + … + k = k(k + 1) / 2sayı = R − L + 1 1 + 2 + … + k = k(k + 1) / 2

burada:

L, Ruygun en küçük ve en büyük girdi
k(k + 1) / 2k(k + 1) / 2ilk k pozitif tam sayının toplamı

Bir aralıktaki tam sayıların sayısı ve artan adımlı toplam.

Karakter dizileri ve üzerlerinde işlemler

Derse git

s[i] s[-1] = s[len(s) - 1]

burada:

s[i]i indisli karakter (kendisi de bir dizidir)
len(s)karakter sayısı; son indis len(s) − 1'dir

s[len(s)] hata verir (IndexError): böyle bir indis yoktur.

s[a:b:c]

burada:

abaşlangıç indisi (dahil); yazılmazsa baştan
bbitiş indisi (dahil değil); yazılmazsa sona kadar
cadım; yazılmazsa 1; negatif adım sağdan sola gider

Dilim a'dan b − 1'e kadar c adımla gider. s[::-1] ters dizidir; c = 1 iken dilimde b − a karakter olur.

NBa = (Dkod + 2 · Dyazılı) · 100 / 33NBa = (Dkod + 2 · Dyazılı) · 100 / 33

burada:

NBaaçık uçlu görevlerin göreli puanı
Dkoddoğru kodlanan cevapların sayısı (0–5)
Dyazılıyazılı görevlere verilen puanların toplamı (0–3)

Kapalı bölüm buna 100/33 · (Dq − Yq/4) ekler; ders için en yüksek puan 100'dür. Yazılı bir görev, iki kodlanan görev kadar ağırlığa sahiptir.

8Veri tabanlarıİleri

Veri tabanı: modeller, VTYS ve ilişkili tablolar

Derse git

Veri tabanında sorgular, arama ve sıralama

Derse git

M(A AND B) = M(A) ∩ M(B)

burada:

M(A)A koşulunu sağlayan kayıtların numaraları
∩kesişim: iki kümede de olanlar

AND — iki koşul da sağlanmalıdır: ortak numaralar kalır.

M(A OR B) = M(A) ∪ M(B)

burada:

∪birleşim: en az bir kümede olanlar

OR — en az bir koşul sağlanmalıdır: numaralar tekrar yazılmadan birleştirilir.

M(NOT A) = U \ M(A)

burada:

Utablonun tüm kayıtları
\fark: U’dan M(A)’yı çıkarırız

NOT — koşulu sağlamayan kayıtlar kalır.

NOT (A AND B) = (NOT A) OR (NOT B) · NOT (A OR B) = (NOT A) AND (NOT B)

burada:

A, Bherhangi koşullar

De Morgan kuralları: NOT parantezin içine girince AND ile OR yer değiştirir.

9Ağlar, internet ve bilgi güvenliğiİleri

İnternette arama: arama motorları ve sorgular

Derse git

n(A OR B) = n(A) + n(B) − n(A AND B)

burada:

n(A), n(B)A ve B sorgularında bulunan sayfa sayıları
n(A AND B)iki sözcüğün de geçtiği sayfaların sayısı
n(A OR B)sözcüklerden en az birinin geçtiği sayfaların sayısı

İki küme için içerme-dışlama ilkesi. Dört niceliğin üçü biliniyorsa dördüncüsü bulunur.

n(A AND NOT B) = n(A) − n(A AND B)

burada:

n(A AND NOT B)A’nın geçip B’nin geçmediği sayfaların sayısı

A dairesinden ortak kısım çıkarılır, B’nin tamamı değil!

n(A OR B OR C) = n(A) + n(B) + n(C) − n(A AND B) − n(A AND C) − n(B AND C) + n(A AND B AND C)

burada:

n(A AND B AND C)üç sözcüğün de geçtiği sayfaların sayısı (merkez, 7. parça)

Üç küme için içerme-dışlama ilkesi: ikili kesişimler çıkarılınca merkez üç kez çıkarılmış olur, bu yüzden bir kez geri eklenir.

Siber güvenlik: parolalar, oltalama ve gizlilik

Derse git

C = Aᴸ

burada:

Colası parola sayısı
Aalfabenin büyüklüğü: kullanılabilecek farklı karakter sayısı
Lparolanın uzunluğu (karakter sayısı)

İlk dersteki N = 2ⁱ formülü bunun özel bir hâlidir: orada alfabede yalnızca 2 sembol (0 ve 1) vardı.

Bilginin korunması ve kriptografi

Derse git

y = (x + k) mod n

burada:

xaçık metindeki harfin numarası
yşifreli metindeki harfin numarası
kanahtar — kaydırma miktarı
nalfabedeki simge sayısı (26, 32 ya da 10)
mod nn’ye bölümden kalan: alfabenin “başa dönmesi”

Şifreleme: k sıra sağa.

x = (y − k) mod n

Şifre çözme: k sıra sola. Negatif bir sayı çıkarsa n ekleyin: örneğin (1 − 3) mod 26 = −2 + 26 = 24.

k = (y − x) mod n; k = (k₁ + k₂) mod n

burada:

x, ybirbirine karşılık gelen açık metin ve şifreli metin harflerinin numaraları
k₁, k₂art arda iki şifrelemenin anahtarları

Anahtarı bulmak için tek harf yeter; iki kaydırma toplanır. k sola kaydırma, n − k sağa kaydırmadır.

10Web programlamaİleri

Web programlama: site hazırlama, HTML etiketleri ve listeler

Derse git

HTML’de tablolar, renk şeması, resimler ve bağlantılar

Derse git

N = 256 · 256 · 256 = 2²⁴ = 16 777 216

burada:

#RRGGBBrenk kodu: üç on altılık çift — kırmızı, yeşil, mavi
256bir çiftin değer sayısı: 00…FF = 0…255
Nyazılabilen renk sayısı

Her renk 3 bayt = 24 bitle kodlanır; raster grafikteki True Color ile aynıdır.

h₂ = h₁ · w₂ / w₁h₂ = h₁ · w₂ / w₁

burada:

w₁, h₁resmin kendi genişliği ve yüksekliği (piksel)
w₂width niteliğinde yazılan genişlik
h₂tarayıcının gösterdiği yükseklik

Yalnızca width (ya da yalnızca height) verilirse tarayıcı oranları korur.

11Algoritmalar ve veri yapılarıÜniversite

Algoritma karmaşıklığı ve Büyük O gösterimi

Derse git

1 + 2 + … + (n − 1) = n(n − 1) / 21 + 2 + … + (n − 1) = n(n − 1) / 2

burada:

ngirdi boyutu (eleman sayısı)

Gauss toplamı: “her eleman diğer her elemanla bir kez” türündeki iç içe döngülerin işlem sayısı.

f(n) = O(g(n)) ⇔ ∃ c > 0, ∃ n₀: 0 ≤ f(n) ≤ c · g(n) ∀ n ≥ n₀

burada:

f(n)algoritmanın işlem sayısı
g(n)karşılaştırma fonksiyonu (n, n², n log n …)
cpozitif bir sabit
n₀eşitsizliğin sağlandığı başlangıç boyutu

f(n) = Ω(g(n)) ⇔ ∃ c > 0, n₀: f(n) ≥ c · g(n) ∀ n ≥ n₀; f(n) = Θ(g(n)) ⇔ f = O(g) ve f = Ω(g)

Ω alt sınırdır; Θ hem üst hem alt sınırdır (iki sabit arasında “sıkışma”).

T(n) = 2T(n/2) + cn ⇒ T(n) = cn · log₂ n + n · T(1) = Θ(n log n)T(n) = 2T(n/2) + cn ⇒ T(n) = cn · log₂ n + n · T(1) = Θ(n log n)

burada:

T(n)n elemanlı girdide çalışma süresi
2T(n/2)2T(n/2)iki yarının özyinelemeli işlenmesi
cnbölme ve birleştirme işi (doğrusal)

Özyineleme ağacı: k. düzeyde n/2ᵏ boyutlu 2ᵏ alt problem vardır; düzeyin toplam işi 2ᵏ · c · n/2ᵏ = cn olur. log₂ n düzey olduğundan toplam cn · log₂ n'dir.

T(n) = a · T(n/b) + Θ(nᵈ)T(n) = a · T(n/b) + Θ(nᵈ)

burada:

aözyinelemeli çağrı sayısı (a ≥ 1)
bboyutun kaç kat küçüldüğü (b > 1)
dbölme ve birleştirme işinin üssü (d ≥ 0)

Ana teorem (sadeleştirilmiş biçim): a ile bᵈ'yi karşılaştır. a < bᵈ → Θ(nᵈ); a = bᵈ → Θ(nᵈ · log n); a > bᵈ → Θ(nᵖ), burada p = log a / log b.

Diziler, bağlı listeler, yığıtlar ve kuyruklar

Derse git

addr(A[i]) = base + i · s

burada:

basedizinin başlangıç adresi (A[0]'ın adresi)
ieleman indeksi (0'dan başlar)
sbir elemanın boyutu, bayt

İndekslerin 0'dan başlamasının nedeni de budur: i, elemanın başlangıçtan kaç adım uzakta olduğunu gösterir.

(n + 1 + 2 + 4 + … + 2ᵏ) / n < (n + 2n) / n = 3, 2ᵏ < n(n + 1 + 2 + 4 + … + 2ᵏ) / n < (n + 2n) / n = 3, 2ᵏ < n

burada:

neklenen eleman sayısı
1 + 2 + … + 2ᵏtüm büyütmelerde kopyalanan eleman sayısı (< 2n)

Amortize maliyet: n eklemenin toplam işi 3n'den azdır; yani ara sıra yapılan “pahalı” büyütmelere rağmen bir ekleme ortalama O(1)'dir.

tail = (head + size) mod m, next(i) = (i + 1) mod m

burada:

headkuyruğun ilk elemanının indeksi
sizekuyruktaki eleman sayısı
mdizinin kapasitesi
tailsonraki elemanın yazılacağı indeks

Hash tabloları

Derse git

h(s) = (s₀ · pᵏ⁻¹ + s₁ · pᵏ⁻² + … + sₖ₋₁ · p⁰) mod m

burada:

s₀ … sₖ₋₁metnin karakterlerinin sayısal kodları
ptaban (genellikle 31 gibi küçük bir asal sayı)
kmetnin uzunluğu
mkova sayısı

Polinom hash hem karakterlere hem de sıralarına bağlıdır: “ab” ile “ba” farklı hash değerleri alır.

P(çakışma yok) ≈ e^(−k(k − 1) / (2m))

burada:

kyerleştirilen anahtar sayısı
mkova sayısı

m = 365, k = 23: k(k − 1)/2 = 253, 253/365 ≈ 0,693, e^(−0,693) ≈ 0,5. Çakışmaların başlaması için yaklaşık √m anahtar yeterlidir.

α = n / mα = n / m

burada:

αdoluluk oranı (yük faktörü)
ntablodaki anahtar sayısı
mkova sayısı

Zincirlemede α ortalama zincir uzunluğudur ve 1'i aşabilir; açık adreslemede her zaman α < 1'dir.

E(zincirleme) = 1 + α; E(doğrusal sondalama) ≈ ½ · (1 + 1 / (1 − α)²)E(zincirleme) = 1 + α; E(doğrusal sondalama) ≈ ½ · (1 + 1 / (1 − α)²)

burada:

Ebaşarısız aramada (anahtar yok) beklenen sondalama sayısı

Düzgün dağılan bir hash varsayımıyla. Doğrusal sondalama formülü Knuth'un analizinden gelir; α → 1 iken sondalama sayısı hızla artar.

Ağaçlar ve yığınlar (heap)

Derse git

n ≤ 2ʰ⁺¹ − 1 ⇒ h ≥ ⌈log₂(n + 1)⌉ − 1 ≈ log₂ n

burada:

ndüğüm sayısı
hağacın yüksekliği (kenar sayısıyla)

d derinliğinde en fazla 2ᵈ düğüm olabilir: 1 + 2 + 4 + … + 2ʰ = 2ʰ⁺¹ − 1. Yani n düğümlü bir ikili ağacın yüksekliği yaklaşık log₂ n'den küçük olamaz, ama n − 1'e kadar büyük olabilir.

left(i) = 2i + 1, right(i) = 2i + 2, parent(i) = ⌊(i − 1) / 2⌋left(i) = 2i + 1, right(i) = 2i + 2, parent(i) = ⌊(i − 1) / 2⌋

burada:

idüğümün dizideki indeksi (0'dan)

Ağaç diziye düzey düzey yazılır; tam olduğu için boşluk kalmaz ve yüksekliği ⌊log₂ n⌋'dir.

T(build-heap) ≤ ∑ₕ (n / 2ʰ⁺¹) · h = (n/2) · ∑ₕ h / 2ʰ ≤ (n/2) · 2 = n = O(n)T(build-heap) ≤ ∑ₕ (n / 2ʰ⁺¹) · h = (n/2) · ∑ₕ h / 2ʰ ≤ (n/2) · 2 = n = O(n)

burada:

hdüğümün yapraklardan yüksekliği
n / 2ʰ⁺¹n / 2ʰ⁺¹yüksekliği h olan düğüm sayısı (yaklaşık)

heapify bir diziyi aşağıdan yukarıya yığına çevirir: düğümlerin yarısı yapraktır (0 iş), dörtte biri 1 adım batar vb. ∑ h/2ʰ = 2 olduğundan toplam O(n log n) değil O(n)'dir. Yığın sıralaması ardından n çıkarmayla O(n log n) yapar.

Graflar ve graf algoritmaları

Derse git

∑ deg(v) = 2|E|, |E| ≤ |V| · (|V| − 1) / 2∑ deg(v) = 2|E|, |E| ≤ |V| · (|V| − 1) / 2

burada:

deg(v)v köşesinin derecesi
|V|, |E|köşe ve kenar sayıları

“El sıkışma önermesi”: her yönsüz kenar derece toplamına iki uçta birer olmak üzere 2 ekler. İkinci eşitsizlik, basit yönsüz bir grafta en fazla kenar sayısıdır.

dist[v] ← min(dist[v], dist[u] + w(u, v)); T = O((V + E) · log V)

burada:

dist[v]kaynaktan v'ye şimdiye kadar bulunan en kısa uzaklık
w(u, v)u–v kenarının ağırlığı (≥ 0)
Tikili yığınla çalışma süresi

Özyineleme ve dinamik programlama

Derse git

n! = n · (n − 1)!, 0! = 1

burada:

n · (n − 1)!özyinelemeli adım
0! = 1temel durum

T(n) = T(n − 1) + T(n − 2) + O(1) = Θ(φⁿ), φ = (1 + √5) / 2 ≈ 1,618T(n) = T(n − 1) + T(n − 2) + O(1) = Θ(φⁿ), φ = (1 + √5) / 2 ≈ 1,618

burada:

T(n)basit özyinelemeli fib(n)'in çalışma süresi
φaltın oran

Bellekleme ile her fib(k) bir kez hesaplanır: n + 1 alt problem × O(1) iş = O(n). Üstelden doğrusala!

dp[i][c] = max(dp[i − 1][c], dp[i − 1][c − wᵢ] + vᵢ), dp[0][c] = 0

burada:

dp[i][c]ilk i eşyayla c kapasitede elde edilen en büyük değer
wᵢ, vᵢi. eşyanın ağırlığı ve değeri (ikinci seçenek yalnızca wᵢ ≤ c iken)

Süre ve bellek O(n · W). Bu sözde polinom bir karmaşıklıktır: W'nin bit sayısına göre üsteldir.

L[i][j] = L[i − 1][j − 1] + 1, eğer aᵢ = bⱼ; aksi hâlde L[i][j] = max(L[i − 1][j], L[i][j − 1])

burada:

L[i][j]a'nın ilk i ve b'nin ilk j karakterinin LCS uzunluğu
L[0][j] = L[i][0]0 (boş metinle ortak hiçbir şey yok)

Süre O(m · n): uzunluğu 1000 olan iki metin için yalnızca 10⁶ hücre gerekir, oysa tüm alt dizileri denemek 2¹⁰⁰⁰ seçenek demektir.

coins[x] = 1 + min { coins[x − c] : c ≤ x }, coins[0] = 0

burada:

coins[x]x tutarını oluşturan en az bozuk para sayısı
ckullanılabilir bir bozuk para değeri

Verimli sıralama algoritmaları

Derse git

T(n) = 2T(n/2) + cn = Θ(n log n)T(n) = 2T(n/2) + cn = Θ(n log n)

burada:

2T(n/2)2T(n/2)iki yarının özyinelemeli sıralanması
cnbirleştirme (en fazla n − 1 karşılaştırma)

log₂ n düzeyin her birinde birleştirmeler toplam ≤ n karşılaştırma yapar → ≤ n log₂ n. Bu en kötü, ortalama ve en iyi durumda aynıdır. Ek bellek O(n)'dir; algoritma kararlıdır (eşit elemanlar sırasını korur).

en kötü durum: T(n) = T(n − 1) + (n − 1) = n(n − 1)/2; ortalama: ≈ 2n ln n ≈ 1,39 n log₂ nen kötü durum: T(n) = T(n − 1) + (n − 1) = n(n − 1)/2; ortalama: ≈ 2n ln n ≈ 1,39 n log₂ n

burada:

T(n − 1)pivot hep en küçük ya da en büyük olduğunda kalan parça
n − 1bir bölümlemenin karşılaştırma sayısı

Dengeli bölümlemelerde hızlı sıralama birleştirmeli sıralama gibi davranır: T(n) = 2T(n/2) + n → Θ(n log n); her seferinde en kötü bölümlemede ise Θ(n²).

h ≥ log₂(n!) ≥ log₂((n/2)^(n/2)) = (n/2) · log₂(n/2) = Ω(n log n)h ≥ log₂(n!) ≥ log₂((n/2)^(n/2)) = (n/2) · log₂(n/2) = Ω(n log n)

burada:

hen kötü durumda karşılaştırma sayısı (ağacın yüksekliği)
n!n elemanın olası dizilişlerinin sayısı

n!'in n/2'den büyük n/2 çarpanının her biri ≥ n/2 olduğundan n! ≥ (n/2)^(n/2). Stirling formülüyle daha kesin olarak log₂(n!) ≈ n log₂ n − 1,44n.

12Bilgisayar sistemleri ve kuramÜniversite

Bilgisayar mimarisi

Derse git

t = N · CPI / ft = N · CPI / f

burada:

tprogramın işlemci süresi, s
Nyürütülen komut sayısı
CPIkomut başına ortalama saat döngüsü
fsaat frekansı, Hz

İşlemci başarımının “temel denklemi”: hızlanmak için ya daha az komut (daha iyi algoritma ve derleyici), ya daha küçük CPI (boru hattı, önbellek) ya da daha yüksek frekans gerekir.

AMAT = t_hit + m · t_miss

burada:

AMATortalama bellek erişim süresi
t_hitönbellekte isabet olduğunda erişim süresi
mıskalama oranı
t_missıskalama cezası (bir sonraki düzeye gitmek)

−x = (NOT x) + 1; n bit: −2ⁿ⁻¹ … 2ⁿ⁻¹ − 1

burada:

NOT xx'in tüm bitlerinin tersine çevrilmesi
nbit sayısı (8 bit: −128 … 127)

x = (−1)ˢ · 1,m₂ · 2^(e − 127)

burada:

sişaret biti (1 bit)
ekaydırılmış üs (8 bit, sapma 127)
mmantisin kesir kısmı (23 bit; baştaki 1 yazılmaz)

32 bitlik (single) biçim. 64 bitlik double: 1 + 11 + 52 bit, sapma 1023, yaklaşık 15–16 ondalık basamak duyarlık. Python float'u bir double'dır.

İşletim sistemleri

Derse git

W = (1 / n) · ∑ (Cᵢ − Aᵢ − Bᵢ)W = (1 / n) · ∑ (Cᵢ − Aᵢ − Bᵢ)

burada:

Wortalama bekleme süresi
Cᵢi sürecinin bitiş anı
Aᵢgeliş anı
Bᵢişlemci patlaması uzunluğu (burst)

p = ⌊VA / P⌋, d = VA mod P, PA = frame(p) · P + dp = ⌊VA / P⌋, d = VA mod P, PA = frame(p) · P + d

burada:

VA, PAsanal ve fiziksel adres
Psayfa boyutu, bayt
p, dsayfa numarası ve sayfa içindeki kayma

P = 2ᵏ iken bölme yalnızca bitleri ayırmaktır: 4 KB = 2¹² sayfalarda alttaki 12 bit kayma, geri kalanı sayfa numarasıdır.

Bilgisayar ağları: derinlemesine

Derse git

N_host = 2^(32 − n) − 2, network = IP AND mask, broadcast = network OR (NOT mask)

burada:

nönek uzunluğu (/n)
N_hostcihazlara verilebilecek adres sayısı
maskn tane 1 ve 32 − n tane 0 (örneğin /26 → 255.255.255.192)

d = L / R + D / s; throughput_TCP ≤ W / RTTd = L / R + D / s; throughput_TCP ≤ W / RTT

burada:

L / RL / Riletim gecikmesi: paket boyutu L (bit) / hat hızı R (bit/s)
D / sD / syayılma gecikmesi: uzaklık D / sinyal hızı s (fiberde ≈ 2 · 10⁸ m/s)
W, RTTTCP pencere boyutu ve gidiş-dönüş süresi

Veri tabanı kuramı

Derse git

π[first_name](σ[city = 'Bakı'](students)) ≡ SELECT first_name FROM students WHERE city = 'Bakı'

burada:

σseçme (selection): koşulu sağlayan satırlar — WHERE
πizdüşüm (projection): gereken sütunlar — SELECT listesi
⋈birleştirme (join): iki ilişkiyi ortak nitelik üzerinden birleştirme — JOIN

h = ⌈log N / log f⌉h = ⌈log N / log f⌉

burada:

hB-ağacı indeksinin yüksekliği (aramada okunan sayfa sayısı)
Ntablodaki satır sayısı
fdallanma: bir sayfaya sığan anahtar sayısı

Hesaplama kuramı

Derse git

M = (Q, Σ, δ, q₀, F), δ: Q × Σ → Q

burada:

Qsonlu durumlar kümesi
Σgirdi alfabesi (örneğin {0, 1})
δgeçiş fonksiyonu
q₀, Fbaşlangıç durumu ve kabul eden durumlar kümesi

L düzenlidir ⇒ ∃ p: ∀ w ∈ L, |w| ≥ p: w = xyz, |xy| ≤ p, |y| ≥ 1, xyⁱz ∈ L ∀ i ≥ 0

burada:

ppompalama uzunluğu (otomatın durum sayısı)
yistenildiği kadar tekrarlanabilen ya da silinebilen boş olmayan parça

Pompalama önsavı: uzun bir dizgi otomatta bir durumdan mutlaka iki kez geçer (güvercin yuvası ilkesi) ve bu döngü istenildiği kadar tekrarlanabilir.

Yazılım mühendisliği

Derse git

C = n(n − 1) / 2C = n(n − 1) / 2

burada:

Cekipteki ikili iletişim kanalı sayısı
nekip üyesi sayısı

5 kişi → 10 kanal, 10 kişi → 45 kanal. Brooks yasası bununla açıklanır: geciken bir projeye insan eklemek onu çoğu zaman daha da geciktirir. Bu yüzden Scrum ekipleri küçük tutulur (genellikle 10 kişiye kadar).

M = E − N + 2P (= karar sayısı + 1)

burada:

MMcCabe'in döngüsel karmaşıklığı: bağımsız yol sayısı
E, Ndenetim akışı grafının kenarları ve düğümleri
Pbağlı bileşen sayısı (tek fonksiyon için 1)

M, tüm dalları kapsamak için gereken en az test sayısının iyi bir tahminidir. M > 10 olan fonksiyonlar genellikle daha küçük parçalara bölünür.

Kriptografi ve bilgi güvenliği

Derse git

C = E(K, M), M = D(K, C)

burada:

M, Cdüz metin ve şifreli metin
Kiki tarafta da bulunan aynı gizli anahtar
E, Dşifreleme ve şifre çözme algoritmaları (örneğin AES)

Kerckhoffs ilkesi: algoritma herkesçe bilinebilir; güvenlik yalnızca anahtarın gizliliğine dayanmalıdır.

A = gᵃ mod p, B = gᵇ mod p, s = Bᵃ mod p = Aᵇ mod p = gᵃᵇ mod p

burada:

p, gherkesçe bilinen asal sayı ve taban
a, btarafların gizli sayıları
sortak gizli anahtar — ağ üzerinden hiç gönderilmez

Diffie–Hellman anahtar değişimi: dinleyen kişi p, g, A ve B'yi görür ama s'yi bulmak için ayrık logaritma problemini çözmesi gerekir.

n = p · q, φ(n) = (p − 1)(q − 1), e · d ≡ 1 (mod φ(n)), c = mᵉ mod n, m = cᵈ mod n

burada:

p, qiki büyük gizli asal sayı (uygulamada her biri ≈ 1024 bit)
(n, e)açık anahtar
dözel anahtar: e'nin φ(n) modülüne göre tersi
m, cmesaj (0 ≤ m < n) ve şifreli metin

RSA (Rivest, Shamir, Adleman, 1977). d'yi bulmak için φ(n), onun için de n'nin çarpanları gerekir; güvenlik çarpanlara ayırmanın zorluğuna dayanır.

H = L · log₂ N

burada:

Hrastgele bir parolanın entropisi, bit
Lparola uzunluğu
Nalfabe boyutu (26 küçük harf, 94 yazdırılabilir karakter)

Her ek bit kaba kuvvet denemesini iki katına çıkarır. Formül yalnızca gerçekten rastgele parolalar için geçerlidir: “Baku2026!” gibi parolalar sözlük saldırılarıyla çabucak bulunur.

1Bilgisayar: bilgi, donanım ve yazılımBaşlangıç

Bilgi, bilginin türleri ve bilgi süreçleri

Bilgisayarın yapısı: işlemci, bellek ve anakart

Giriş ve çıkış birimleri

Dosya sistemleri ve diskte kaplanan alan

2Kelime işlemciler ve elektronik tablolarBaşlangıç

Kelime işlemciler: düzenleme, biçimlendirme ve klavye işlemleri

Elektronik tablo: adresler, aralıklar ve formüller

Elektronik tabloda fonksiyonlar

Elektronik tabloda grafikler ve öğeleri

3Bilginin kodlanması ve ölçülmesiOrta

Bilginin ölçülmesi: bit, bayt ve birimler

Metin bilgisinin kodlanması

Bilgisayar grafiği: raster ve vektör görüntülerin kodlanması

Ses ve video bilgisinin kodlanması

4Sayı sistemleri ve mantıkOrta

Sayı sistemleri: konumsal sistemler ve ikilik sistem

Sekizlik ve on altılık sayı sistemleri

Farklı sayı sistemlerinde aritmetik işlemler

Sayı sistemleri: tabanı bilinmeyen problemler

5ModellemeOrta

Modeller ve modelleme

Tablo bilgi modeli: mantık problemlerinin tabloyla çözümü

Ağaç bilgi modeli

Graf bilgi modeli: komşuluk matrisi ve yol sayısı

6AlgoritmalarOrta

Algoritma, özellikleri ve gösterim biçimleri

Dallanan algoritmalar

Döngülü algoritmalar ve izleme tablosu

Akış şeması oluşturma: yazılı sorular

Sıralama algoritmaları

7Python ile programlama (okul dersi)Orta

Programlama dilleri ve Python: değişkenler, veri girişi ve çıkışı

Koşul ifadesi: if, elif, else ve bileşik koşullar

Döngüler: for, while, döngü adımı, break, continue ve iç içe döngüler

Sayılar üzerinde işlemler: rakamlar, bölenler ve asal sayılar

Program analizi: çıktıdan girdiye

Karakter dizileri ve üzerlerinde işlemler

Listeler ve listeler üzerinde işlemler

Fonksiyon: def, parametreler ve return

Program yazmak: yazılı görevlerin çözümü

8Veri tabanlarıİleri

Veri tabanı: modeller, VTYS ve ilişkili tablolar

Veri tabanında sorgular, arama ve sıralama

9Ağlar, internet ve bilgi güvenliğiİleri

İnternette arama: arama motorları ve sorgular

Siber güvenlik: parolalar, oltalama ve gizlilik

Bilginin korunması ve kriptografi

10Web programlamaİleri

Web programlama: site hazırlama, HTML etiketleri ve listeler

HTML’de tablolar, renk şeması, resimler ve bağlantılar

11Algoritmalar ve veri yapılarıÜniversite

Algoritma karmaşıklığı ve Büyük O gösterimi

Diziler, bağlı listeler, yığıtlar ve kuyruklar

Hash tabloları

Ağaçlar ve yığınlar (heap)

Graflar ve graf algoritmaları

Özyineleme ve dinamik programlama

Verimli sıralama algoritmaları

12Bilgisayar sistemleri ve kuramÜniversite

Bilgisayar mimarisi

İşletim sistemleri

Bilgisayar ağları: derinlemesine

Veri tabanı kuramı

Hesaplama kuramı

Yazılım mühendisliği

Kriptografi ve bilgi güvenliği