Commodore 64 ile Matematik ve Bilimsel Hesaplamalar

• BASIC
• Kurslar ve dersler

Sinan Vural Commodore 64 piyasaya ilk çıktığı günden beri kendi alanındaki rakipleri arasında hep yükselmiştir. Her alanda kullanılabilecek kadar esnek olan bu müthiş alet şimdiye kadar ülkemizde eğitim alanında çok sınırlı olarak kullanılmış, ancak bazı ortaokul ve liselerimizde bilgisayar dilleri öğretilmiştir. Birçok bilgisayar sahibi öğrenci Commodore 64'leri ile oyun oynamaktadır. Program yapıp kendini geliştirmeye çalışanların ise ancak küçük bir kısmı kendi dersleriyle ilgili programları yazabilmektedir. Bu yazı boyunca sizlere genel matematik ve bilimsel hesaplamalar konusunda programlar ve algoritmalar anlatacağız, rutinlerden örnekler vereceğiz. Bu kadar geniş bir konuyu işlerken elbette atladığımız birçok detay olacaktır ama bu konuların her biri hakkında birer kitap yazılabilir. Bu yazı dizisinde bilgisayarların, özellikle Commodore 64'ün matematik ve bilimsel hesaplamalar alanında nasıl kullanılabileceğini göstereceğiz. Yazı dizimiz boyunca verdiğimiz programlar BASIC ile hazırlanmış olacak. Programları direkt olarak yazıp kullanmak için hiçbir ön bilgiye sahip olmanız gerekmiyor, ama eğer bilgisayar konusunda biraz deneyimliyseniz kendi amaçlarınız doğrultusunda programları değiştirebilirsiniz. Vereceğimiz programlar kısa rutinler halinde yazılmış olacak ve başka bir program tarafından hemen çağrılabilecek durumda olacaklar. Ayrıca bir konu sonunda o konuyla ilgili rutinler birleştirilmiş olarak ve karşılaştırmalı bir halde yazılacak.

Sıralama Sistemleri ve Programları

Doğal bilimlerle uğraşırken ölçülmüş dataların sıralanması gerekir. Sıralama programları da bu iş için kullanılırlar.

Bu programların birçoğu da altprogram (subroutine) olarak kullanılır. Sıralama sistemlerinden özellikle bazıları çok yaygındır. Burada inceleyeceğimiz sistemler yaygın olarak kullanılanlardan bazılarıdır. Sıralama algoritmalarının sistemleri ve sistemler kullanılarak hazırlanmış olan programların isimleri aşağıda sıralanmıştır. Bu sıralama programların verimlilikleri hakkında da genel bir fikir edinmenizi sağlayabilir: 1. Araya sıkıştırmalı sıralama (insertion). Örnek: doğrusal (linear) sıralama ve dalgacık (ripple) sıralama. 2. Değiştirmeli sıralama (exchange). Örnek: kabarcık (bubble) sıralama. 3. Seçimli sıralama (selection). Örnek: Shell sıralama. 4. Karışık ve özel yöntemler. Örnek: hızlı (quick) sıralama. Datalarımızın sayısal olduğunu varsayacağız. Yani sıralanacak olan bilgiler sayılardan oluşacak ve bir dizi içinde saklanacak. Bu bölümde anlatılanlardan daha verimli sıralama programları mutlaka vardır, ancak bunlar daha kısıtlı alanlarda kullanılabilirler veya çok daha karmaşıktırlar. Bunların dışında, sadece floppy diskler gibi dış kayıt ortamlarında sıralama yapmak için hazırlanmış algoritmalar da vardır. En çok bilinen sıralama algoritmaları doğrusal, kabarcık, hızlı ve Shell-Metzner sıralamalarıdır. Bu metodları anlatmaya çalışacağız, çünkü bu sistemler en yaygın olarak kullanılan algoritmalara dayanırlar. Bu konudan bahsederken, bir yandan da metodların hızlarının karşılaştırmasını yapacağız. Ancak programlara getireceğimiz bazı sınırlamalar olacak, örneğin recursive, yani kendi kendini çağıran algoritmalar kullanmayacağız. Belirtmemiz gerekir ki, özellikle Pascal gibi diğer programlama dillerinde bu sistemler dilin yapısında vardır. Sıralama rutinlerini, kendi programlarınızda istediğiniz gibi kullanabilirsiniz. Örneğin bir grafik çizmek için verilmiş olan bir grup datanın sıralanması gerekebilir. Temel bazı değişkenleri tanımladıktan sonra bu rutinleri çağırarak kendi işleriniz için kullanabilirsiniz. Sıralama algoritmalarını daha da iyileştirebilirsiniz. Programların hızlı çalışmasının zararı değil yararı vardır. Şimdi ilk örneğimize bakalım: kabarcık sıralama.

