Donald Knuth önerdiği kitapların doğruluğuna çok önem veren bir bilgisayar bilimcisidir. bir altıgen dolar (2,56 ABD Doları, 0x1,00 ABD Doları) bulunan herhangi bir "hata" için; burada hata, "teknik, tarihsel, tipografik veya politik olarak yanlış" olan herhangi bir şey olarak tanımlanır. Gerçekten Knuth'tan bir çek almak istiyordum, bu yüzden onun başyapıtındaki hataları aramaya karar verdim. "Programlama Sanatı" (TAOCP). Üç tane bulmayı başardık. Knut sözüne sadık kalarak bir çek gönderdi. 0x3,00$.

Gördüğünüz gibi bu gerçek bir çek değil. Knuth gerçek çekler gönderiyordu ancak 2008'de şu nedenlerden dolayı durdu: yaygın dolandırıcılık. Artık "kişisel mevduat sertifikalarını" gönderiyor San Serriff Bankası (Patron). Gerekirse gerçek para göndermeye hazır olduğunu söylüyor ama bu çok zahmetli gibi görünüyor.

İki yazım hatası ve bir tarihsel hata buldum. Bunları önemsizliği azaltacak şekilde sıralayacağım.

Yazım hatası #1

İlk yazım hatası, “Sıralama ve Arama” kitabının üçüncü cildinin 392. sayfasında, alttan sekizinci satırdadır: “Başarısız bir aramanın ardından, bazen (bazen) aşağıdakileri içeren tabloya yeni bir kayıt girilmesi istenir: K; bunu yapan yönteme arama ve ekleme algoritması denir. Hata şu ki bunun yerine bazen должно быть bazen.

Elbette böyle bir hata şaşırtıcı değil. Yalnızca bu makalede bile birkaç yazım hatası olması kaçınılmazdır (bunları bulmanın ödülü yoktur). Asıl şaşırtıcı olan bunun bu kadar uzun süre fark edilmemesiydi. Sayfa 392 matematik bölümünün derinliklerine gömülmemiştir, ilk sayfa Bölüm 6 "Arama"! Muhtemelen kitabın en çok okunan bölümlerinden biri. Teorik olarak en az yazım hatası olması gerekir ama hayır.

Bu arada, eğer TAOCP okumayı düşündüyseniz bir deneyin. Birçoğu bunun böyle olduğunu söyleyecektir rehber, doğrudan okumaya yönelik değildir, ancak bu doğru değildir. Yazarın net bir bakış açısı ve kendine özgü bir üslubu var. Okunabilirliği engelleyen tek şey matematiğin karmaşıklığıdır. Ancak bunun basit bir çözümü var: Anlamadığınız matematiğe gelinceye kadar okuyun, atlayın ve anlayabileceğiniz bir sonraki bölüme geçin. Bu şekilde okuduğumda kitabın en az %80'ini kaçırıyorum ama diğer %20'si harika!

TAOCP'nin de olduğu söyleniyor alakasız, güncel değil veya başka bir şekilde "gerçek programlamaya" uygulanamaz. Bu da doğru değil. Örneğin, girişten sonraki ilk bölüm, sıralanmamış bir dizide bir öğenin bulunmasına bakıyor. En basit algoritma tüm programcılara aşinadır. İşaretçiyi dizinin başlangıcında başlatın ve ardından bir döngüde aşağıdakileri yapın:

1. Geçerli öğenin istenen öğe olup olmadığını kontrol edin. Eğer öyleyse iade ederiz; aksi takdirde
2. İşaretçinin dizi sınırının dışında olup olmadığını kontrol edin. Eğer öyleyse, bir hata döndürün; aksi takdirde
3. Yakınlaştırın ve devam edin.

Şimdi düşünün: Bu algoritma ortalama olarak kaç tane sınır kontrolü gerektiriyor? Dizinin bir öğe içermediği en kötü durumda, listedeki her öğe bir kontrol gerektirecektir ve ortalama olarak şöyle bir şey olacaktır: . Daha akıllı bir arama algoritması yalnızca tek bir sınır kontrolüyle bu durumdan kurtulabilir. İstenilen öğeyi dizinin sonuna ekleyin, ardından işaretçiyi dizinin başlangıcında başlatın ve bir döngü içinde aşağıdakileri yapın:

1. Geçerli öğenin istenen öğe olup olmadığını kontrol edin. Eğer öyleyse, işaretçi dizinin içindeyse bir yanıt, değilse bir hata döndürürüz. Aksi takdirde
2. Yakınlaştırın ve devam edin.

