WALKER

Dasturchi, frilanser, gik va introvert

Kategoriya

Algoritmlar

by Sherzod Shermukhamedov

Dynamic programming

1_yEugK-e5TyuSMPsjLDpb1Q

Dynamic programming (DP, dinamik dasturlaş) deb muammoni kiçik masalalarga ajratib, ularni faqat bir marta yeçiş va natijani keyingi bir xil tipdagi masalada işlatiş uçun saqlab turiş texnikasiga aytiladi.

by Sherzod Shermukhamedov

NFA simulyatsiyasi va API

maxresdefault

NFA simulyatsiyasini körib çiqişdan avval NFAning özini kodda qanday ifodalaşni körib çiqamiz. Avvalgi maqolada aytib ötilganidek, NFAda 0 dan M gaça state'lar + accept state mavjud. M - bu yerda qavs içiga olingan regular expression'dagi belgilar soni. Masalan ((A*B|AC)D) regexp uçun NFA state'lari

by Sherzod Shermukhamedov

Regular expressions

dbnauyuy7y1o3k839iny

Regular expression (yana regex, regexp) - qidiriş patternini belgilab beruvçi belgilar ketma-ketligi. Odatda regex'lar matn içida qidiruv algoritmlarida sözlarni topiş (find), topiş va almaştiriş (find & replace), hamda kiritilgan ma'lumotni tekşiriş uçun işlatiladi.

by Sherzod Shermukhamedov

Matn içida qidiruv. Boyer-Moore algoritmi

boyer-moore-algorithm-1-638

Avvalgi mavzuda ötganimiz - Knuth-Morris-Pratt algoritmi yordamida biz matn içida qidiruvni O(N + M) vaqt içida bajara olamiz. Navbatdagi algoritm - Boyer-Moore algoritmi bizga O(N) ni kafolatlay olmasada, amaliyotda KMPdan samaraliroq işlaydi. Örganişga ham osonroq ;)

by Sherzod Shermukhamedov

Matn içida qidiruv. Brute-force yondaşuvi

image-from-rawpixel-id-911496-jpeg

Matn içida söz/ibora qidiruv (substring search) algoritmlari bilan tanişib çiqişni boşlaymiz. Qöyiladigan masala juda oddiy. N uzunlikdagi matn içidan M uzunlikdagi iborani (pattern) topiş kerak bölsin. Bunda matn juda katta hajmda, pattern esa juda kiçik - bir-ikki sözdan iborat.

by Sherzod Shermukhamedov

Ternary search tries

Binary search tree

Ternary search tries (TST, uçlamçi qidiruv trie) R-way tries'dagi kamçilikka yeçim ölaroq tavsiya etiladi. TSTda belgilar indeks körinişida emas, node içida saqlanadi (R-way tries'da belgilar indeks nomer sifatida saqlanardi). Şuningdek har bir node uç çild'ga ega: kiçikroq (çap), teng (örtada), kat