Bilişim Teknolojileri - 16 - Temel Algoritmalar

  • Published on
    29-May-2018

  • View
    215

  • Download
    0

Embed Size (px)

Transcript

<ul><li><p>8/9/2019 Biliim Teknolojileri - 16 - Temel Algoritmalar</p><p> 1/47</p><p>T.C.</p><p>MLL ETM BAKANLII</p><p>MEGEP(MESLEK ETM VE RETM SSTEMNN</p><p>GLENDRLMES PROJES)</p><p>BLM TEKNOLOJLER</p><p>TEMEL ALGORTMALAR</p><p>ANKARA 2007</p></li><li><p>8/9/2019 Biliim Teknolojileri - 16 - Temel Algoritmalar</p><p> 2/47</p><p>Milli Eitim Bakanl tarafndan gelitirilen modller;</p><p> Talim ve Terbiye Kurulu Bakanlnn 02.06.2006 tarih ve 269 sayl Karar ileonaylanan, Mesleki ve Teknik Eitim Okul ve Kurumlar nda kademeli olarakyaygnlatrlan 42 alan ve 192 dala ait ereve retim programlarndaamalanan mesleki yeterlikleri kazandrmaya ynelik gelitirilmi retim</p><p>materyalleridir (Ders Notlardr).</p><p> Modller, bireylere mesleki yeterlik kazandrmak ve bireysel renmeyerehberlik etmek amacyla renme materyali olarak hazrlanm, denenmek vegelitirilmek zere Mesleki ve Teknik Eitim Okul ve Kurumlarndauygulanmaya balanmtr.</p><p> Modller teknolojik gelimelere paralel olarak, amalanan yeterliikazandrmak koulu ile eitim retim srasnda gelitirilebilir ve yaplmasnerilen deiiklikler Bakanlkta ilgili birime bildirilir.</p><p> rgn ve yaygn eitim kurumlar, iletmeler ve kendi kendine mesleki yeterlikkazanmak isteyen bireyler modllere internet zerinden ulalabilirler.</p><p> Baslm modller, eitim kurumlarnda rencilere cretsiz olarak datlr.</p><p> Modller hibir ekilde ticari amala kullanlamaz ve cret karlndasatlamaz.</p></li><li><p>8/9/2019 Biliim Teknolojileri - 16 - Temel Algoritmalar</p><p> 3/47</p><p>i</p><p>NDEKLERNDEKLER..........................................................................................................................iAIKLAMALAR ....................................................................................................................iiGR .......................................................................................................................................1RENME FAALYET-1.....................................................................................................31. SIRALAMA .........................................................................................................................3</p><p>1.1. Ekleme Sralamas ..........................................................................................................41.2. Balon Sralamas ............................................................................................................71.3. Kabuk Sralamas ...........................................................................................................81.4. Hzl Sralama .............................................................................................................. 101.5. Sralama Algoritmalar ................................................................................................. 12UYGULAMA FAALYET ............................................................................................... 14LME VE DEERLENDRME .....................................................................................15</p><p>RENME FAALYET-2................................................................................................... 162. ARAMA .............................................................................................................................16</p><p>2.1. Sral (Ardk) Arama..................................................................................................162.2. kilik Arama .................................................................................................................182.3. Kyma (Hashing) Yntemi...........................................................................................19</p><p>2.3.1. Kyma Fonksiyonu ..............................................................................................192.3.2. Kyma Ynteminde akmalar ..........................................................................202.3.3. Kyma Ynteminde Arama.................................................................................. 20</p><p>UYGULAMA FAALYET ............................................................................................... 22</p><p>LME VE DEERLENDRME .....................................................................................23RENME FAALYET-3................................................................................................... 243. KOD YLETRME .........................................................................................................24</p><p>3.1. Doru Veri Yapsn Semek ....................................................................................... 243.2. Doru Algoritmay Semek .........................................................................................253.3. Kaynak Kodu yiletirmek ...........................................................................................25UYGULAMA FAALYET ............................................................................................... 29LME VE DEERLENDRME .....................................................................................30</p><p>MODL DEERLENDRME ..............................................................................................31CEVAP ANAHTARLARI .....................................................................................................32SZLK ................................................................................................................................ 33</p><p>KOD RNEKLER................................................................................................................34NERLEN KAYNAKLAR..................................................................................................42KAYNAKA .........................................................................................................................43</p><p>NDEKLER</p></li><li><p>8/9/2019 Biliim Teknolojileri - 16 - Temel Algoritmalar</p><p> 4/47</p><p>ii</p><p>AIKLAMALARKOD 481BB0028</p><p>ALAN Biliim Teknolojileri</p><p>DAL/MESLEK Alan Ortak </p><p>MODLN ADI Temel Algoritmalar</p><p>MODLN TANIMISralama ve arama ile ilgili program yazm, koduiyiletirme ile ilgili renme materyalidir.</p><p>SRE 40/24</p><p>N KOUL Veri Yaplar modln alm olmak.</p><p>YETERLK Temel algoritmalar yapmak</p><p>MODLN AMACI</p><p>Genel AmaGerekli ortam salandnda, sralama ve arama ile</p><p>ilgili algoritmalar yazabilecek, programlamann sonaamas olarak kodu iyiletirebileceksiniz.Amalar</p><p>1. Sralama yapabileceksiniz.2. Arama yapabileceksiniz.3. Kodu iyiletirebileceksiniz.</p><p>ETM RETMORTAMLARI VEDONANIMLARI</p><p>Bilgisayar laboratuvar ve bu ortamda bulunan;bilgisayar, yazc, bilgisayar masalar, kt, kalem, lisansliletim sistemi program ve ak diyagram sembolleri ileilgili panolar.</p><p>LME VEDEERLENDRME</p><p>Her faaliyet sonrasnda o faaliyetle ilgilideerlendirme sorular ile kendi kendinizideerlendireceksiniz. Modl iinde ve sonunda verilenretici sorularla edindiiniz bilgileri pekitirecek,</p><p>uygulama rneklerini ve testleri gerekli sre iindetamamlayarak etkili renmeyi gerekletireceksiniz.Srasyla aratrma yaparak, grup almalarna katlarak veen son aamada alan retmenlerine danarak lme vedeerlendirme uygulamalarn gerekletireceksiniz.</p><p>AIKLAMALAR</p></li><li><p>8/9/2019 Biliim Teknolojileri - 16 - Temel Algoritmalar</p><p> 5/47</p><p>1</p><p>GRSevgili renci,</p><p>Her eyden nce herkes bir programlama dilini renebilir. Bilgisayar programlamayksek bir zek ve matematik bilgisi gerektirmez. Sadece asla vazgememe sabr verenme istei yeterlidir.</p><p>Programlama bir hnerdir. Baz insanlar doal olarak dierlerinden daha iyidir, amaherkes pratik yaparak iyi olabilir. Baaramamaktan korkmak yerine, kendinizi bu maharetevererek, renmek iin uran. Programlama elencelidir, fakat yanl almayntemleriyle sinir bozucu olabilir ve zamannzn boa gemesine neden olabilir. Busebeple bu modlleri takip ederek, en az sknt ve en yksek memnuniyet ile programlamayreneceksiniz.</p><p>Bu modl ile kazanacanz bilgiler sralama ve arama ile ilgili program yazmak vekodu iyiletirme yntemlerini kullanmaktr. Modl bitirdiinizde anlamadnz yerleritekrar okuyup, uygulaynz.</p><p>Bu modl programlama temelleri modllerinin ilk drt modlnde gsterilenkonularn bir araya gelmi hlidir. Takldnz yerlerde eski modllerdeki bilgilere (diziler,veri yaplar, dngler) geri dnerek uygun konulara gz atnz.</p><p>GR</p></li><li><p>8/9/2019 Biliim Teknolojileri - 16 - Temel Algoritmalar</p><p> 6/47</p><p>2</p></li><li><p>8/9/2019 Biliim Teknolojileri - 16 - Temel Algoritmalar</p><p> 7/47</p><p>3</p><p>RENME FAALYET-1</p><p>Programda sralama ile ilgili ksmlar yazabileceksiniz.</p><p>Bu faaliyet ncesinde hazrlk amal aada belirtilen aratrmafaaliyetlerini yapmalsnz.</p><p> Kitaplnzda kark hlde bulunan ansiklopedilerinizi veya dergilerinizi nas lsral hle getirirsiniz? Dzenli olarak durmasnn faydalar neler olabilir?</p><p> Bir yerden bir yere gitmek iin birok alternatifiniz olabilir. En avantajl yolunasl seersiniz? En ksa yol bulma problemi ile ilgiliaratrma yapnz. rnein IETT sitesini ve GoogleEarth programlarn inceleyebilirsiniz.</p><p> Doada bulunan motifler, simetri ve fraktal hakkndaaratrma yapnz. Mesela Fibonacci say dizisi ileayieinin ekirdekleri ayn ekilde sralanr.</p><p>1. SIRALAMA</p><p>Genellikle sralama (sorting) ilemlerini veritabannda kullanrz.sim bilgileri harf srasnda, telefon bilgileri alan kodlarna sral olarakistenebilir. Programmz bu olanaklar salamaldr. ok gerekli olan bu</p><p>ilemlerin algoritmas karmak olabilir. Programnzn sralama hz danemlidir. rnein 15 ismin sralanmas dakikalarca srmemelidir.</p><p>RENME FAALYET1</p><p>AMA</p><p>ARATIRMA</p></li><li><p>8/9/2019 Biliim Teknolojileri - 16 - Temel Algoritmalar</p><p> 8/47</p><p>4</p><p>Bu blmde greceiniz bilgisayar bilimi almalar, en ksa srede en etkili ekilde</p><p>sralama iin dzenlenmitir.</p><p>Byk O Gsterimi</p><p>Bir algoritmann etkinliini lmek iin bilgisayar programclar Byk OGsterimini tasarlamlardr. Byk O, bir algoritmann ynetmesi gereken bilgimiktarnn ilenme hzn ler.</p><p>Programclar genellikle ayn miktardaki verinin, farkl algoritmalardaki ilem sresinibilmek isterler. Ortalama ve en kt durum senaryosu retirler. Byk O sayesindeprogram iin en uygun algoritma seilir.</p><p>Mesela isimlerin sralanaca bir algoritmada, isimlerin says programn hznetkiler. Bu O(n) ile gsterilir. O sralama bykl, n de nesne saysdr. nboyutundaki bir problemin zmnde geen adm says T(n) = 4n - 2n + 2 olarakbulunabilir.</p><p>1.1. Ekleme Sralamas</p><p>Ekleme sralamas (insertion sort) aslnda bir kart oyunundaki kartlarn sralanmasnabenzetilebilir. Dank durumdaki kartlardan iki tanesini elinize alrsnz, ncsndierlerinin yannda uygun bir yere eklersiniz. Her kart aldnzda dierlerinin iindenuygun olan yere eklersiniz. Bylece kartlar sral hle gelir.</p><p>Bu yntem ile basite program, kark olan saylar u admlar ile sralar:1. lk iki eleman listeden al np, karlatrlr, gerekirse yerleri deitirilir.2. Bir sonraki eleman alnp, nceki sral elemanlar iinde uygun yere eklenir.3. kinci adm sralama bitene dek tekrar edilir.</p><p>Resim 1.1: Ekleme sralamas yntemi</p></li><li><p>8/9/2019 Biliim Teknolojileri - 16 - Temel Algoritmalar</p><p> 9/47</p><p>5</p><p>Ekleme sralamasnda nce diziye* rastgele deerler ykleriz. Dizinin ikinci</p><p>elemanndan balayan bir ana dng iinde program yazarz. Bir sonraki dizi eleman geiciolarak bir deikene aktarldktan sonra, bu deeri aktif dizi eleman ile karlatrrz. Eergeici deer kk ise baka bir dngde, sral olan ksmda bu deerin yeri bulunur. Dizisralanana dek bu ilem devam eder.</p><p>Ekleme Sralamas programnn 5 elemanl dizi iin ak emas aadaki gibidir:</p><p>Resim 1.2: Ekleme Sralamasnn ekran grnts</p><p> Ekleme sralamas rneinin sahte kodlarn yaznz.</p><p>* Diziler, programlama dillerinde genellikle 0 veya 1 indis deeri ile balarlar.</p></li><li><p>8/9/2019 Biliim Teknolojileri - 16 - Temel Algoritmalar</p><p> 10/47</p><p>6</p><p>Resim 1.3: Ekleme sralamas ak emas</p></li><li><p>8/9/2019 Biliim Teknolojileri - 16 - Temel Algoritmalar</p><p> 11/47</p><p>7</p><p>1.2. Balon Sralamas</p><p>Balon sralamasnda (bubble sort) kark durumdaki saylar suyun iindeki balonlargibi hareket ederek yerlerini bulurlar. Say lar tekrarl olarak kontrol edilerek yakn saylar biraraya getirilir.</p><p>1. lk iki eleman karlatrlr, gerekirse yerleri deitirilir.2. Listede bir sonraki elemana gidilerek, bir nceki eleman ile karlatrlr.3. Liste sonuna kadar 2. adm tekrar edilir.4. 1 ve 3. adm, tm listenin sralamas bitene dek tekrar edilir.</p><p>Resim 1.4: Balon sralamas yntemi</p><p>nce veri listesi hazrlanr. n artl bir ana dng iine, snrlar ilk elemandansondan bir nceki elemana kadar olan bir dng yaplr. Seili elemann deeri ile dizininsonraki elemannn deeri karlatrlr. Eer byk ise iki dizi eleman yer deitirilir. Dizisonuna kadar tarama ve yer deitirme ilemleri devam eder. Bu dng tekrar edilir ve</p><p>deiiklik kalmam ise ana dng sonlandrl r.</p><p> Balon sralamas rneinin sahte kodlarn yaznz.</p><p>Resim 1.5: Balon sralamasnn ekran grnts, 13 rakamna dikkat ediniz</p></li><li><p>8/9/2019 Biliim Teknolojileri - 16 - Temel Algoritmalar</p><p> 12/47</p><p>8</p><p>Resim 1.6: Balon sralamas ak emas</p><p>Her iki algoritmann ilem admlarn karlatrnz. Kark listenin ka admdasralandn bulunuz.</p><p> Dizilerin maksimum snrlarn deitirerek, ka admda sralamann bittiini testediniz.</p><p>1.3. Kabuk Sralamas</p><p>Kark durumdaki listede, en sondaki eleman en baa getirmek zaman kaybdr. Busebeple programclar kabuk sralamas (shell sort) algoritmasn gelitirmilerdir.</p><p>Bl ve ynet mant ile tm dizinin sralanmas yerine, kk paralar halinde dizi</p><p>sralanr. Kk listeler sralandktan sonra, listeler birletirilir.</p></li><li><p>8/9/2019 Biliim Teknolojileri - 16 - Temel Algoritmalar</p><p> 13/47</p><p>9</p><p>Aslnda kabuk sralamas balon ve ekleme sralamasn hzlandrmak iin</p><p>gelitirilmitir. Yani farkl bir sralama algoritmas deildir.1. Byk liste kk listelere blnr.2. Kk liste balon veya ekleme sralamas ile sralanr.3. Resim 1.7deki rnekte 15 ve 29 rakam sralanmasna gerek yoktur. 16 ve 4</p><p>rakam sralanr, 78 ise ileme girmez.4. 3. admda sadece 4 ve 16nn yeri deiir, tekrar dizi kk listelere blnr.5. Dizide 15, 78 ve 16 sralanr, 4 ve 29 rakamlarnn sralanmas na gerek yoktur.6. Liste sralamas tamamlanana kadar 2 ve 4. admlar tekrarlanr.</p><p>Resim 1.7: Kabuk sralamas yntemi</p><p> Kabuk sralamas sahte kodlar aadaki gibidir. Ak emasn hazrlaynz.</p><p>Resim 1.8: Kabuk sralamas ekran grnts</p></li><li><p>8/9/2019 Biliim Teknolojileri - 16 - Temel Algoritmalar</p><p> 14/47</p><p>10</p><p>Bala</p><p>Saysal Dizi Veriler(5)</p><p>Saysal i, Geici, Dur, Ge, X, Snr</p><p>Yaz; "Sralanacak veriler:"Dng i = 1, 5, 1</p><p>Veriler(i) = Rasgele(100)</p><p>Yaz; Veriler(i)</p><p>Dng Bitti</p><p>X = tamsay(5 / 2)ken (X &gt; 0)</p><p>D u r = 0</p><p>Snr = 5 Xken (Dur = 0)</p><p>G e = 0</p><p>Dng i = 1, S</p><p>n</p><p>r, 1</p><p>Eer (Veriler(i) &gt; Veriler(i + X)) seGeici = Veriler(i)</p><p>Veriler(i) = Veriler(i + X)</p><p>Veriler(i + X) = Geici</p><p>Ge = 1</p><p>Eer BittiDng Bitti</p><p>Snr = G e XEe r G e = 0 s e D u r = 1</p><p>ken Bitti</p><p>X = tamsay( X / 2 )ken BittiYaz; "Sral liste:"</p><p>Dng i = 1, 5, 1Yaz; Veriler(i)</p><p>Dng Bitti</p><p>Bitir</p><p>1.4. Hzl Sralama</p><p>Hzl sralama (quick sort) dier yntemlere gre daha ok kullanl r. Bu yntemdelistenin ortasndan bir eleman alnr, elemann deerine gre sol veya sadaki deerler yerdeitirir.</p><p>Resim 1.9: Hzl sralama yntemi</p></li><li><p>8/9/2019 Biliim Teknolojileri - 16 - Temel Algoritmalar</p><p> 15/47</p><p>11</p><p>Liste yarya blndkten sonra, her ayrlan para tekrar yarya blnr. Alt paralar</p><p>kendi aralarndasralanr. Kk paralar birletirilerek tm listenin sral hali oluturulur.1. Listenin ortasndan bir eleman seilir. Seili elemandan byk olan elemanlar</p><p>saa, kk olanlar sola yer deitirilir.2. 1. adm listenin her yars iin tekrar edilir.3. Kk listeler birletirilir, sral liste elde edilir.</p><p>Kendini tekrar eden fonksiyonlara tekrarlamal - recursive fonksiyon denir. Basitolarak fonksiyonun kendini armasdr. Hzl sralamada bu yntem kullanlyor. Busebeple sralama iin alt program yapmamz gereklidir.</p><p>Resim...</p></li></ul>