|
U hali ochilmagan eng yaqin tugunni ochko'zlik bilan tanlash uchun ustuvor navbatdan foydalanadi va barcha chekkalarida bo'shashish jarayonini amalga oshiradi. (Kimdan)
Misol jalb qilingan
Masalan, biron bir kishi manba A va boradigan joy D o'rtasidagi eng qisqa masofani, shu bilan birga uning manbasi va borishi orasidagi eng qisqa yo'l bo'lgan pastki yo'lni hisoblashni xohlaydi. Keling, Dijkstra algoritmi qanday ishlashini ko'rib chiqamiz;
U har qanday pastki yo'l, aytaylik, A va D tepaliklari orasidagi eng qisqa yo'lning B dan D gacha bo'lgan pastki yo'lini, shuningdek, B va D tepalari orasidagi eng qisqa yo'l, ya'ni har bir pastki yo'l eng qisqa yo'l.
Bu erda Dijkstra algoritmi ushbu xususiyatni teskari yo'nalishda ishlatadi, ya'ni masofani aniqlash paytida biz har bir tepaning boshlang'ich tepadan masofasini ortiqcha baholaymiz, so'ngra har bir tugunni va uning qo'shnilarini ushbu qo'shnilarga eng qisqa pastki yo'lni aniqlash uchun tekshiramiz.
Shu tarzda algoritm ochko'z yondashuvni navbatdagi ishonchli echimni izlash orqali amalga oshiradi va yakuniy natija butun muammo uchun mos echim bo'lishini kutadi.
Sodda savollar
Algoritm :
Algoritm qandaydir natijaga erishish uchun bajariladigan amallarning tartibi(ketma-ketligi) ni tavsiflovchi yo’riqnomalar to’plami.Algoritm bajaruvchisi odatda kompyuter bo’ladi. Lekin algoritm tushunchasi faqat kompyuter dasturiga tegishli emas. Masalan ovqat pishirish yo’riqnomalari ham algoritm.
Algoritm ishlash vaqti:
Agar massivdagi birinchi uchraydigan indeks izlanayotgan bo’lsa u holda chiziqli qidiruv algoritmining ishlash vaqti:
Eng yaxshi holatda: O(1). Ya’ni izlanayotgan element qaralayotgan intervalning boshida bo’lsa.
Eng yomon holatda: O(n). Ya’ni izlanayotgan element izlanayotgan intervalning oxirida bo’lsa yoki umuman uchramasa.
n – izlanayotgan intervaldagi elementlar soni. Yuqoridagi misol uchun n=R-L+1.
Chiziqli qidiruv algoritmi qidirilayotgan interval uzunligi kichik bo’lgan vaqtdagina effektiv bo’ladi.
Jon Fon Neyman
John fon Neumann (ing. John von Neumann / vɒn ˈnɔɪmən /; yoki Johann fon Neumann, nemis Johann von Neumann; tug'ilish paytida Janos Lajos Neumann, venger Neumann Janos Lajos, IPA: [nojmɒn ˈjaːˈno]; 28 dekabr - 8 fevral, 1957 yil, Vashington) - Venger-amerikalik matematik, fizik va yahudiy kelib chiqadigan o'qituvchi, u kvant fizikasi, kvant mantig'i, funktsional tahlil, to'plamlar nazariyasi, informatika, iqtisod va boshqa fan sohalariga muhim hissa qo'shgan.
U eng zamonaviy kompyuterlarning arxitekturasi (fon Neyman arxitekturasi deb ataladi), operator nazariyasini kvant mexanikasiga tatbiq etish (fon Neyman algebra) bilan bog'liq bo'lgan shaxs, shuningdek Manxetten ishtirokchisi sifatida tanilgan. Loyiha va o'yin nazariyasi va uyali avtomatika kontseptsiyasining yaratuvchisi sifatida.
Fon Neymanning operator uzuklari nazariyasi bo'yicha asosiy ishi fon Neyman algebralari bilan bog'liq ishlar edi. Fon Neyman algebra - bu zaif operator topologiyasida yopilgan va identifikator operatorini o'z ichiga olgan Xilbert fazosidagi chegaralangan operatorlarning * -algebrasi.
Fon Neymanning ikki komutantli teoremasi, Ney Neyn algebrasining analitik ta'rifi algebraik ta'rifga tengligini, Hilbert fazosidagi chegaralangan operatorlarning * -algebrasi ekvivalentligini isbotlaydi, bu uning ikkinchi kommutator kichik guruhiga to'g'ri keladi.
1949 yilda Jon fon Neyman to'g'ridan-to'g'ri integral tushunchasini kiritdi. Fon Neymanning xizmatlaridan biri bu ajratiladigan Xilbert bo'shliqlarida fon Neyman algebralarining tasnifini omillar tasnifiga kamaytirishdir.
Charlz Hoar
Ser Charlz Antoni Richard Xoare yoki Toni Xoare yoki C.A. Xare; 1934 yil 11-yanvarda tug'ilgan, Kolombo, Seylon, Britaniya imperiyasi, hozirgi Shri-Lanka) - ingliz olimi, axborot fani va hisoblash sohasida ixtisoslashgan. U "tez saralash" algoritmini ishlab chiquvchisi sifatida tanilgan (1960), bu hozirgacha eng mashhur saralash algoritmi.
Uning ishining boshqa muhim natijalari: Z tilining spetsifikatsiyalari va ketma-ket jarayonlarning o'zaro ta'sirining parallel modeli (CSP, Communicating Sequential Process). Uning yutuqlari qatorida dasturlash tillarini aniqlash va loyihalash uchun foydalaniladigan to'g'ri dasturlarni yaratish uchun ilmiy asos bo'lgan Hoare Logic-ning rivojlanishi. Hoare dasturiy ta'minotni spetsifikatsiya qilish, loyihalash, tatbiq etish va unga xizmat ko'rsatishga bag'ishlangan bir qator maqolalar muallifi bo'lib, ular ilmiy natijalarning kompyuter ish faoliyatini yaxshilash va dasturiy ta'minotning ishonchliligini oshirish uchun muhimligini namoyish etadi.
Rekursiv algoritm
Funksiya o'ziga o'zi to'g'ridan-to'g'ri yoki qandaydir vosita orqali murojaat qilish jarayoniga rekursiya deyiladi va bunday funksiya rekursiv funksiya deb ataladi.
Kombinatorika:
Kombinatorikada chekli yoki muayyan ma’noda chekli deb faraz qilinuvchi to’plam elementlarini qismlarga ajratish, o’rinlashtirish, o’zaro joylash kabi masalalar o’rganiladi.
Kombinatsiya:
Kombinatorikaning asosiy tushunchasi bu kombinatsiya hisoblanadi.
Bu tushuncha yordamida ixtiyoriy to’plamning qandaydir sondagi elementlaridan tashkil topgan tuzilmalar ifodalanadi.Bu tuzilmalarning asosiy ko’rinishlari: o’rin almashtirish , o’rinlashtirish va guruhlash deb nomlanadi.
Graf:
“Graf” iborasi D. Kyonig tomonidan 1936 yilda graflar nazariyasiga bag‘ishlangan dastlabki darslikda uchraydi. Kyonig (Dénes König, 1884-1944) – venger matematigi.
Bu darslik olmon tilida yozilgan.
Graflar nazariyasi bo‘yicha tadqiqotlar natijalari inson faoliyatining turli sohalarida qo‘llaniladi. Ulardan ba’zilari quyidagilardir: boshqotirmalarni hal qilish; qiziqarli o‘yinlar; yo‘llar, elektr zanjirlari, integral sxemalari va boshqarish sistemalarini loyihalashtirish; avtomatlar, blok-sxemalar va kompyuter uchun programmalarni tadqiq qilish va hokazo.
Input:
Output
Bog’liqlik matritsasi
Insidentlik matritsasi
Samaradorlik
Saralash
Do'stlaringiz bilan baham: |