Kabarcık Sıralama

Kabarcık sistemi, sıralama metodlarının en çok bilinenidir. Ancak bu programı bile yanlış hazırlayıp süreyi uzatmak mümkündür. Bu sistem nasıl çalışır? Kabarcık sıralama en çok bilinen sistem olmasının yanında en kolay algoritmaya da sahiptir. Program adımları şöyle özetlenebilir: 1. Data grubu içinden en yüksek olanı bul.

2. En büyük elemanı ilk elemanla değiştir. 3. Elemanlar istenen sıraya girene kadar 1. ve 2. adımları tekrarla. Programlar genel olarak biri diğerinin içinde yer alan iki FOR-NEXT döngüsünden oluşur. Dış döngü birden başlar ve sıralanacak data sayısından bir düşüğe kadar gider. İç döngü ise, dış döngünün değerinin bir fazlasından başlar ve toplam değer sayısına kadar gider. Böylece küçük değerler yavaş yavaş data grubunun başına doğru giderler. Değerler su “kabarcıkları” gibi yükselir. Kabarcık sıralama basit ve kolay uygulanabilir olmasına rağmen büyük data grupları için çok yavaş kalır. Bunun sebebi de tüm grup içinden geçiş yapılması gerektiğidir. Bunu bir formül yardımıyla da anlayabiliriz. Program şu formda bir karar komutuna sahiptir:

IF — THEN ...

Bu komutun kaç defa işletileceği şu formülle anlaşılabilir: (n-1)+(n-2)+...+2+1 = n(n-1) / 2 = k (karşılaştırma) Başka bir deyişle bu komutun işlenme sayısı sıralanacak grup elemanlarının (n) karesine bağlı olarak artar. Ancak bir süre sonra bu komuta ihtiyacımızın kalmadığını göreceksiniz. Basit bir kabarcık sıralama programı şöyledir:

30000 REM
30010 REM ***KABARCIK
SIRALAMA RUTİNİ***
30020 REM
30030 FOR I-İ TO N-İ
30040 ::FOR J-İ41 TON
30050 ::::1F — X(J) THEN 30090
30060 ::::B — X()
30070 ::::X(D) —
30080 ::::X()) — B
30090 ::NEXT J
30100 NEXT I
30110 RETURN

Daha önce bahsettiğimiz satırı değiştirecek kabarcık sıralamayı biraz geliştirelim. Böylece değiştirdiğimiz program şu hale gelir:

30000 REM 30003 REM ***GELİŞTİRİLMİŞ KABARCIK SIRALAMA RUTİNİ*** 30006 REM

30010 FORI-1
30020 ::B - |
30030 ::FOR J-İ41 TON

30040 — X(J) THEN 30060
30050 ::::B — : J
30060 J
30070 ::X(K) —
30080 ::X() - B
30090 NEXT I

30100 RETURN

Bu rutin de ilk örnekteki “değiştirerek sıralama” sistemine dayanır. 30040. satırdaki karşılaştırma komutu değiştirilerek sıralamanın yönü de (artan veya azalan) ayarlanabilir. İyi de niye ikinci program daha hızlı? Bu cevabı, ikinci versiyonda dış döngüde sadece bir X değiştirilmesi yapılmasıdır. Rutin bu değerin daha önce değiştirilip değiştirilmediğini kontrol eder, bunun için de geçici B değişkeni kullanılmaktadır. Böylece toplam işlem

Ma aaa sayısı (n-1)'e düşer. Doğrusal Sıralama

Bu yöntem “araya sıkıştırmalı sıralama” prensibine dayanır. Örneğin siz bir dizi kartı dizerken istediğiniz kartları diğerlerinin arasına sıkıştırırsınız. Böylece zaten gereken yerde bulunan elemanların yeri boşu boşuna değişmez. Eğer data grubu biraz sıralıysa bu sistem çok hızlı işler. Eğer grup çok dağınıksa sıralama için büyük zaman harcanır. Doğrusal sıralama rutini aşağıdaki gibidir:

30000 REM
30005 REM ***DOĞRUSAL
SIRALAMA***
30010 REM
30020 FOR 1-2 TO N
30030 ::A(0) — A(I)

30040 ::B — I-I
30050 ::1F A(0) — — A(B) THEN
GOTO 30090
30060 ::A(B-- 1) — A(0)
30070 ::B —
30080 ::1F B 0 THEN

Di Ve va er Ü

GOTO 30050
30090 ::A(B4 1) — A(0)
30100 NEXT I
30110 RETURN

Gördüğünüz gibi doğrusal sıralama her işinizi en kısa zamanda görecek bir program değildir. Aslında gerçekten fazla önemi yoktur. Daha önce bahsettiğimiz geliştirilmiş kabarcık sıralama çok daha yararlıdır. Toplam işlem sayısı (n*n + 3*n - 4)/2'dir.

Shell Sıralaması

Biraz daha verimli olmasına rağmen anlaşılması daha zor olan bir sıralama sistemi olan Shell, 1959 yılında D.L. Shell tarafından önerilmiştir. Bu metodda da direkt bir yaklaşım izleyeceğiz. Sıralanacak olan değerler komşu değerlerle değil uzaktaki değerlerle karşılaştırılacaktır. Shell sıralaması aslında “araya sıkıştırma” yönteminin değişik bir uygulamasıdır. Ancak sebebi bilinmeyen nedenlerle en verimli adım büyüklüğü tespiti hâlâ yapılamamaktadır. Shell sıralamasının anlatımı için uygulanabilecek en kolay yol aşağıda verilen yapısal akış şemasıdır. Bu sistemde data elemanları gittikçe azalan uzaklıktaki diğer elemanlarla karşılaştırılır ve gerektiğinde yer değiştirilir. Yavaş yavaş en küçük uzaklığa erişilir ve (umarız) elemanlar sıralanmış olur.

Aşağıda programın listesini, çok karışık olması açısından yapısal akış şeması Adım büyüklüğünü tespit etmek için şeklinde veriyoruz. belli bir yöntem olmadığından adım genellikle data dizisindeki eleman sayısının yarısı kadar alınır. Bu n tane eleman için adım n/2 alınır. Hızlı sıralamaya başlamadan önce Shell sıralamasının programını verelim:

30000 REM

30010 REM ***SHELL
SIRALAMASI***
30020 REM
300308 - N
300408 - N
30050 IF S-0 THEN 30180
30060 DI — N-2
30070 FOR J-1 TO Dİ
30080 J
30000 ::81-1-4- 8
x(1):>b 30100 ::1F — — X(SI)
izİZM THEN 30160

30110 ::H — X()
30120 — X(S1)
30130 -H
30140 ::IFI — 0 THEN 30090
30150 NEXT J
30160 RETURN

s:ızi Hızlı Sıralama

Çok dağınık haldeki elemanları en hızlı şekilde sıralamanın yolu Quicksort'ta yatar. Bu sistem daha da verimli hale getirilmiş bir kabarcık sıralama gibi düşünülebilir. Bu algoritma kalitesini, elemanlar mümkün olan en dağınık haldeyken gösterir. Bu programın adı bazen yaratıcısının adıyla Hoare olarak da anılır. Quicksort'un anlaşılması gerçekten biraz zordur, bu yüzden genel bir taslağını vereceğiz. Burada yine karşılaştırmalar büyük uzaklıklar üzerinden yapılır. Bu, yüksek seviyeli sıralama algoritmalarının karakteristik özelliğidir. Shell sıralamasının aksine bu sistemde karşılaştırmalar dışardan içeri doğru yapılır. Bu yüzden karşılaştırma değeri olarak tanımlayacağımız X değeri çok önemlidir. X değeri için genellikle orta büyüklükte bir eleman seçilir. 34 56 12 33 78 90 21 10 8 dizisinde medyan değeri olan 33 seçilir. Bu değer, elemanların bir yarısından küçük veya onlara eşit ve aynı zamanda diğer elemanlara eşit veya onlardan küçük olan birkaç değerden biridir.

repeat until 1>-r

repeat until s-0 17