Примерно 40 лет тому назад М. Гарднер придумал такую задачу: <В некотором царстве, в некотором государстве пришло время принцессе выбирать себе жениха. В назначенный день явились 1000 царевичей. Их построили в очередь в случайном порядке и стали по одному приглашать к принцессе. Про любых двух претендентов принцесса, познакомившись с ними, может сказать, какой из них лучше. Познакомившись с претендентом, принцесса может либо принять предложение (и тогда выбор сделан навсегда), либо отвергнуть его (и тогда претендент потерян: царевичи гордые и не возвращаются). Какой стратегии должна придерживаться принцесса, чтобы с наибольшей вероятностью выбрать лучшего?>.
В 1965 году формулировку этой задачи и её решение рассказал на своём семинаре Е. Б. Дынкин. Но его метод был необобщаем на другие варианты задачи: например, когда целью является выбор не наилучшего, а одного из трёх лучших. В таком виде задача была решена автором при помощи метода, который легко переносится и на ряд близких задач. Так из полушуточной задачи вырос новый раздел математики — т е о р и я о п т и м а л ьн о й о с т а н о в к и с л у ч а й н ы х п р о ц е с с о в.
Текст брошюры представляет собой обработку записи лекции, прочитанной автором 30 ноября 2002 года на Малом мехмате МГУ для школьников 9—11 классов (запись Ю. Л. Притыкина). Брошюра рассчитана на широкий круг читателей: школьников, студентов, учителей.
Хотите верьте, хотите нет | но либо в шахматах у белых есть гарантированный выигрыш, либо у чёрных есть гарантированная ничья.
В этой брошюре рассказывается, что это значит, почему это верно (хотя и бесполезно в шахматной практике!), какие ещё бывают подобные игры и как их можно математически анализировать.
Есть в математике темы, пользующиеся достаточно известностью и в то же время признаваемые традицией слишком сложными (или маловажными) для включения в обязательное обучение: обычай относит их к занятиям факультативным, дополнительным, специальным и т. п. В перечне таких тем есть несколько, остающихся сейчас там исключительно в силу инерции. Одной из них является теорема Гёделя.
Несмотря на то, что очень многие математики (и нематематики) слышали о ней, мало кто из них может объяснить, в чем состоит утверждение теоремы Гёделя и тем более как она доказывается. Вместе с тем результат столь важен, а причины, вызывающие неустранимую неполноту (т. е. невозможность добиться того, чтобы каждое истинное утверждение было доказуемо), столь просты, что теорема Гёделя могла бы излагаться на самых младших курсах.
Более того, для понимания доказательства необходимо лишь знакомство с простейшей терминологией теории множеств (словами «множество», «функция», «область определения» и тому подобными) и некоторая привычка к восприятию математических рассуждений, так что оно вполне доступно подготовленному школьнику.
Машина Поста — это хотя и абстрактная (т. е. не существующая в арсенале действующей техники), но зато очень простая вычислительная машина. Она способна выполнять лишь самые элементарные действия, и потому ее описание и составление простейших программ может быть доступно ученикам начальной школы.
Тем не менее на машине Поста можно запрограммировать — в известном смысле — любые алгоритмы. Изучение машины Поста можно рассматривать как начальный этап обучения теории алгоритмов и программированию.
1-е изд. — 1979 г.
Для широкого круга читателей.
Книга Б. А. Трахтенброта рассматривает в популярной форме основные вопросы теории алгоритмов и связь этой теории с современной машинной математикой.
Автор подробно рассказывает об истории развития понятия алгоритм, о принципе работы современных быстродействующих вычислительных машин, об основах программирования, о схеме машины Тьюринга, об алгоритмически неразрешимых проблемах.
Книга рассчитана на школьников старших классов, преподавателей, инженерно-технических работников и всех лиц, интересующихся перспективами применения новой вычислительной техники.
В брошюре рассматриваются идеи и конструкции, лежащие в основе «математики текстов»; среди примеров её результатов — несчётность множества последовательностей из нулей и единиц, невозможность создать программу, распознающую самоприменимость программ. Обсуждается важное понятие сложности текста по Колмогорову, позволяющее отличать случайные тексты от неслучайных.
Текст брошюры представляет собой обработанную запись лекции, прочитанной автором 5 декабря 1999 года для участников III Международного математического турнира старшеклассников «Кубок памяти А. Н. Колмогорова» — школьников 8—11 классов. (Запись Е. Н. Осьмовой, обработка Р. М. Кузнеца.)
Для широкого круга читателей, интересующихся математикой: школьников старших классов, студентов младших курсов, учителей…
В книге описан ряд классических идей решения олимпиадных задач, которые для большинства школьников являются нестандартными. Каждая идея снабжена комментарием, примерами решения задач и задачами для самостоятельного решения. Приведены подборки задач олимпиадного и исследовательского типов (всего 200 задач), которые сгруппированы по классам.
Сборник адресован старшеклассникам, учителям, руководителям кружков и всем любителям математики.
Предыдущее издание книги вышло в 2004 г.
Эта книга написана по материалам одной из секций школьного математического кружка при Московском государственном университете им. М. В. Ломоносова, работавшей в 1945/46 и 1946/47 учебных годах. Один из авторов был руководителем этой секции, другой — её участником. Секция называлась секцией общего типа.
На её занятиях рассматривались вопросы из различных областей математики. Основной целью было не столько сообщить участникам новые сведения, сколько научить их активному, творческому отношению к математике.
Наиболее удачные темы складывались в процессе самой работы секции. В предлагаемую книгу вошли — в значительно переработанном и расширенном виде — три такие темы: задачи о многоцветной раскраске карт, задачи из теории чисел, решаемые с помощью арифметики вычетов, и задачи из теории вероятностей, связанные с так называемыми случайными блужданиями.
Цель книги – способствовать формированию у школьников умений и навыков, необходимых для взаимодействия с ЭВМ на языках высокого уровня. Даются конструкции таких языков и основные приемы прикладного программирования.
Учащиеся знакомятся с современным уровнем и перспективами развития информатики и вычислительной техники.
Текст книги в основном ориентирован на школьников 5–8 классов.
Комбинаторика — важный раздел математики, знание которого необходимо представителям самых разных специальностей. С комбинаторными задачами приходится иметь дело физикам, химикам, биологам, диагностам, специалистам по кодам и др.
Комбинаторные методы лежат в основе решения многих задач теории вероятностей и её приложений. В книге в популярной форме рассказывается об интересных комбинаторных задачах и методах их решения.
