Katalog

Matematik Olimpiyatı Köşesi Programlama dillerinin gizli kahramanları Salih Yurttaş Nuretün Ergun Uluslararası Maternatık Olımpıyatlarımn gerçekleştırıhşı, katılımcı ulkeleıın hazııldrıışı ve olırnpıyatlaıın yapılmdsının dmdçları uzeı ıne ayrmtılı bir yazıyı, sonraka bır haftaya bırakarak, bugun dılersenız Amerıkan Olımpıyat takımının belırlenmesı amacıyla yapılan son eleme sınavından alınmış (buna ulusal olımpıyat yarışrridsı denıt), polınomlar uzerıne, ılgınç ve çetın ıkı soruyla uc) raşalım 1975 yılından bu yana Amerıka nın kendı ulusal olımpıyatlarındd soıulan solulaı ve çozumlor, Amerı kan Matematik Bırhgı (The Mathematıcdl Assocıatıon of Arrıerıca tara fından kıtap olarak yayınla nır Rusya, Bulgdrıstan, Romanya ve Kanadd gıbı başka ulkelerın de benzen yayınları vardıı Elemelerı kaza nıp ulusal takıma gırmeye hak kazanan ogıencüer, olımpıyat oncesı süa ve yoğun bırkaç hazırlık (ohmpıyatçılann deyımıyle 'kamp") donemı yaşarlar Her gun onlarra ılgınç ve sıradışı problemle boguşan adaylara, kamptdkı gorevlı uyeleri tarafından belkı de dk kez tanık olduklan pek çok kavram, bılgı ve çozme yontemı verüır, problem çozme becerılerı gelıştırılır Duzey yıne de lıse duzeymı çok aşmaz. Aşagıdakı ıkmcı soıunuıı çozumu, bu açıdan tıpık bır ornektıı sanırız Çozumdc kullanılan bılgıloı onlar ıçın yenı degıldır ama yontem alışümadık ve beklenmedık gelebılır Evet ılgı duyanlann çözümlere bakmadan, bu soıularla kendı baş 1 larına "boguşmalaıını oneııyoruz, 1 kolay gele Soru 1: Tam katsayüı hıçbır p(x) I daha 'ohn Backus, Grace Hopper, John Avrupa ABD'ye gore hepeska ve McCarthy, Niklaus Wirth, Denbıçımsel kalmıştır Bılgasdyarların ve nis Ritchle, Alan Kay, Bjarne Stro programcılıgın tıcarı, sanayı, para, kaustrup, James Grosling adlannı ga zanç, ış, pazaı yanları Amerıkalılaı ıçın /etelerde, deryıleıde pek yoıemezsınız hep oncclıklıyken Avrupa'lı ınsan ıçın, Bu kışılenn heıbııı bılqısayaı bılım soyutlama gucu, dogruluk ve tutarlılık lerının kısacak tarıhınde, yaygın olarak oncelıklıdır Algol dılını yaratanların Av kullanılan dılleıın duşunuru, tasarımcısı rupa'lı oyunculdrı ıçınde bulurıan Niklave yapımcısıdırlar Sıraladıgrm adlar, bını us Wirth zamdn ıçınde dahd ıyıyı, daha aşkm programldma dillerinin seçkınlen guzelı bulmdk ıçın çalışıyor ve Pascal'ı dır yaratıyoı Pascal, kısa zamanda oğıtım ve Progrdmldnid dıllerı yapay dıllerdır, ogretımın temelı oluyor bılgısayar bılım demıştık Dıl yapımı, kımı omeklerde, kı lermde 1970'ler ve 1980'lerın gelışı şısel bır çabarun urunu oluyoı, kımı du 1968'de behrlpnıyor bır bakıma rumlarda takım çalışmasınm Bazı dıllerın Dennis Ritchie ve AT&T'dekı arardında, etkın, guçlu bıl kadaşları ıse degışık gısayar kııruluşları var Bugün çocuklar bile bıı deneyım ve umut bazı dıll^r use ABD devlela dıllerdekı bu çogal tı ve kamu oıgutlerırım bilgisayarı oyuncak maya, yalın ve yogun buyuk destegıyle uıetıl gibi kullanıyorlarsa, C, dılıyle katkıda bulu dı Dıllerın herbuı bır on bu kolaylığın nuyorlar C dılı, Fort cekının vaı lıgından vc arkasmda, bilgisayar rdrı'ırı makmeden baçabasından yararlanıyor ğımsızlaşrrid kaygısına Kımı yapımlar, yenı bır dilleri ve bu dilleri kaışılık, yuksek duzey yonu sımgelerken, kımı geliştiren dılıyle makıne duzeyı yapımlar, bır oncekının ne ınmeye makınenın aıınnıası ya da bır once kahramanlar var... bıtlerını programlama kının eklemlenmesı ola ya çozumdur rak gerçekleşıyor Jahn Backus, Fortran dılının, ar dındakı golge onder, 1950'lerın başında IBM'de çdlışırken, gunun pıogramcüaıımıı zorlu pıogıamlama yukunu kolaykş tırmak ıçın Fortran'ı duşluyor Kuçuk bır butçe, kısıtlı bır çalışma duzenı ve olana gıyla, beş on kışılık bır takım çalışmasıyla Fortran'ı ortaya çıkarıyorlar Bugunun bılyı.sayar bılırnlpruıde eskirnış bu duşunce oldiı Fortran, çok uzun sure kullanılmış bır programlama dılıdıı Foı tran, ılkm ve ılke lın sımgesı, gunumuzdo Grace Hopper, ABD Denız Kuvvet lerı'nde amıral rutbesme degın erışmış, saygın bır kadın, Cobol dılmı duşıınen ve dk uygulayan kışı olarak bılınıyor Cobol'un pek çok ozgunluklerı vaı, Foıt ran'dan aonra geldı, Foıtran'ın eksık yan larını tamamladı ve programlama deneyı mını zengınleştırdı Programlamanın, ma kıne dışında da yaşamı oldugu ve olacagının ılk sezınlemesınm başarılı deneyırrndrr Cobol John McCarthy, MIT'de profesor ıken yepyerıı bır dıl modelı Lısp'le çıkıyor ortaya 0 donemde bılgısayar bılımcılerı makıneleıı duşunduıme, yapay zekâ araştırmalan ıçınde, Fortran'a destek ola cak bır program katalogları/kıtaplıklan duşuncesmm peşmdeydı Lısp dılı, programlamada yalınlıgın adıdır Insanldrı makmeden, dılden ve programddn bagımsızlaştırmaya çalışmıştıı 1950'lerdeyız poünomunun, ıkışer ıkışeı farklı kl, k2, k3 tam sayüarı ıçın kl nız Soru 2: Gerçel katsayılı beş td ne pO(x), pl(x), , p4(x) polınomu hor x gerçel sayısı ıçın pO(x5) t xpl(x5) * x2p2(x5) * x3p3(x5) = (x4 + x3 + x2 + x + I)p4(x) gerçekleşır Beşının de x 1 de koklu oldugunu gostermız t(nO+2) = f(nütnl+2) f(nO+2nl+2) = ve benzerı eşıtlıkler kolayra eldp edılır O halde kolayca gorulecektır kı f(N) goruntu kumesı, en fazla şu mO 1 tanc farklı elemanı ıhtıva edebılıı, bun lar f( 1), f(2), , f(nO), f(nO+1)', f(nO+2), , f(nO+nl 1) dogal sayılarıdır Demek (1) ve (2) koşulunu gerçekleyen bır f fonksıyonunun goruntu kumesı sonlu elemanlıdır Oysa bu bu çelışkıdu, çunku f(n+1) doo;al sayısı, pozıtıf do^al sayılar kumesmın elemanı olduĞfun dan, (1) koşulu sayesınde f(n)<ff(n) geçerlıdır Bu son eşıtsızlıkte n dogal sayısı yerıne t(n) yazılırsa sonuçta tumevdrımld f(rı) < ff(rı) < fff(n) < bulunur Sozgelımı (f(l), ff(l), fff(l), } kumesmde ve sonuçta f(N) kumesınde sonsuz farklı do^al sayı vardır Başka bır deyımle (1) koşulunu gerçekleyen f fonksıyonu farklı bu dogal sayı çıftı ıçın asla (2) koşulunu gerçekleyemez, demek kı bırebn olur Gerçek olımpıyat soıulaıı ıle ıler kı yazılarda karşınızda olmak dılegıyle ıyı çalışmalar düıyoruz 568/19 p(kl) = k2 p(k2) k3, p(k3) (1) gerçekleyemeyeceÇını gosterı Alan Kay ıse, yıne 1970'lerde bılgısayaı makuıeleııru salt uzmanlar ve pıogıamcılaı değıl, çocuklar büe kulla malıdır dıye duşıınen yaratıcı bır beym Dıl, makıne ıle ınsan ılışkısındekı etkıleşı mın dılı, ozlu VP evrılen bır ozellıkte olmalıdır dıye duşluyor Konuşur gıbı, duyularımızla kullanmalıyız bılgısayan, pıogram ve dıl degıl, makınenın kendısı de taşınabılır olmalfdır, dıye ongoruyor Iştc Smalltalk, geçmışın klavye ve kâğıdı yerıno, yenı ortamlar ve olanaklar duşunenlerm oncusu ve neredeyse onderı olarak ortaya çıkıyoı Smalltalk grdfık temellıdıı bılgısayar etkıleşııııının or neğıdu Bjaıne Stroustnıp Smalltalk'ın, C sentaksıyla yenı makıneleı geıek meden de kullanılabılır olacagını duşunuyor ve C++'ı sunuyor C++'nın gorduğu ılgı VP C'nırı saglam temellen, Internet olanaklarını programlamada koldyldşlırnid duşuncesı, James Gosling'ı Java dılıne vardırıyor Kımı dıller ozgun ve yaratıcı kat kılarla kulldnıma açılırken, kımı (iıller arınmacı, kımı dıller bıreşımcı ışlevde oluyor Her bır dılın ardındd, ddlı, ddsız kahramanlar vaı Bu dıllerı kulldnan ve yazılım geliştiren dunyanın dort bır yanındakı mılyonlaıca programcı, bıl gısayar dillerinin otekı kahramanlandır yurttas@cs tamu edu http //www cs tamu odu/faculty/yurttas Geçen haftanın çözümü Çozum Oncelıkle şu onemlı gozlemı yapalım F'ger bır no ve mO dogdl sayı çıftı ıçın f(nO) = f(mO) (2) eşıtlıgı gerçekleşırse Her n doğal sdyısı ıçın f(nO+n) = f(mO+n) (3) gerçekleşır, çunku (2) nedenıyle ff(nO) ff(mO) ve sonuçta (1) nedenıyle f(nO+l) f(mO+l) bulunur Demek kı f fonksıyonu ıkı dogal sayıda eşıt deger alırsa, oıüdrııı ardışıklarında da eşıt degerler alıı ve sonuçta tumevanm ıl kcsı nedenıyle (3) bulunur Demek kı, f fonksıyonu eger bıre bır degılse (2) koşulunu gerçekleyen farklı bır nO ve mO doğal sayıkrı vardır Bunldrdan bırısı buyuk olacaktır Sozgelımı nO<mO nO+nl olsun 0 hdlde f(nO) = f(nO+nl) = f(nO+2nl) = f(nO+3nl) = elde edılır, çunku nO+nl mO, nO+2nl mO+nl, geçerlıdır ve (3) kıilanılır Benzer bıçımde f(nO+l) f(nO+nl + l) = f(nO+2nl + l) =