1. Dasturiy ta’minot va uning turlari

Tekislikda chiziqlar kesishgan sohalarni qidirish algoritmi (Sweep Line)

Chiziqli qidirish algoritmi qanday ishlaydi
Kerakli joyni qidirish jarayonini quyidagi tartibda olib borish qulay bo’ladi. 2-elementdan boshlab har bir elementni qarab chiqamiz, ya’ni har bir elemento’zidan oldin turgan element bilan solishtiriladi. Agar qaralayotgan element kichik bo’lsa, oldinda turgan element bilan o’rin almashadi va yana o’zidan oldinda turgan element bilan solishtiriladi, jarayon shu kabi davom etadi. Bu jarayon quyidagi shartlarning birortasi bajarilganda to’xtatiladi: 1. x elementi oldida uning kalitidan kichik kalitli a(j) elementi chiqqanda. 2. x elementi oldida element qolmaganda.
Aytib o’tganimizdek, bu algoritm juda ham sodda ishlaydi va tasavvur qilishga ham oson.

• 
  Arrayning birinchi elementidan tekshirish boshlanadi.
  
• 
  Element olinadi va u berilgan shartga tekshirib ko’riladi.
  
• 
  Agar shartni qanoatlantirsa, uning qiymati yoki joylashgan o’rni (qiymati yoki shunchaki true) qaytariladi va algoritm tugaydi.
  
• 
  Shart qanoatlantirilmasa, keyingi elementga o’tiladi va 2-qadamga qaytiladi
  
• 
  Array tugab, element topilmasa, buni anglatuvchi qandaydir qiymat qaytariladi (-1 yoki false)
  

Ko’rinishidan ko’pdek tuyulsa ham, aslida bu algoritm hayotdagi odatiy qidirish bilan bir xil ishlaydi. Keling uni visual holda tasavvur qilamiz.
Hisoblash geometriyasida , supurish chizig'i algoritmi yoki tekislik tarash algoritmi , Evklid fazosida turli muammolarni hal qilish uchun kontseptual tozalash chizig'ini yoki tarash sirtini ishlatadigan algoritmik paradigmadir . Bu hisoblash geometriyasining asosiy usullaridan biridir.Ushbu turdagi algoritmlarning g'oyasi chiziqni (ko'pincha vertikal chiziq) tekislik bo'ylab supurib yoki harakatlantirib, ba'zi nuqtalarda to'xtashini tasavvur qilishdir. Geometrik amallar kesishish chizig'i to'xtaganda yoki unga yaqin joylashgan geometrik ob'ektlar bilan chegaralanadi va chiziq barcha ob'ektlar ustidan o'tgandan keyin to'liq yechim mavjud.

73.