Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Математикалық дәлелдеудің конструктивті емес әдісі
Nonconstructive method for mathematical proofs
Математикада ықтималдық әдіс – негізінен комбинаторикада қолданылатын және Пауль Эрдос бастамасымен математикалық объектінің белгіленген түрінің бар екенін дәлелдеуге арналған конструктивті емес әдіс. Ол белгілі бір сыныптан кездейсоқ нысандарды таңдағанда, нәтиже белгіленген түрге ие болу ықтималдығы қатаң түрде нөлден жоғары екенін көрсету арқылы жұмыс істейді. Дәлелдеу ықтималдықты пайдаланса да, соңғы қорытынды нақты анықталады, ешқандай қателікке жол жоқ. Бұл әдіс қазір математиканың басқа салаларына, мысалы, сандар теориясына, сызықтық алгебраға және нақты талдауға, сондай-ақ информатикаға (мысалы, кездейсоқ дөңгелектеу) және ақпарат теориясына қолданылып келеді.
In mathematics, the probabilistic method is a nonconstructive method, primarily used in combinatorics and pioneered by Paul Erdős, for proving the existence of a prescribed kind of mathematical object. It works by showing that if one randomly chooses objects from a specified class, the probability that the result is of the prescribed kind is strictly greater than zero. Although the proof uses probability, the final conclusion is determined for certain, without any possible error. This method has now been applied to other areas of mathematics such as number theory, linear algebra, and real analysis, as well as in computer science (e. g. randomized rounding), and information theory.
Кіріспе
Егер нысандар жиынтығындағы әрбір нысан белгілі бір қасиетке ие болмаса, онда жиынтықтан кездейсоқ таңдалған нысанның сол қасиетке ие болу ықтималдығы нөлге тең. Сол сияқты, ықтималдықтың (қатаң түрде) 1-ден кем екенін көрсету, берілген қасиеттерге сәйкес келмейтін нысанның бар екенін дәлелдеуге қолданылуы мүмкін. Ықтималдық әдісін қолданудың тағы бір жолы – кейбір кездейсоқ шаманың күтілетін мәнін есептеу. Егер кездейсоқ шаманың күтілетін мәннен төмен мәнге ие бола алатыны көрсетілсе, онда ол кездейсоқ шаманың күтілетін мәннен жоғары мәнге ие болатынын дәлелдейді. Басқаша айтқанда, ықтималдық әдісі үлгі кеңістігінде қажетті элементтің күтілетін мәнге тең немесе одан үлкен мәнімен бар екендігін кепілдендіру үшін де қолданылуы мүмкін, себебі мұндай элементтің болмауы үлгі кеңістігіндегі барлық элементтердің күтілетін мәннен кіші екенін білдіреді, бұл қайшылыққа әкеледі. Ықтималдық әдісінде қолданылатын негізгі құралдарға Марков теңсіздігі, Чернофф шектері және Ловас жергілікті леммасы жатады.
If every object in a collection of objects fails to have a certain property, then the probability that a random object chosen from the collection has that property is zero. Similarly, showing that the probability is (strictly) less than 1 can be used to prove the existence of an object that does not satisfy the prescribed properties. Another way to use the probabilistic method is by calculating the expected value of some random variable. If it can be shown that the random variable can take on a value less than the expected value, this proves that the random variable can also take on some value greater than the expected value. Alternatively, the probabilistic method can also be used to guarantee the existence of a desired element in a sample space with a value that is greater than or equal to the calculated expected value, since the non existence of such element would imply every element in the sample space is less than the expected value, a contradiction. Common tools used in the probabilistic method include Markov's inequality, the Chernoff bound, and the Lovász local lemma.
Ердосқа байланысты екі мысал
Оның алдындағылар ықтималдық әдіс арқылы теоремаларды дәлелдегенімен (мысалы, Сзеленің 1943 жылғы нәтижесінде үлкен саны бар турнирлердің болуы көрсетілген гамильтондық циклдар), осы әдісті қолдана отырып жасалған ең танымал дәлелдемелердің көп бөлігі Ердосқа тиесілі. Төмендегі бірінші мысал 1947 жылғы осындай нәтижелердің бірін сипаттайды, ол Рэмси саны R(r, r) үшін төменгі шек дәлелдейді.
Although others before him proved theorems via the probabilistic method (for example, Szele's 1943 result that there exist tournaments containing a large number of Hamiltonian cycles), many of the most well known proofs using this method are due to Erdős. The first example below describes one such result from 1947 that gives a proof of a lower bound for the Ramsey number R(r, r).