taggimpu (sanklishtata)

ganana samardhyam siddhaantam mariyu ganana sanklishtata siddhaantamlo, taggimpu anedi oka samasyanu maroka samasyaga maarchadaaniki oka algorithm. oka samasya nundi maroka samasyaku taginanta samarthavanthamaina taggimpunu rendava samasya kaneesam modati samasya vale kashtamani choopinchadaaniki upayoginchavacchu.
samasya "bii" nuu samarthavantamgaa parishkarinchadaaniki oka algorithm (adhi unikilo unte) kooda samasya "eah" nuu samarthavantamgaa parishkarinchadaaniki upa-rutinga upayoginchagaligithe, akaaranamgaa, samasya "eah" nuu samasya "bii" gaa tagginchavachhu. idhi nijamainappudu, "a" nuu parishkarinchadam anedi "b" nuu parishkarinchadam kante kashtam kaadu. "kathinamainadi" antey icchina sandarbhamlo avasaramaina ganana vanarulapai adhika anchanaa veyadam (udhaa.zii.adhika samaya sanklishtata, ekkuva memory avasaram, single-thread solutiontho poliste samaantara parishkaram kosam adanapu hardware processor korla khareedaina avasaram modalainavi.). a" nundi "b" kuu taggimpu unikini, saadhaaranamgaa upayoginchabadutunna taggimpu rakanni suuchimchadaaniki ≤ paie subscripto "a" ≤ m "b" anae sankshipta sangnaamaanamlo vraayavacchu (m: mapping taggimpu, p: bahupadi taggimpu).
oka nirdishta rakam taggimpula dwara samasyala samitipai utpannamayye ganita nirmaanam saadhaaranamgaa oka puurva kramaanni yerparustundi, dheeni samanatva taragatulanu parishkarinchaleni mariyu sanklishtata taragatula sthaayilanu nirvachinchadaaniki upayoginchavacchu.
parichayam.
taggimpulanu upayoginchaalsina rendu pradhana paristhitulu unnaih
taggimpuku chaalaa sulabhamaina udaaharana "gunakaaram" nundi "vargamu" varaku untundi. elaa cheyaalo manaku telisinadantaa jodinchadam, teesiveyadam, chaturasraalu teesukovadam mariyu rendutho bhaaginchadam anie anukundam. eee krindi suutramtoe kalipi, edainaa rendu sankhyala gunakaaram pondadaaniki manam eee gnaanaanni upayoginchavachhuh
manaku itara disalo kooda taggimpu undhi; spashtamgaa, manam rendu sankhyalanu guninchagaligite, manam oka sankhyanu vargaparachavachhu. eee rendu samasyalu samanamga kashtamani idhi suuchistunnatlu telustondi. eee rakamaina taggimpu turing taggimpuku anugunamgaa untundi.
ayithe, manam squaring functionnu okasari matrame upayoginchagalamani parimitini jodiste, taggimpu chaalaa kashtamavutundi. eee sandarbhamlo, gunanamtho sahaa anni praathamika ankaganita karyakalapalanu upayoginchadaaniki manaku anumati unnappatikee, saadhaaranamgaa etuvanti taggimpu undadu, endukante kaavalasina phalitaanni oka vargamgaa pondadaaniki manam modata daani vargamuulaanni lekkinchaali, mariyu eee vargamoolamu suutram _ 2 vanti ahetuka sankhya kaavacchu, dheenini hetubaddha sankhyalapai ankaganita karyakalapala dwara nirminchalemu. ayithe, itara disalo velthe, manam khachitamgaa oka sankhyanu kevalam oka gunanamtho, chivarilo matrame vargaparachagalamu. eee parimita taggimpu roopaanni upayoginchi, gunakaaram anedi saadhaaranamgaa vargamu kante kashtamani aascharyakaram kaani phalitaanni chuupinchaamu. idhi aneka-oka taggimpuku anugunamgaa untundi.
aastulu.
taggimpu anedi oka mundastu arder, idhi p (n) × p (n) paie reflexive mariyu transitive sambandham, ikkada p (n) anedi sahaja sankhyala power sett.
taggimpula rakalu mariyu anuvartanaalu.
paie udaaharanalo vivarinchinatlugaa, ganana sanklishtatalo upayoginche rendu pradhana rakaala taggimpulu unnaayi, aneka-oka taggimpu mariyu turing taggimpu. aneka-oka taggimpulu oka samasya yokka "sandarbhaalanu" maroka samasya yokka "sandarbhaalaku" mapp chestaayi; turing taggimpulu oka samasyaku parishkaranni "lekkistaayi", maroka samasyanu parishkarinchadam sulabham anie bhaavinchi. aneka-oka taggimpu anedi turing taggimpu yokka balamaina rakam, mariyu samasyalanu vibhina sanklishtata taragatulugaa vaeru cheyadamlo marinta prabhaavavantamgaa untundi. ayithe, aneka-oka taggimpulapai perigina parimitulu vaatini kanugonadam marinta kashtataram chestaayi.
taragatiloni prati samasya aaa samasyaku taggithe, adhi tharagathilone unte sanklishtata taragatiki oka samasya puurtavutumdi. eee konamlo samasya varganni suuchistumdi, endukante daaniki edainaa parishkaram, taggimpulatoe kalipi, taragatiloni prati samasyanu parishkarinchadaaniki upayoginchavacchu.
ayithe, upayogakaramgaa undalante, taggimpulu "sulabham" ayi undaali. udaaharanaku, booliyan santruptikara samasya vanti parishkarinchadaaniki kashtamaina enpi-puurti samasyanu oka chinna samasyaga tagginchadam chaalaa saadhyame, oka sankhya sunnaki samanam kaadaa anie nirnayinchadam vantivi, taggimpu yantram samasyanu ghaataanka samayamlo parishkarinchadam dwara mariyu parishkaram untene sunna avtput cheyadam dwara. ayithe, idhi peddagaa saadhinchadu, endukante manam kotta samasyanu parishkarinchagaliginappatiki, taggimpu cheyadam anedi paatha samasyanu parishkarinchadam antha kashtam. adevidhamgaa, ganana cheyaleni functionnu tagginchadam anedi nirnayinchaleni samasyanu nirnayinchaleni samasyaga taggistundi. maikhel sipsar "ganana siddhaantaaniki parichayam" loe etthi chupinatlugah "taragatiloni saadhaarana samasyala sanklishtataku sambandhinchi taggimpu sulabham ayi undaali...] taggimpunu lekkinchadam kashtamgaa unte, puurti samasyaku sulabhamaina parishkaram anedi tagginche samasyalaku sulabhamaina parishkaranni ivvadu."
anduvalla, taggimpu yokka tagina bhavana adhyayanam cheyabadutunna sanklishtata taragati meeda aadharapadi untundi. sanklishtata taragati enn. pii. mariyu bahupadi sopanakramam vanti kathinamaina taragatulanu adhyayanam chesetappudu, bahupadi-samaya taggimpulu upayoginchabadataayi. enn. sii. mariyu enn. ell. vanti pii. lopala taragatulanu adhyayanam chesetappudu, logg-space taggimpulu upayoginchabadataayi. yantraala dwara samasyalu parishkarinchagalavaa ledhaa anie choopinchadaaniki ganana siddhaantamlo taggimpulu kooda upayoginchabadataayi; eee sandarbhamlo, taggimpulu ganana vidhulaku matrame parimitam cheyabadataayi.
optimisation (garishteekarana ledhaa kanishteekarana) samasyala vishayamlo, memu tarachugaa ujjaayimpu-parirakshana taggimpu paramgaa aalochistaamu. manaku rendu optimisation samasyalu unnayani anukundam, oka samasya yokka sandarbhaalanu marokati yokka sandarbhaalalo mapp cheyavachu, taruvaati samasya yokka sandarbhaalaku daadaapu saraina parishkaralanu tirigi maarchavacchu, tadwara modatidaaniki daadaapu saraina parishkaralanu andistundi. eee vidhamgaa, samasya b yokka sandarbhaalaku daadaapu-vaanchaneeya (ledhaa vaanchaneeya) parishkaralanu kanugone optimisation algorithm (ledhaa ujjaayimpu algorithm) mariyu samasya a nundi samasya b kii samarthavanthamaina ujjaayimpu-parirakshana taggimpu unte, kuurpu dwara manam oka optimisation algorithamnu pondutaamu, idhi samasya a yokka sandarbhaalaku daadaapu-vaanchaneeya parishkaralanu istundi. ujjaayimpu-samrakshinche taggimpulu tarachugaa ujjaayimpu phalitaala kaatinyaanni niroopinchadaaniki upayoginchabadataayih konni optimisation samasya a anedi kontha α kante merugaina karakam lopala anchanaa veyadam kashtamaite (kontha sanklishtata ooha prakaram), mariyu β-approximation-samasya a nundi samasya b varaku taggimpu unte, samasya b anedi α/β karakam lopala anchanaa veyadam kashtam anie manam nirdhaarinchavacchu.
udaaharanalu.
vivaranaatmaka udaaharana.
oka bhasha nirnayinchalenidani niroopinchadaaniki aagipoye samasya nundi taggimpunu elaa upayoginchaalo eee krindi udaaharana choopistundi. icchina turing yantram "m" input string "w" paie agutunda (angeekarinchadam ledhaa tiraskarinchadam dwara) anie nirnayinche samasya "h" ("m", "w") anie anukundam. eee bhasha nirnayinchalenidigaa prasiddhi chendindi. icchina turing yantram "m" angeekarinche bhasha khaliga undaa (maroe maatalo cheppalante, "m" edainaa teegalanu angeekaristundaa) anie nirnayinchadamlo "e" ("m") samasya undani anukundam. h" nundi taggimpu dwara "e" anedi nirnayinchalenidi anie memu chuupistunnaamu.
vairudhyaanni pondadaaniki, "r" anedi "e" kii nirnayaatmakamainadi anukundam. h" (idhi unikilo ledani manaku telusu) kosam nirnayaatmaka "s" nuu utpatti cheyadaaniki dheenini upayogistaamu. m" mariyu "w" (turing yantram mariyu kontha input string) ichinatlayithe, eee krindi pravartanatho "s" ("m", "w") nuu nirvachinchandih "s" anedi turing yantram "n" nuu srushtistundi, idhi "n" kuu input string "w" mariyu "m" input "w" paie aagithene angeekaristundi, lekapothe aagadu. nirnayakudu "luu" ippudu "r" ("n") nuu moolyaankanam chesi "n" dwara aamodinchabadina bhasha khaliga undho ledho tanikhi cheyavachu. r" "n" nuu angeekaristhe, appudu "n" dwara aamodinchabadina bhasha khaliga untundi, kabatti mukhyamgaa "m" input "w" paie aagadu, kabatti "s" tiraskarinchavacchu. r" "n" nuu tiraskariste, appudu "n" dwara aamodinchabadina bhasha khaliga undadu, kabatti "m" input "w" paie aagipotundi, kabatti "s" angeekarinchavacchu. anduvalla, manaku "e" kosam nirnayaatmaka "r" unte, edainaa yantram "m" kosam "h" ("m", "w") mariyu input "w" kosam aagipoye samasya kosam nirnayaatmaka "s" nuu utpatti cheyagalugutamu. atuvanti "luu" unikilo undavani manaku telusu kabatti, "ii" bhasha kooda nirnayinchalenidi.

