شماره ركورد
25727
شماره راهنما
MAT2 726
عنوان
تحليل و بهبود الگوريتم هاي شناسايي زنبورها
مقطع تحصيلي
كارشناسي ارشد
رشته تحصيلي
رياضي كاربردي- رمز و كد
دانشكده
رياضي و آمار
تاريخ دفاع
1404/11/19
صفحه شمار
155 ص .
استاد راهنما
رضا سبحاني
كليدواژه فارسي
مسئله شناسايي زنبور , كدگشايي مشترك , الگوريتم هاي شناسايي , تطابق كامل , كانال متقارن دودويي , كانال پاك شدگي دودويي
چكيده فارسي
در اين پايان نامه، به تحليل و بهبود الگوريتم هاي شناسايي زنبورهاي باركددار بر اساس دادەهاي دريافت نويزي و نامرتب پرداخته شده است.مسأله اين پايان نامه، يافتن تطابق بهينه ميان مجموعه اي از كدواژەها ي دودويي وخروجي هاي دريافتي از كانال هاي نويزي نظير كانال متقارن دودويي و پاك شدگي دودويي است؛ به گونه اي كه احتمال شناسايي صحيح هر زنبور حداكثر شود. براي اين منظور، مسأله شناسايي بەصورت يك مسئله تطابق كامل در گراف هاي دو بخشي مدل سازي شد و با هدف كمينه سازي وزن كل تطابق، الگوريتم هاي كارآمدي براي هر نوع كانال توسعه يافت.
در حالت كانال پاك شدگي دودويي، الگوريتمJEDI معرفي و پيادەسازي گرديد. اين الگوريتم با استفاده ازروش هايي همچون حذف تدريجي و الگوريتم هاپكروف كارپ، تطابق كامل را با پيچيدگي زمان (2O(Mمحاسبه م كند. همچنين، با بهرەگيري از ساختار كدهاي ريد⁃مولر، نشان داده شد كه پيچيدگ زماني به طورچشم گيري كاهش يافته و در برخي حالات، به زمان تقريباﹰ خطي نزدي م شود.
براي كانال متقارن دودويي، الگوريتمJMDI مبتن بر كمينه سازي مجموع فواصل همينگ ارائه شد كه با پيادەسازي الگوريتم مجارستاني ، شناسايي بهينه با پيچيدگي زمان (3O(M انجام مي شود. علاوەبراين، بابه كارگيري روش هاي تقريبي و ليست ديكدينگ، سرعت اجرا بهبود يافت و دقت شناسايي حفظ شد.
نتايج حاصل بيانگر آن است كه روش هاي ارائه شده، بەويژه در تركيب با كدهاي ريد⁃مولر، ضمن كاهش قابل توجه نرخ خطا، موجب بهينه سازي هزينه محاسبات مي شوند. اين دستاوردها زمينه را براي توسعه سامانه هاي شناسايي خودكار زنبورها و كاربردهاي مشابه فراهم مي سازد.
علاوه بر بررسي مفاهيم پايه، بخش عمدەاي از تحليل ها، توسعەهاي الگوريتمي و ارزيابي هاي ارائه شده در اين پژوهش، حاصل تلاش هاي مستقل نگارنده است كه به منظور بهبود و بسط روش هاي پيشين صورت گرفته است.
كليدواژه لاتين
Bee recognition problem , joint decoding , recognition algorithms , perfect matching , binary symmetric channel , binary erasure channel
عنوان لاتين
Analysis and improvement of Bee identification algorithms
گروه آموزشي
رياضي كاربردي و علوم كامپيوتر
چكيده لاتين
Inthisthesis,theanalysisandimprovementofbeerecognitionalgorithmsbased onnoisyandunorderedreceiveddataareaddressed. Theproblemofthisthesisistofindtheoptimalmatchbetweenasetofbinarycodesandtheoutputs receivedfromnoisychannels,suchasthebinarysymmetricchannelandbinary erasurechannel,inawaythatmaximizestheprobabilityofcorrectrecognitionof eachbee.Tothisend,therecognitionproblemismodeledasaperfectmatching probleminbipartitegraphs,andefficientalgorithmsaredevelopedforeachtype ofchanneltominimizethetotalmatchingcost.
Inthecaseofthebinaryerasurechannel,theJEDIalgorithmisintroducedand implemented.Thisalgorithmcomputesperfectmatchingwithatimecomplexity of O(M2) usingtechniquessuchasprogressiveeliminationandtheHopcroft-Karp algorithm.Additionally,byutilizingReed-Mullercodestructures,itisshownthat thetimecomplexitysignificantlyreduces,approachingnearlylineartimeinsome cases.
Forthebinarysymmetricchannel,theJMDIalgorithmbasedonminimizingthe sumofHammingdistancesispresented,whichperformsoptimalrecognitionwith atimecomplexityof O(M3) byimplementingtheHungarianalgorithm. Moreover,byemployingapproximatemethodsandlistdecoding,theexecutionspeed isimprovedwhilemaintainingrecognitionaccuracy.
Theresultsindicatethattheproposedmethods,particularlywhencombined withReed-Mullercodes,significantlyreducetheerrorrateandoptimizecomputationalcost.Theseachievementspavethewayforthedevelopmentofautomatic beerecognitionsystemsandsimilarapplications.
تعداد فصل ها
7
فهرست مطالب pdf
157644
نويسنده