Öyle ya da böyle, öğenin bulunması garanti edilir ve bu durumda sınır kontrolü yalnızca bir kez gerçekleştirilir. Bu derin bir fikir ama acemi bir programcı için bile yeterince basit. Muhtemelen işin başkalarıyla olan ilgisi hakkında konuşamam, ancak bu bilgeliği hem kişisel hem de profesyonel kurallara hemen uygulayabildim. TAOCP kitabı bu tür mücevherlerle dolu (adil olmak gerekirse, orada pek çok tuhaf şey de var, örneğin kabarcık sıralama).

"Arama Arama
Elveda
Arama Arama
Sadece dans etmek istedim"
- Luther Vandross, "Arama" (1980)

Yazım hatası #2

İkinci yazım hatası Cilt 4A, Kombinatoryal Algoritmalar, Kısım 1'dedir. Sayfa 60'ta komedyenlerin çeşitli kumarhanelerde gösteri yapmasının planlanmasını içeren bir sorun anlatılmaktadır. Örnek olarak Lily Tomlin, Weird Al Yankovic ve kitap yayınlandığında hala hayatta olan Robin Williams gibi gerçek hayattaki birçok komedyen gösteriliyor. Knuth her zaman dizinde tam adları listeler, bu nedenle Williams 882. sayfada "Williams, Robin McLorim" olarak listelenir. Ancak göbek adı "m" ile değil "n" ile bitiyor, yani McLaurin.

McLaurin annesinin kızlık soyadıydı. Mississippi'nin 34. Valisi Anselm Joseph McLaurin'in torununun torunuydu. Görünüşe göre saltanatı iyi bir şeyle hatırlanmadı. Kitaptan "Mississippi: Tarih":

“McLaurin yönetimi sırasındaki en önemli olay, ABD'nin 1898 baharında İspanya'ya savaş ilan etmesiydi... Ne yazık ki savaş, bazı hükümet yetkililerine rüşvete bulaşma fırsatı vermiş olabilir. McLaurin, kayırmacılık ve af yetkilerinin aşırı kullanımı da dahil olmak üzere çeşitli şüpheli uygulamalarla suçlandı. Ölçülülük hareketi sırasında, eleştirmenler valiyi sarhoş olmakla suçladı ve kendisi de bunu açıkça kabul etti.”

Tarihsel hata

Consider geleneksel çarpma algoritması okul müfredatından. Kaç tek basamaklı çarpma işlemi gerektirir? Diyelim ki çoğaldınız -dijital numara üzerinde -biraz . İlk önce ilk rakamı çarpın her rakam için birer birer. Daha sonra ikinci rakamı çarpın her rakam için tüm sayıları geçinceye kadar tek tek . Dolayısıyla geleneksel çarpma gerektirir ilkel çarpımlar. Özellikle iki sayının çarpılması gerekli rütbeler tek basamaklı çarpmalar.

Bu kötü ama Sovyet matematikçi Anatoly Alekseevich Karatsuba tarafından geliştirilen bir yöntemi kullanarak süreci optimize etmek mümkün. Öyleymiş gibi yapalım и  - iki basamaklı ondalık sayılar; yani sayılar var , , , öyle ki и (Bu algoritmayı daha büyük sayılara genellemek biraz manipülasyon gerektirir; çok zor olmasa da ayrıntılarda hata yapmamak için basit bir örnek üzerinde dursam iyi olur). Daha sonra , , . Binomların çarpılması şunu verir . Şu anda hala elimizde tek basamaklı çarpma: , , , . Şimdi toplayıp çıkaralım . Okuyucuya alıştırma olarak bırakacağım birkaç yeniden düzenlemeden sonra, şu ortaya çıkıyor:  - yalnızca üç tek haneli çarpma! (Bazı sabit katsayılar vardır, ancak bunlar yalnızca rakamları toplayıp kaydırarak hesaplanabilir).

Kanıt isteme ama Karatsuba algoritması (Yukarıdaki örnekten yinelemeli olarak genelleştirilmiştir), geleneksel çarpma yöntemini şu şekilde geliştirir: daha önce yapılan işlemler . Bunun zihinsel hesaplamalar için bir optimizasyon değil, algoritmada gerçek bir gelişme olduğunu lütfen unutmayın. Gerçekten de algoritma zihinsel aritmetik için uygun değildir çünkü özyinelemeli işlemler için büyük masraflar gerektirir. Buna ek olarak, sayılar yeterince büyüyene kadar etki tam olarak kendini göstermeyecektir (neyse ki, Karatsuba'nın algoritmasının yerini daha hızlı yöntemler almıştır: Mart 2019'da yalnızca n günlük n çarpmalar; ivme yalnızca hayal edilemeyecek kadar büyük sayılar için geçerlidir).

