1. Algoritm — orınlawshı ushın málim bir máseleni sheshiwge qaratılǵan kórsetpelerdiń anıq izbe-izligi. Algoritmlar bul kompyuter programmaları artı daǵı ideyalar. Algoritm orınlawshısı



Yüklə 339,36 Kb.
səhifə14/20
tarix05.09.2022
ölçüsü339,36 Kb.
#63425
1   ...   10   11   12   13   14   15   16   17   ...   20
shpor

23.Floyda algoritmi.
Floyda algoritminde kesteni toltiriw formulasi yaki kerisinshe:


24.Floyda warshl algoritimi.
Floyd Warshall algoritmı barlıq juplıqlar eń qısqa jol mashqalasın sheshiw ushın mólsherlengen. Mashqala berilgen shet vaznli jóneltirilgen grafik daǵı hár bir jup shıń arasındaǵı eń qısqa aralıqtı tabıw bolıp tabıladı
26. Ford-Bellman algoritmi. Graf ham onin manisleri berilgen bolsa, manislerden barliq tobelerge shekemgi en qisqa joldi tabiw maselesin qarastirayiq. Grafta bolsa teris salmaqlar berilgen boliwi mumkin. Biz bul masele ushin Deykstra algoritmin bilemiz. Deykstra teris salmaqtagi graflar ushin islemeydi. Bellman-Ford bolsa bunday graflar ushin isleydi. Bellman-Ford algoritmi awirliqtagi grafda bir tobeden basqa tobelerge en qisqa jollardi esaplaytugin algoritm. Ol Deykstradan aste isleydi, biraq kop qirli sebebi bazi shetki awirligi teris bolgan graflar ushin da orinlı. Eger grafta derekten erisiw mumkin bolgan teris cikl (yagniy qabirgalari teris maniske iye bolgan cikl) bar bolsa Bellman_ford cikldi aniqlap beriwi mumkin. Bellman-Ford algoritmi Deykstraga qaraganda kobirek kiriwler klasina qollaw imkaniyatin beredi




27. Terek tusinigi ham turleri. Terek – bul berilgenler strukturası bolıp, onda maǵlıwmatlar elementleri ierarxiyalıq túrde baǵdarlar(ssilkalar) menen baylanısqan boladı. Hár bir terek túbir túyininen ibarat bolıp, onnan terektiń hár bir elementine kiriwimiz múmkin. Túbir túyininen baslap hár bir túyin onıń balaları (childnode) sıpatında onıń menen baylanısqan 0 yaki onnan kóp túyinlerge iye. Terek bólimleri: Terek túbir túyini (root), japıraq túyini(leaf) hám ishki túyinlerden ibarat bolıp, hár bir túyin tuwrı sızıqlar menen baylanısqan (edge), biz onı qabırǵa dep ataymız. Túbir túyin(rootnode): bul terektiń eń joqarǵı túyini bolıp, barqulla 1 túyin boladı terek jaratılǵannan baslap hám biz basqa túyinlerge usı túyinnen shıǵa alamız. Mısaldaǵı 50-túyini túbir túyin esaplanadı. Ata-ana túyini(parentnode): Hár qanday túyinniń ata-anası usı túyinge baǵdarlanıwshı túyin boladı. Mısaldaǵı 50 túyini 20 hám 45 túyinleri ushın ata-ana túyini boladı, al 20 túyini 11, 46 hám 15 túyinleri ushın ata-ana túyini hám jánede 45 túyini 30 hám 78 túyinleri ushın ata-ana túyini boladı. Balaları túyini(childnode): ata-ana túyininen ssilkalar arqalı kórsetilgen túyinlerge aytamız. Mısaldaǵı 20 hám 45 túyinleri 50 túyininiń balaları, al 11, 46, hám 15 túyinleri 20 hám 30 túyininiń balaları, 78 túyini 45 túyininiń balası. Shegara: ata-ana túyinin bala túyini menen baylanıstırıwshı túyin shegara delinedi. Mısaldaǵı hár bir túyinlerdi tutastırıwshı sızıqtı qabırǵa dep ataymız. Japıraq túyin(leafnode): terektegi balaları joq túyinlerdi aytamız. Mısaldaǵı 11, 46, 15, 30 hám 78 túyinleri japıraq túyinler boladı. Ishki túyinler: keminde bir bala elementi bolǵan túyinlerge aytamız. Mısaldaǵı 50, 20 hám 45 túyinleri ishki túyinler. Binar terek – bul hár bir túyin maksimum 2 bala(child) elementine iye bolǵan terek berilgenler strukturasına aytamız. Bul degeni binary terektegi hár bir túyin bir yaki eki yaki ulıwma dawamshıǵa iye bolǵan túyinge aytamız. Binar terektegi hár bir túyin terektegi maǵlıwmatlar hám áwladlarǵa baǵdarlar (ssilkalar) dan dúzilgen. Jaǵdaylarına qarap balaların shep yaki oń balası dep aytamız. Binar terekte túyinler strukturası tómendegishe: Reference to the Left Child, Data, Reference to right Child. Terektiń diametri dep eki túyin arasındaǵı maksimal uzınlıqtaǵı jolǵa aytıladı. 1)Binar terek hár bir túyini shep hám oń terekke iye bolǵan túbirge iye terek bolıp tabıladı. Binar terektiń ushları terekti kórip shıǵıwdı túrli jollarına sáykes keletuǵın úsh tártibi bar bolıp: 1. Pre-order: Daslep túbir, keyin shep bólim terek, keyin oń bólim terek. 2. In-order: Daslep shep bólim terek, keyin túbir, keyin oń bólim terek. 3. Post-order: Daslep shep bólim terek, keyin oń bólim terek, keyin túbir. 2)Binar indekslengen terek yamasa Fenwick teregi massivtiń dinamikalıq variantı bolıp tabıladı. Ol massivte eki O(logn) waqıtlı ámeller qabıl etedi: aralıq sorawlardı esaplaw hám bahalardı jańalaw.Binar terektiń abzallıǵı sonda ol bizge nátiyjeli túrde massiv bahaların ózgertiw imkaniyatın beredi. 3)Segment tree eki ámel qabıl etetuǵın maǵlıwmatlar strukturası bolıp tabıladı: aralıq sorawdı ámelge asırıw hám massiv ma`nisin update qılıw. Segment terekler jıyındı sorawı, minimum soraw, maksimum



soraw hám sol sıyaqlı basqa sorawlardı qabıl etedi jáne bulardıń barlıǵında O(logn) waqıtlı eki ámelden paydalanadı. Segment terek tómendegi úshlari massiv elementleri bolǵan hám qalǵan elementleri aralıq sorawların ámelge asırıwǵa kerek bolatuǵın bahalardan ibarat terek.

Yüklə 339,36 Kb.

Dostları ilə paylaş:
1   ...   10   11   12   13   14   15   16   17   ...   20




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azkurs.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin