Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Математикалық функцияларды сақтау тәртібі
Order preserving mathematical function
Математикада монотонды функция (немесе монотонды функция) – берілген ретті сақтайтын немесе өзгертетін реттелген жиынтар арасындағы функция. Бұл ұғым алғаш рет математикалық анализде пайда болды, кейіннен тәртіп теориясының көбірек абстрактілі жағдайына жалпыланды.
In mathematics, a monotonic function (or monotone function) is a function between ordered sets that preserves or reverses the given order. This concept first arose in calculus, and was later generalized to the more abstract setting of order theory.
Есептеу және талдау
Калькульде нақты сандардың кіші жиынында анықталған және нақты мәндерге ие функция, егер ол толығымен кемімейтін немесе толығымен өспейтін болса, монотонды деп аталады. Рет белгісін кері бұру арқылы, қатаң түрде кемитін (сондай-ақ кемитін) деп аталатын сәйкес ұғымды табуға болады. Осы контексте, "монотонды түрлендіру" термині оң монотонды түрлендіруді білдіреді және сандардың ретін өзгертетін "теріс монотонды түрлендіруден" ажырату үшін қолданылады.
In calculus, a function defined on a subset of the real numbers with real values is called monotonic if and only if it is either entirely non increasing, or entirely non decreasing. Again, by inverting the order symbol, one finds a corresponding concept called strictly decreasing (also decreasing). In this context, the term "monotonic transformation" refers to a positive monotonic transformation and is intended to distinguish it from a "negative monotonic transformation," which reverses the order of the numbers.
Іздеу алгоритмдері аясында
Іздеу алгоритмдерінің аясында монотондық (немесе консистенттік) – эвристикалық функцияларға қолданылатын шарт. Эвристика монотонды болып есептеледі, егер кез келген n түйіні мен n әрекеті a арқылы тудырылған n' мұрагері үшін, n-ден мақсатқа жетудің бағаланған құны, n'-ге жету құнына және n'-ден мақсатқа жетудің бағаланған құнына қосылғаннан артық болмаса.
In the context of search algorithms monotonicity (also called consistency) is a condition applied to heuristic functions. A heuristic is monotonic if, for every node n and every successor n' of n generated by any action a, the estimated cost of reaching the goal from n is no greater than the step cost of getting to n' plus the estimated cost of reaching the goal from n',
Бұл үшбұрыш теңсіздігінің бір түрі, мұнда n, n' және мақсат Gn түйіні n-ге ең жақын орналасқан. Барлық монотонды эвристикалар қабылданатындықтан, монотондық қабылданудан қатаң талап болып табылады. Мысалы, A* сияқты кейбір эвристикалық алгоритмдер, егер олар қолданатын эвристика монотонды болса, оптималды екенін дәлелдеуге болады.
This is a form of triangle inequality, with n, n', and the goal Gn closest to n. Because every monotonic heuristic is also admissible, monotonicity is a stricter requirement than admissibility. Some heuristic algorithms such as A* can be proven optimal provided that the heuristic they use is monotonic.
Буль функцияларында
Буль алгебрасында монотонды функция — {0,1} жиынындағы барлық ai және bi үшін, егер a1 ≤ b1, a2 ≤ b2, ..., an ≤ bn (яғни, {0, 1}^n картезиан көбейтіндісі координата бойынша реттелген болса), онда f(a1, ..., an) ≤ f(b1, ..., bn) болады. Басқаша айтқанда, Буль функциясы монотонды болады, егер кіріс мәндерінің кез келген комбинациясы үшін, кіріс деректерінің біреуін жалғаннан шынға өзгерту шығыстың жалғаннан шынға өзгеруіне ғана себеп болса, шыннан жалғанға емес. Графикалық тұрғыдан алғанда, бұл n-арғы Буль функциясының шындық мәндерімен белгіленген n-куб түріндегі бейнесінде шындықтан жалғанға қарай бағытталған тік қабырға болмаса, функция монотонды болады. (Бұл белгіленген Хассе диаграммасы функцияның белгіленген Венн диаграммасының дуалы болып табылады, және n ≤ 3 үшін көбірек қолданылады.) Монотонды Буль функциялары — операторларды «және» және «немесе» (әсіресе «емес» операторына рұқсат етілмейді) қолданып, кіріс мәндерін біріктіретін өрнектер арқылы анықталуы мүмкін функциялар. Мысалы, «a, b, c-ның кемінде екеуі орындалады» — a, b, c-ның монотонды функциясы, себебі оны мысалы, ((a және b) немесе (a және c) немесе (b және c)) түрінде жазуға болады. n айнымалыдағы мұндай функциялардың саны n-нің Дедекинд саны деп аталады.
In Boolean algebra, a monotonic function is one such that for all ai and bi in {0,1}, if a1 ≤ b1, a2 ≤ b2, , an ≤ bn (i. e. the Cartesian product {0, 1}^(n) is ordered coordinatewise), then f(a1, , an) ≤ f(b1, , bn). In other words, a Boolean function is monotonic if, for every combination of inputs, switching one of the inputs from false to true can only cause the output to switch from false to true and not from true to false. Graphically, this means that an n ary Boolean function is monotonic when its representation as an n cube labelled with truth values has no upward edge from true to false. (This labelled Hasse diagram is the dual of the function's labelled Venn diagram, which is the more common representation for n ≤ 3.) The monotonic Boolean functions are precisely those that can be defined by an expression combining the inputs (which may appear more than once) using only the operators and and or (in particular not is forbidden). For instance "at least two of a, b, c hold" is a monotonic function of a, b, c, since it can be written for instance as ((a and b) or (a and c) or (b and c)). The number of such functions on n variables is known as the Dedekind number of n.
SAT мәселесін шешу, әдетте NP-қиын міндеттің бірі, барлық қатысты функциялар мен предикаттар монотонды және Бульдік болған жағдайда тиімді жүзеге асырылуы мүмкін.
SAT solving, generally an NP hard task, can be achieved efficiently when all involved functions and predicates are monotonic and boolean.