Bu algoritma Cilt 295, Yarı Sayısal Algoritmalar'ın XNUMX. sayfasında açıklanmaktadır. Orada Knuth şöyle yazıyor: "Bu fikrin yalnızca 1962 Yıl” Karatsuba’nın algoritmasını anlatan bir makale yayınlandığında. Ancak! 1995'te Karatsuba, "Hesaplamalı Karmaşıklık" üzerine birkaç şey söyleyen bir makale yayınladı: 1) 1956 civarında, Kolmogorov çarpma işleminin XNUMX'den daha kısa sürede yapılamayacağını öne sürdü. adımlar; 2) içinde 1960 yıl Karatsuba, Kolmogorov'un n² hipotezini sunduğu seminere katıldı. 3) "Tam olarak bir hafta içinde" Karatsuba "böl ve yönet" algoritmasını geliştirdi; 4) 1962'de Kolmogorov bir makale yazdı ve yayınladı Karatsuba adına algoritmanın bir açıklaması ile. “Bu makaleyi ancak yeniden yayınlandıktan sonra öğrendim.”

Yani hata şu ki bunun yerine 1962 belirtilmeli 1960 yıl. Bu kadar.

analizi

Hataları bulmak özel bir beceri gerektirmiyordu.

1. İlk hata mümkün olduğu kadar önemsizdi ve nispeten görünür bir yerdeydi (bölümün başında). Herhangi bir aptal onu bulurdu; Benim de o aptal olduğum ortaya çıktı.
2. İkinci yazım hatasını bulmak şans ve gayret gerektiriyordu ama beceri gerektirmiyordu. "Williams" dizini, kitabın oldukça önemli bir kısmı olan cildin sondan bir önceki sayfasında yer almaktadır. Sadece indekse göz atıyordum (göründüğü kadar acıklı değil, çünkü Knuth'un indekslerinde gizli Paskalya yumurtaları var. Örneğin, Arapça ve İbranice girişler var, her ikisi de 66. sayfayı işaret ediyor. Ama o sayfada bundan bahsedilmiyor) her iki dil; bunun yerine “sağdan sola okunan diller” anlamına gelir. Ve ikinci isim dikkatimi çekti. Genellikle Wikipedia'yı okuduğum için Robin Williams'ı kontrol ettim ve bir tutarsızlık fark ettim.
3. Keşke tarihsel bir hatayı bulmak için ciddi bir araştırma yaptığımı söyleyebilseydim, ama gerçekten sadece baktım Karatsuba'nın algoritmasıyla ilgili Wikipedia sayfası. İlk satırlarda şöyle yazıyor: “Karatsuba algoritması hızlı bir çarpma algoritmasıdır. 1960 yılında Anatoly Karatsuba tarafından keşfedildi ve 1962'de yayımlandı." Bundan sonra geriye ikiyle ikiyi eklemek kalıyordu.

Gelecekte özellikle Knuth'un kodunda daha önemli bir hata bulmak istiyorum. Ayrıca Temel Algoritmalar'ın ilk cildinde de bir hata bulmak istiyorum. Belki bulurdum ama nedense yerel kütüphanede yalnızca 2, 3 ve 4A ciltleri var.

Finansal gerçekler:

• Toplamda TAOCP'ye katkım yalnızca üç karakterden oluşuyor: bir ekleme s, yenisiyle değiştirme m üzerinde n и 2 üzerinde 0. 2,56 Dolar değerinde bunlar oldukça kazançlı semboller; Eğer size bu kadar para ödenseydi, 1000 kelimelik (ortalama dört karakter) bir makale size on bin dolar kazandırırdı.
• Üç onaltılık dolarla, diğer 29 vatandaşla birlikte San Serriff Bank'ın en zengin mevduat sahipleri listesinde (69 Mayıs 1 itibarıyla) 2019. sırada yer alıyorum.

Knuth'tan gelen çeklerle ilgili diğer tartışmalar

• Knuth'tan çek nasıl alınır?

  Knuth'un kitaplarındaki hataları bulmaya yönelik genel öneriler. Çoğunlukla bende olmayan teknik hatalarla ilgilidirler. Orada ciddiye aldığım bir öneri var:

  Göndermek için bir dizi hata toplayana kadar beklemek en iyisidir. Birkaç gerçek ama çok değerli olmayan hatayı birleştirerek, bunlardan birinin aslında bir hata veya tavsiye olarak değerlendirilme olasılığını artırırsınız. Hataları tek tek gönderirseniz her biri ayrı ayrı reddedilebilir.

  Saçma yazım hataları göndermek istemedim ama tavsiyeye uydum ve mektubu ancak yeterince ciddi görünen tarihi bir hata bulduğumda gönderdim.

• Ashutosh Mehra'nın çekleri

  Ashutosh Mehra, BoSS'daki 0x$207.f0 muazzam net değeriyle San Serriff'teki üçüncü en zengin yatırımcıdır.

• Gerçek TeX kodundaki bazı işlevsel olmayan hataları kontrol edin
• Çeşitli: #1 #2 #3 #4 #5 #6

Kaynak: habr.com