Pathfinder 2E notları

Yıllar önce nasıl (D&D) 4E için sisteme genel bir bakış yazdıysam, şimdi de PF2 hakkında bir şeyler yazayım, temel olarak kendime bir hatırlatıcı olarak.

L^1 ve L^2 uzayların/metriklerin farklarına dair yanlış bir gözlem

Dün gece uykuya dalarken aklıma eski bir anı geldi:

"Sabit 1 noktaya eşit mesafedeki noktalar kümesi bir çember, 2 noktaya mesafeler toplamı eşit olan noktalar kümesi ise bir elips. 2 noktaya olan mesafelerinin kareleri toplamı sabit olan noktalar kümesi ise gene bir çember!"

Sabah uyandığımda önce bunu teyit ettim, sonra da biraz elips tanımlarını örtüştürmeye çalıştım (yani yukarıda yazdığım tanım ile ağırlıklı-çember tanımı: (x/a)^2 + (y/b)^2 = 1) Başarısız oldum ama bu süreç bana şunu düşündürttü:

Mesafelerin toplamıyla karelerin toplamı aslında L^1 ve L^2 normlara benziyor, işte biri iki nokta merkezli elmasların kesişimiyken diğeri çemberlerin kesişimi ve biri elips diğeri çember veriyor ne kadar ilginç

Ancak  bunu yazarken fark ettim ki "mesafenin kendisinin toplamı" L^1 norm değil, alakası bile yok! Çünkü söz edilen "mesafe" zaten L^2 (Euclid). Takiben, "mesafenin kareleri toplamı" da L^2 değil, hatta bir bakıma o L^1 olmaya daha yakın (arada bir kare alma işi var ama olsun).

O yüzden bu düşünce taslağını yanlış bir taslak olarak bırakalım.

Yakın geçmiş oyunları v.2

Zaten eve kapanmış olsam da COVID-19 sebebi ile bu kapanışın ruh hali değişince ben de günlük rutinlerime bir değişiklik getirip çeşitli oyunlar oynadım. Not etmekten zarar gelmez:

Elric

kitapları okumamın üzerine çok geçmiş olması sebebiyle hep unutmuşum, hızlıca bir göz atıp hatırlayıp, bir de not edeyim ki bir sonraki okumam sırasında benzer bir ihtiyaç olursa kolaylık olsun. bunda del rey külliyatındaki basım takip edilecektir.

Hafıza Kullanımı

Geçtiğimiz günlerde gittiğim bir yazılım mülakatında, O(.) analizinin sadece işlem adım sayısıyla ilgili kullanılabileceği söylendi, ki bu tabii ki yanlış. Örneğin bir programın hafıza kullanımı da değişkene bağlı olarak değişiklik gösterilebilir. Sonra da bu konuda sentetik bir problem düşündüm ve asimptotik değil kesin çözümünü buldum.

SORU:

İlk N doğal sayının saklanması (işaretsiz olarak) kaç bit harcayacaktır? örn. 5 101 olarak 3, 77 ise 1001101 olarak 7 bit kullanacaktır.

YANIT:

Aslında bu Σ_{i=1}^{N}{\ceil{\log i}} toplamını bulma sorusu (0'ı dahil edip etmeyeceğimize göre 1 eklenebilir), öyleyse bunu özel bir durum olan N=2^k vaziyeti için inceleyelim.

Bu durumda 1'den k'a kadar olan sayıları topluyoruz, öyle ki bu sayılardan toplam N adet var. Dağılımı da i sayısından 2^(i-1) ve 2^i arasındaki kadar olacak şekilde: yani 2^(i-1). Dolayısıyla toplam farklı bir ifade kazandı:

S(k) = Σ_{i=1}^{k}{i2^(i-1)}

Ancak bu da bir çırpıda çözülebilir bir toplam gibi görünmedi. O noktada, \int xe^x dx = (x-1)e olmasından yola çıkarak benzer bir şekilde F(k)=Σ_{i=1}^{k}{i2^i} için Ak+B2^k+Ck2^k+D şeklinde bir gösterim olup olmayacağını merak ettim. Olduğunu varsayıp F(k+1)-F(k) farkını inceledim ve bunu (k+1)2^(k+1)'e eşitlemeye çalıştım. Dikkat edilmesi gereken noktalardan biri bu sırada D için hiç bir şey söyleyemeyeceğimiz. Bunun sonunda çıkan eşitlik:

A + (B+C)2^k + C(k+1)2^k = (k+1)2^(k+1)

ve bu her k için geçerli olacak, ve k ve 2^k terimleri lineer bağımsız, yani sonunda

• A = 0
• B+C = 0
• C = 2

sonucuna ulaştık. Buradan F(k) = (k-1)2^(k+1)+D ve F(1)=2 kullanılarak D=2 bulunur ve ufak manipülasyonlarla S(k) = (k-1)2^k+1 bulunur, son olarak da k sayısını N=2^k olacak şekilde hatırlayarak bunun (logN-1)N+1 olduğu görülür. Bir sonraki adım, hafıza gereksiniminin O(NlogN) olduğunu söylemek. (Bu adım biraz havada, kabul ediyorum, lineer bağımsızlık argümanı gibi)

Alternatif yol

Bu yazıyı yazarken F(k)'i hesaplamak için hiç bir varsayıma ihtiyaç duymayan başka bir yol fark ettim, ekliyorum:

• İlk olarak fark edilmeli ki her k için F(k)=2S(k)
• Ancak indis değiştirip toplamı ayırırsak, S(k) = Σi2^(-1)
  = Σ(i-1)2^(i-1) + Σ2^(i-1) = Σi2^i + Σ2^i
  = F(k-1) + 2^k -1
• Bunun bize söylediği şey, F(k) = 2F(k-1) + 2^(k+1) -1,
• ve ayrıca biliyoruz ki F(k) = F(k-1) + k2^k
• Buradan F(k-1) sadeleştirildiğinde F(k-1) = (k-2)2^k+2 çıkıyor, ki bu da aradığımız şeydi.