Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Марзулло алгоритмі, Кит Марзуллоның 1984 жылы докторлық диссертациясы үшін ойлап тапқан алгоритмі, шулы уақыт көздерінен дәл уақытты анықтау үшін қажетті көздерді таңдауға қолданылатын келісім алгоритмі болып табылады. Оның жетілдірілген нұсқасы, "қиылыс алгоритмі" деп қайта аталған, қазіргі заманғы Желілік уақыт протоколының құрамына кіреді. Марзулло алгоритмі сонымен қатар бірнеше берік жиынтықтарды бағалау әдістеріне қажетті n қораптың (немесе жалпы алғанда Rn-нің n ішкі жиынының) бос қиылысын есептеу үшін де қолданылады.
Marzullo's algorithm, invented by Keith Marzullo for his Ph. D. dissertation in 1984, is an agreement algorithm used to select sources for estimating accurate time from a number of noisy time sources. A refined version of it, renamed the "intersection algorithm", forms part of the modern Network Time Protocol. Marzullo's algorithm is also used to compute the relaxed intersection of n boxes (or more generally n subsets of Rn), as required by several robust set estimation methods.
Мақсаты
Марзулло алгоритмі сенімділік интервалы бар бағалаулар жиынтығынан оңтайлы мәнді шығару үшін уақыт жағынан тиімді, онда нақты мән кейбір көздер үшін сенімділік интервалынан тыс болуы мүмкін. Бұл жағдайда ең жақсы бағалау ең көп сандағы көздерге сәйкес келетін ең кіші интервал деп есептеледі. Егер бізде 10 ± 2, 12 ± 1 және 11 ± 1 бағалаулары болса, онда бұл интервалдар [8,12], [11,13] және [10,12] болады, олар [11,12] немесе 11,5 ± 0,5 түрінде үш мәнге де сәйкес келеді. Егер диапазон [8,12], [11,13] және [14,15] болса, онда барлық осы мәндерге сәйкес келетін интервал жоқ, бірақ [11,12] ең көп сандағы көздерге – атап айтқанда, екеуіне – сәйкес келеді. Соңында, егер диапазон [8,9], [8,12] және [10,12] болса, онда [8,9] және [10,12] интервалдары ең көп сандағы көздерге сәйкес келеді. Бұл процедура интервалды анықтайды. Егер қажетті нәтиже осы интервалдан ең жақсы мән болса, онда қарапайым тәсіл интервалдың ортасын мән ретінде алу болады, бұл бастапқы Марзулло алгоритмінде көрсетілген. Көбірек зерделі тәсіл бұл дереккөздердің сенімділік интервалдарынан пайдалы ақпаратты жоғалтуы мүмкін екенін, ал дереккөздердің ықтималдық моделі орталықтан өзге мәнді де қайтара алатынын ескереді. Есептелген мәнді "оптималды" емес, "оптимистік" деп сипаттаған дұрыс. Мысалы, үш интервалды [10,12], [11, 13] және [11.99,13] қарастырайық. Төменде сипатталған алгоритм [11.99, 12] немесе 11.995 ± 0.005 есептейді, бұл өте дәл мән. Егер біз бағалаулардың бірі дұрыс емес болуы мүмкін деп күдіктенсек, онда кем дегенде екі бағалау дұрыс болуы керек. Осы шарт бойынша, ең жақсы бағалау [11,13] болады, себебі бұл әрқашан кем дегенде екі бағалауды қиып өтетін ең үлкен интервал. Төменде сипатталған алгоритм қате бағалаулардың максималды санымен оңай параметрленеді.
Marzullo's algorithm is efficient in terms of time for producing an optimal value from a set of estimates with confidence intervals where the actual value may be outside the confidence interval for some sources. In this case the best estimate is taken to be the smallest interval consistent with the largest number of sources. If we have the estimates 10 ± 2, 12 ± 1 and 11 ± 1 then these intervals are [8,12], [11,13] and [10,12] which intersect to form [11,12] or 11.5 ± 0.5 as consistent with all three values. If instead the ranges are [8,12], [11,13] and [14,15] then there is no interval consistent with all these values but [11,12] is consistent with the largest number of sources — namely, two of them. Finally, if the ranges are [8,9], [8,12] and [10,12] then both the intervals [8,9] and [10,12] are consistent with the largest number of sources. This procedure determines an interval. If the desired result is a best value from that interval then a naive approach would be to take the center of the interval as the value, which is what was specified in the original Marzullo algorithm. A more sophisticated approach would recognize that this could be throwing away useful information from the confidence intervals of the sources and that a probabilistic model of the sources could return a value other than the center. Note that the computed value is probably better described as "optimistic" rather than "optimal". For example, consider three intervals [10,12], [11, 13] and [11.99,13]. The algorithm described below computes [11.99, 12] or 11.995 ± 0.005 which is a very precise value. If we suspect that one of the estimates might be incorrect, then at least two of the estimates must be correct. Under this condition, the best estimate is [11,13] since this is the largest interval that always intersects at least two estimates. The algorithm described below is easily parameterized with the maximum number of incorrect estimates.
Тиімділік
Марзулло алгоритмі кеңістік және уақыт бойынша тиімді. Асимптотикалық кеңістік қолданысы O(n) құрайды, мұнда n – дереккөздер саны. Асимптотикалық уақыт талабын қарастырғанда, алгоритм кесте құрудан, оны сұрыптаудан және іздеуден тұрады деп есептеуге болады. Сұрыптау O(n log n) уақытында орындалуы мүмкін, бұл кесте құру және іздеу кезеңдерінен басым, олар сызықтық уақытта жүзеге асырылуы мүмкін. Сондықтан Марзулло алгоритмінің уақыт тиімділігі O(n log n) шамасына тең. Кесте құрылып, сұрыпталғаннан кейін, жаңа ақпарат түскен кезде бір дереккөз үшін интервалды сызықтық уақытта жаңартуға болады. Демек, бір дереккөздің деректерін жаңарту және ең жақсы интервалды табу O(n) уақытында орындалуы мүмкін.
Marzullo's algorithm is efficient in both space and time. The asymptotic space usage is O(n), where n is the number of sources. In considering the asymptotic time requirement the algorithm can be considered to consist of building the table, sorting it and searching it. Sorting can be done in O(n log n) time, and this dominates the building and searching phases which can be performed in linear time. Therefore, the time efficiency of Marzullo's algorithm is O(n log n). Once the table has been built and sorted it is possible to update the interval for one source (when new information is received) in linear time. Therefore, updating data for one source and finding the best interval can be done in O(n) time.