
saamoohik sanchaalan

saamoohik sanchaalan paraspar kriya key liye nirmaan khand hain, jinka upayog aksar samanantar prograaming sandarbh mein aiss. pee. aim. dee. algorithm mein kiya jaataa haye. isaliye, inn karyon koo kushalata seey puuraa karane mein ruchi haye.
saamoohik sanchaalan kaa ehsas sandesh paarit interfaces (aim. pee. aaee.) dwara pradaan kiya jaataa haye.
paribhaashaaen.
sabhi asymptotic runtime karyon mein, humm vilambata sootra _ 1, prati shabd sootra _ 2 sanchaar laagat, prasanskaran ikaaiyon kii sankhya sootra _ 3 aur prati node sootra _ 4 input aakar koo darshaate hain. aise mamalon mein jahaan hamaare paas ack seey adhik node parr praarambhik sandesh hain, humm maanate hain kii sabhi sthaaniya sandesh samaan aakar key hain. vyaktigat prasanskaran ikaaiyon koo sambodhit karane key liye humm sootra _ 5 kaa upayog karate hain.
yadi hamaare paas samaan vitaran naheen haye, tou i.ee. node sootra _ 6 mein aakar sootra _ 7 kaa sandesh haye, humm sootra _ 8 nirdhaarit karke runtime key liye ack oopari seema praapt karate hain.
ack vitarit smriti model maanaa jaataa haye. saajha smriti model key liye avadhaaranaaen samaan hain. haalaanki, saajha smriti pranali kuchh sanchaalan jaise prasaran () key liye hardware samarthan pradaan curr sakati haye, udaaharan key liye, joe suvidhajanak samvarti padhane kii anumati detaa haye. iss prakaar, naee algoridmic sambhaavanaaen upalabdh hoe sakati hain.
prasaran.
prasaran pattern kaa upayog ack prasanskaran ikai seey sabhi prasanskaran ikaaiyon mein detta vitarit karane key liye kiya jaataa haye, joe aksar input yaa vaishvik moolyon koo vitarit karane key liye aiss. pee. aim. dee. samanantar karyakramon mein aavashyak hotaa haye. prasaran koo cumm karane key pattern () key ack vyutkram sanskaran key roop mein vyakhya kii jaa sakati haye. shuru mein kewal mool sootra _ 9 sootra _ 10 sootra _ 11 key saath sandesh sootra _ 12 sangraheet kartaa haye. prasaran sootra _ 12 key dauran shesh prasanskaran ikaaiyon koo bheja jaataa haye, taaki antatah sootra _ 12 sabhi prasanskaran ikaaiyon key liye upalabdh hoe.
choonki formula _ 15 punaraavrittiyon key saath anukramik roop seey loop key liye ack karyanvayan ack baadha bunn jaataa haye, isaliye vibhajit karein aur jeeten drishtikon aam hain. ack sambhavana yeh haye kii ack dwipad vriksh sanrachana kaa upayog iss aavashyakta key saath kiya jaae kii sootra _ 3 koo dou kii shakti honey chaahiye. jaba ack prasanskaran ikai sootra _ 12 koo prasanskaran ikaaiyon key sootra _ 18 koo bhejane key liye jimmedaar hoti haye, tou yeh sootra _ 12 koo prasanskaran ikai sootra _ 20 koo bhejati haye aur prasanskaran ikaaiyon key sootra _ 21 key liye jimmedaari usey saunpati haye, jabaki isaki apani jimmedaari sootra _ 22 mein kaat dee jaati haye.
dwipadi vrikshon mein lambe sandesh sootra _ 12 key saath ack samasya hoti haye. sootra _ 12 kii praapt karane vaali ikai kewal sandesh koo anya ikaaiyon mein prasaarit curr sakati haye, jaba yeh puuraa sandesh praapt kartaa haye. iss beach, sanchaar network kaa upayog naheen kiya jaataa haye. isaliye dwiaadhaari pedon parr pipelining kaa upayog kiya jaataa haye, jahaan sootra _ 12 koo sootra _ 26 key aakar key sootra _ 27 key packets kii ack sarani mein vibhajit kiya jaataa haye. packets koo phir ack key baad ack prasaarit kiya jaataa haye, taaki sanchaar network mein detta teji seey vitarit kiya jaa sakey.
santulit dwiaadhaari vriksh parr pipelined prasaran sootra _ 28 mein sambhav haye.
cumm karein.
cumm karane key pattern kaa upayog vibhinn prasanskaran ikaaiyon seey detta yaa aanshik parinam ekatra karane aur unhein ack chune hue operator dwara vaishvik parinam mein sanyojit karane key liye kiya jaataa haye. sootra 3 prasanskaran ikaaiyon koo diye jaane parr, sandesh sootra 30 shuru mein prasanskaran ikai sootra 6 parr haye. sabhi sootra _ 30 koo sootra _ 33 dwara ekatrit kiya jaataa haye aur parinam antatah sootra _ 34 parr sangraheet kiya jaataa haye. kamee prachaalak sootra _ 33 cumm seey cumm sahayogi honah chaahiye. kuchh algorithm key liye ack tatasth tatva key saath ack commutative operator kii aavashyakta hoti haye. sootra _ 36, sootra _ 37, sootra _ 38 jaise prachaalak samanya hain.
karyanvayan key vichaar prasaran () key samaan hain. dwiaadhaari pedon parr pipelining key liye sandesh koo ghatak-vaar kamee key liye chhoti vastu key vector key roop mein darshaaya jaanaa chaahiye.
ack santulit dwiaadhaari vriksh parr pipelined reduce sootra _ 28 mein sambhav haye.
sabhi cumm.
yadi cumm karane key liye operation () key parinam koo sabhi prasanskaran ikaaiyon mein vitarit kiya jaanaa chaahiye tou sabhi-cumm karane vaale pattern (jise oleraduce bhee kahaa jaataa haye) kaa upayog kiya jaataa haye. sootra 3 prasanskaran ikaaiyon koo diye jaane parr, sandesh sootra 30 shuru mein prasanskaran ikai sootra 6 parr haye. sabhi sootra _ 30 koo ack prachaalak sootra _ 33 dwara ekatrit kiya jaataa haye aur parinam antatah sabhi sootra _ 6 parr sangraheet kiya jaataa haye. cumm karane key liye, prachaalak sootra _ 33 cumm seey cumm sahayogi honah chaahiye.
sabhi-cumm koo baad key prasaran () key saath ack cumm karane vaale sanchaalan key roop mein vyakhya kii jaa sakati haye. lambe sandeshon key liye ack sambandhit karyanvayan upayukt haye, jabaki chhote sandeshon key liye, vilambata koo ack hypercube () topology kaa upayog karke cumm kiya jaa sakata haye, yadi sootra _ 3 dou kii shakti haye. aul-reduce koo butterfly algorithm key saath bhee lagu kiya jaa sakata haye aur ishtatam vilambata aur bandwidth praapt kii jaa sakati haye.
sabhi-cumm sootra _ 28 mein sambhav haye, kyonki santulit dwiaadhaari pedon parr pipelining key saath sootra _ 28 mein cumm aur prasaran sambhav haye. titali algorithm key saath lagu kiye gaye sabhi-cumm usee asymptotic runtime koo praapt kartaa haye.
upsarg-raashi/scan.
upsarg-raashi yaa scan operation kaa upayog vibhinn prasanskaran ikaaiyon seey detta yaa aanshik parinam ekatra karane aur ack operator dwara madhyavarti parinamon kii ganana karane key liye kiya jaataa haye, joe una prasanskaran ikaaiyon parr sangraheet hotey hain. ise cumm karane key sanchaalan () key saamaanyikaran key roop mein dekhaa jaa sakata haye. sootra 3 prasanskaran ikaaiyon koo diye jaane parr, sandesh sootra 30 prasanskaran ikai sootra 6 parr haye. prachaalak sootra 33 cumm seey cumm sahayogi honah chaahiye, jabaki kuchh algorithm mein ack commutative prachaalak aur ack tatasth tatva kii bhee aavashyakta hoti haye. samanya prachaalak sootra 36, sootra 37 aur sootra 38 hain. antatah prasanskaran ikai sootra 6 upsarg yog sootra 58 formula 59 koo sangraheet kartaa haye. tathaakathit vishesh upsarg yog key mamle mein, prasanskaran ikai sootra 6 upsarg yog sootra 61 formula 59 koo sangraheet kartaa haye. kuchh algorithm koo upsarg raashi key alawa pratyek prasanskaran ikai mein samagr raashi koo sangraheet karane kii aavashyakta hoti haye.
laghu sandeshon key liye, yeh ack atee-ghana topology key saath praapt kiya jaa sakata haye yadi sootra _ 3 dou kii shakti haye. lambe sandeshon key liye, hypercube (,) topology upayukt naheen haye, kyonki sabhi prasanskaran ikaaiyaan harr charan mein sakriya hain aur isaliye pipelining kaa upayog naheen kiya jaa sakata haye. ack dwiaadhaari vriksh topology manmaane sootra _ 3 aur lambe sandeshon () key liye behtar haye.
dwiaadhaari vriksh parr upsarg-raashi koo oopar kii or aur neeche kii or charan key saath lagu kiya jaa sakata haye. oopar kii or charan mein kamee kii jaati haye, jabaki neeche kii or charan prasaran key samaan hotaa haye, jahaan upsarg raashi kii ganana baaen aur daaen bachchon koo alag-alag detta bhejkar kii jaati haye. iss drishtikon key saath pipelining sambhav haye, kyonki sanchaalan kamee () aur prasaran () key barabar hain.
dwiaadhaari vriksh parr pipelined upsarg yog sootra _ 28 mein sambhav haye.
baadha.
saamoohik sanchaalan key roop mein baadha ack baadha kii avadharana kaa saamaanyikaran haye, jiska upayog vitarit computing mein kiya jaa sakata haye. jaba ack prasanskaran ikai baadha koo coll karati haye, tou yeh taba taka prateeksha karati haye jaba taka kii anya sabhi prasanskaran ikaaiyon koo bhee baadha naheen kahaa jaataa haye. iss prakaar baadha kaa upayog vitarit computing mein vaishvik samanvaya praapt karane key liye kiya jaataa haye.
baadha koo lagu karane kaa ack tarika haye ack khaali/nakali operand key saath aul-reduce () coll karna. humm jaanate hain kii sabhi-cumm kaa runtime sootra _ 66 haye. ack nakali operand kaa upayog karane seey aakar sootra _ 4 koo ack sthir kaarak mein cumm curr diyaa jaataa haye aur sootra _ 68 key runtime kii or leey jaataa haye.
ikattha hoe jaaen.
sangrah sanchaar pattern kaa upayog sabhi prasanskaran ikaaiyon seey detta koo ack ekal prasanskaran ikai parr sangraheet karane key liye kiya jaataa haye. diye gaye sootra _ 3 prasanskaran ikaaiyon, sandesh sootra _ 30 prasanskaran ikai sootra _ 6 parr. ack nishchit prasanskaran ikai sootra _ 72 key liye, humm sandesh sootra _ 73 koo sootra _ 72 parr sangraheet karna chaahte hain. ikattha karane koo ack cumm operation () key roop mein socha jaa sakata haye joe sanyojan operator kaa upayog kartaa haye. yeh iss tathya key kaaran kaam kartaa haye kii sanyojan sahayogi haye. usee dwipad vriksh kamee algorithm kaa upayog karke hamein sootra _ 75 kaa ack runtime milata haye. humm dekhate hain kii asymptotic runtime cumm sootra _ 28 key asymptotic runtime key samaan haye, lekin sootra _ 77 shabd mein ack kaarak p key judane key saath. yeh atirikt kaarak pratyek charan mein sandesh key aakar mein vriddhi key kaaran haye kyonki sandesh sanyojit hoe jaate hain. isaki tulanaa cumm karane key liye karein jahan sootra _ 37 jaise prachaalak key liye sandesh kaa aakar sthir haye.
sabhi ikattha.
sabhi prasanskaran ikaaiyon seey detta ekatra karane aur sabhi prasanskaran ikaaiyon parr ekatra kiye gaye detta koo sangraheet karane key liye sabhi-sangrah sanchaar pattern kaa upayog kiya jaataa haye. sootra _ 3 prasanskaran ikaaiyon sootra _ 6, sandesh sootra _ 30 koo diye gaye sootra _ 6 parr shuru mein sangraheet kiya gayaa haye, humm pratyek sootra _ 72 parr sandesh sootra _ 73 koo sangraheet karna chaahte hain.
isake baare mein kaee tarikon seey socha jaa sakata haye. pahala ack poorna-cumm sanchaalan () key roop mein haye jisamen sanchaalak key roop mein sanyojan hotaa haye, usee tarah seey jise ikattha karke cumm kiya jaa sakata haye. doosara ack sangrah-sanchaalan key roop mein haye jisake baad aakar sootra _ 85 key nae sandesh kaa prasaran hotaa haye. isake saath humm dekhate hain kii sootra _ 75 mein sabhi ekatra karna sambhav haye.
failaaen.
scatter sanchaar pattern kaa upayog ack prasanskaran ikai seey sabhi prasanskaran ikaaiyon mein detta vitarit karane key liye kiya jaataa haye. yeh prasaran seey alag haye, kyonki yeh sabhi prasanskaran ikaaiyon koo ack hii sandesh naheen bhejata haye. isake bajaay yeh sandesh koo vibhajit kartaa haye aur iska ack hissa pratyek prasanskaran ikai koo vitarit kartaa haye.
sootra _ 3 prasanskaran ikaaiyon kaa sootra _ 6 diyaa gayaa haye, ack nishchit prasanskaran ikai sootra _ 72 joe sandesh sootra _ 90 rakhta haye. humm sandesh sootra _ 30 koo sootra _ 6 parr leey jaanaa chaahte hain. vahee karyanvayan chintaaen joe ikattha karane () key liye lagu hoti hain. yeh sootra _ 75 mein ack ishtatam runtime kii or leey jaataa haye.
sabhi seey sabhi.
sabhi seey sabhi sabse samanya sanchaar pattern haye. sootra _ 94 key liye, sandesh sootra _ 95 vaha sandesh haye joe shuru mein node sootra _ 96 parr sangraheet kiya jaataa haye aur ise node sootra _ 97 parr vitarit kiya jaataa haye. humm una sabhi sanchaar adim koo vyakt curr sakate hain joe sabhi-seey-sabhi key madhyam seey prachaalak kaa upayog naheen karate hain. udaaharan key liye, node sootra 99 seey sandesh sootra 12 key prasaran kaa anukaran sootra 101 key liye sootra 100 nirdhaarit karke aur sootra 103 key liye sootra 102 khaali karke kiya jaataa haye.
yeh maanate hue kii hamaare paas poori tarah seey judaa huaa network haye, sabhi key liye sabse achchha sambhav runtime sootra _ 104 mein haye. yeh seedhe sandesh adaan-pradaan key sootra _ 3 daur key madhyam seey praapt kiya jaataa haye. 2 key sootra _ 3 kii shakti key liye, sanchaar goal sootra _ 26 mein, node sootra _ 6 node sootra _ 109 key saath sandeshon kaa adaan-pradaan kartaa haye.
yadi sandesh kaa aakar chhota haye aur vilambata sanchaar parr haavi haye, tou samay sootra _ 110 mein sandeshon koo vitarit karane key liye ack hypercube algorithm kaa upayog kiya jaa sakata haye.
runtime avalokan.
yeh talika sabse prasiddh asymptotic runtime parr ack avalokan detee haye, yeh maanate hue kii hamaare paas network topology kaa swatantra vikalp haye.
humm ishtatam runtime key liye chaahte hain kii dwiaadhaari vriksh, dwipad vriksh, atee-ghana jaise udaaharan hain.
vyavhaar mein, hamein upalabdh bhautik topology key saath samaayojan karna hoga, jaise.jee. dragonfly, fait tree, grid network (anya topology kaa bhee sandarbh).
network topology key tahat adhik jaankaari.
pratyek operation key liye, ishtatam algorithm input aakar sootra _ 4 parr nirbhar curr sakata haye. udaaharan key liye, chhote sandeshon key liye prasaran koo ack dwipad vriksh kaa upayog karke sabse achchha lagu kiya jaataa haye jabaki lambe sandeshon key liye ack santulit dwiaadhaari vriksh parr ack pipeline sanchaar ishtatam hotaa haye.
talika mein bataai gaee jatilataaen vilambata sootra _ 1 aur prati shabd sanchaar laagat sootra _ 2 parr nirbhar karati hain, isake alawa prasanskaran ikaaiyon kii sankhya sootra _ 3 aur prati node sootra _ 4 key input sandesh aakar key alawa. "#sanders" aur "#receivers" collum kramshah preshakon aur receivers kii sankhya kaa pratinidhitva karate hain joe operation mein shamil hain. #sandesh" collum mein input sandeshon kii sankhya aur "gananaaen" soochibaddh hain?"collum ingit kartaa haye kii kyaa sandeshon parr koee ganana kii jaati haye yaa sandeshon koo binaa prasanskaran key vitarit kiya jaataa haye. "jatilata" topology key swatantra vikalp key tahat ack ishtatam karyanvayan kii asymptotic runtime jatilata detaa haye.

