Математика

Введение Одной из важнейших задач в теории чисел является проверка числа на простоту. То есть по заданному числу эффективно определить является оно простым или составным. Алгоритмы, решающие эту задачу (их также называют тестами простоты), известны с древних времён, пример – решето Эратосфена. Но алгоритма, имеющего полиномиальную сложность, долгое время известно не было. В 2002 году индийскими математиками Агравалом, Кайялом и Саксеной в работе “PRIMES is in P” был впервые предложен алгоритм проверки простоты чисел (известный как тест AKS), который одновременно является полиномиальным, универсальным, детерминированным и безусловным....

Хотя люди давно соревнуются в играх, сила игроков долгое время оценивалась субъективно по выступлениям на турнирах и качеству сыгранных партий. Первые числовые рейтинговые системы стали использоваться лишь в 40-х годах 20 века. Локомотивом этого направления были, конечно, шахматы. Рейтинг Эло Шахматная федерация США применяла рейтинговые системы для оценки силы шахматистов с 1950-х годов. И хотя полученные рейтинги, по общему мнению, соответствовали соотношению силы игроков, они были несовершенны и иногда приводили к неожиданным результатам....