Книги: [Классика] [Базы данных] [Internet/WWW] [Сети] [Программирование] [UNIX] [Windows] [Безопасность] [Графика] [Software Engineering] [ERP-системы] [Hardware]

Конкретная математика. Основание информатики Р. Грэхем, Д. Кнут, О. Паташник Издано: 1998, М., "Мир" Для широкого круга ISBN: 5-03-001793-3 Твердый переплет, 703 стр. Формат: 70x100/16 Начало Полное содержание Об авторах

Предисловие

В ОСНОВУ ЭТОЙ КНИГИ положен одноименный курс лекций, который ежегодно читается в Станфордском университете, начиная с 1970 года. Каждый год его слушателями становятся около пятидесяти человек - студентов предпоследнего и последнего курсов, но, в основном, дипломников,-а ряд наших выпускников уже начал насаждать подобные курсы и в других местах. Так что настала, видимо, пора ознакомить с материалами курса более широкую аудиторию (включая младшекурсников).

Конкретная математика зарождалась в смутное и неспокойное десятилетие. В те бурные годы казавшиеся незыблемыми ценности постоянно подвергались сомнениям: студенческие городки превращались в очаги жарких дискуссий. Оспаривались сами учебные программы, и математика не стала исключением. Как раз в то время Джон Хаммерсли написал полемическую статью "О снижении уровня математической подготовки в школах и университетах благодаря 'современной математике' и подобной ей жидкой интеллектуальной похлебке" [330]; другие обеспокоенные математики [279] даже задавались вопросом: "Можно ли спасти математику?" Когда один из авторов настоящей книги задумал серию книг под названием Искусство программирования для ЭВМ, то при написании первого тома он (Д.Э.К.) обнаружил, что в его арсенале отсутствуют важные математические инструменты: математика, которая требовалась для досконального, обоснованного истолкования компьютерных программ, совершенно отличалась от той, которую автор изучал в колледже в качестве профилирующей дисциплины. Поэтому он ввел новый курс, содержащий материал, который он, в свое время, предпочел бы прослушать сам.

С самого начала название курса - "конкретная математика" - подразумевало его противопоставление "абстрактной математике", поскольку конкретные классические результаты стремительно вымывались из современного математического образования новой волной абстрактных идей, популярно именовавшихся "новой мат'кой" Абстрактная математика-чудесный предмет, и в ней нет ничего плохого: она красива, обща и полезна. Однако ее приверженцы впали в заблуждение, что вся остальная математика занимает более низкое положение и далее не заслуживает внимания. Погоня за обобщениями оказалась столь захватывающей, что целое поколение математиков потеряло способность находить прелесть в частностях, в том числе получать удовольствие от решения численных задач или оценить по достоинству роль математических методов. Абстрактная математика стала вырождаться и терять связь с действительностью - математическое образование нуждалось в конкретном противовесе для восстановления устойчивого равновесия.

Когда Д.Э.К. приступал к чтению курса конкретной математики в Станфорде, он объяснял несколько странное название курса тем, что это попытка преподавания математики в стиле ,,хард" вместо "софт" Он объявил, что вопреки ожиданию некоторых его коллег он не собирается излагать ни теорию агрегатов Вейрштрасса, ни теорему вложения Стоуна, ни даже компактификацию Стоуна-Чеха. (Несколько студентов с факультета гражданского строительства поднялись со своих мест и потихоньку покинули аудиторию.)

Хотя конкретная математика возникла в качестве реакции на другие тенденции в математике, основные причины ее появления скорее позитивны, нежели негативны. И по мере того как этот курс продолжал занимать надлежащее место в учебном процессе, содержание предмета "отвердевало" и доказывало свою ценность в целом ряде новых приложений. Тем временем поступило другое независимое подтверждение уместности подобного наименования курса: 3. А. Мелзяк опубликовал два тома Справочника по конкретной математике [216].

На первый взгляд, содержание конкретной математики может показаться беспорядочным нагромождением уловок, но на деле - это упорядоченный набор инструментов. Более того, методы конкретной математики обладают не только внутренним единством, но и внешней привлекательностью. Когда другой автор этой книги (Р. Л. Г.) впервые прочитал данный курс в 1979г., студенты пришли в такой восторг, что договорились продлить это удовольствие на следующий год.

Но что же в действительности представляет собой КОНКРЕТНАЯ математика? Это смесь континуальной и ДИСКРЕТНОЙ математики. Еще более конкретно: это осмысленное оперирование математическими формулами с использованием определенного набора методов решения задач. После того как вы, читатель, изучите материал этой книги, все, что вам потребуется,-это ясная голова, большой лист бумаги и сносный почерк для вычисления ужасных сумм, решения запутанных рекуррентных соотношений и выявления коварных закономерностей в данных. Вы овладеете алгебраической техникой в такой степени, что зачастую вам будет проще получить точные результаты, нежели удовлетвориться приближенными ответами, которые справедливы лишь в пределе.

Исчисление сумм, рекуррентные соотношения, элементарная теория чисел, биномиальные коэффициенты, производящие функции, дискретная теория вероятностей и асимптотические методы -вот наиболее важные темы этой книги. При этом предпочтение отдается технической стороне дела, а не теоремам существования или комбинаторным рассуждениям: наша цель состоит в том, чтобы сделать каждого читателя настолько осведомленным в дискретных операциях (типа вычисления функции "наибольшего целого" или конечной суммы), насколько изучающие анализ знакомы с непрерывными операциями (типа вычисления функции "абсолютной величины" или определенного интеграла).

Заметим, что этот перечень тем совершенно отличается от того, что в наши дни обычно читается в качестве спецкурсов под названием "Дискретная математика" Поэтому наш предмет нуждается в отличительном наименовании, и название "Конкретная математика", право, не хуже любого другого.

Первоначальным руководством по конкретной математике для станфордского курса служил раздел "Математическое введение" из Искусства программирования для ЭВМ [139]. Но изложение на тех 110 страницах было слишком сжатым, поэтому еще один автор книги (О. П.) загорелся желанием составить длинный ряд дополнений. Настоящая книга выросла на их почве: она одновременно предваряет и дополняет материал "Математического введения" Некоторые вопросы повышенной сложности были опущены; в то же время в книгу включено несколько тем, которых не было раньше и без которых изложение было бы неполным.

Авторы с удовольствием объединили свои усилия для работы над этой книгой, поскольку ее предмет начал зарождаться и обретать свою собственную жизнь на наших глазах; кажется, что книга написана как бы сама собой. Более того, отчасти разнородные подходы, которые выбирал каждый из нас, оказались после стольких лет совместной работы настолько плотно подогнанными друг к другу, что мы не могли удержаться от ощущения, что эта книга - своего рода манифест единодушно выбранного нами пути занятий математикой. Поэтому мы полагаем, что наша книга прозвучит одой математической красоте и очарованию, и надеемся, что наши читатели разделят с нами хотя бы ? того удовольствия, которое мы испытали при ее написании.

Поскольку книга родилась в университетской среде, мы попытались передать дух аудитории наших дней, выбрав неформальный стиль изложения. Есть люди, полагающие, что математика-это нудное занятие, которое всегда уныло и скучно; мы же находим математику развлечением и не стыдимся признаться в этом. К чему проводить четкую грань между делом и игрой? Конкретная математика полна тому примеров: действия не всегда доставляют удовольствие, но результаты могут быть удивительно приятны. Радости и горести математической работы явно присутствуют в этой книге, поскольку являют собой части нашего бытия.

Студенты всегда умнее своих учителей, поэтому мы попросили изучавших впервые этот материал откровенно поделиться своим мнением в форме "граффити" на полях. Некоторые из их маргиналий были попросту банальны, некоторые не лишены смысла: одни предупреждали о двусмысленностях или неясностях, другие были типичными комментариями умников с последних рядов. Часть замечаний позитивна, часть-негативна, ценность остальных равна нулю. Но все они, несомненно, отражают реальные чувства читателей, что должно облегчить восприятие книги. (Вдохновляющая идея для подобных маргинальных пометок почерпнута из Справочника для поступающих в Станфорд, где официальной линии университета противопоставляются ремарки покидающих его студентов. К примеру, справочник гласит: "Есть несколько вещей, которые нельзя пропустить в таком аморфном образовании, каковым является Станфорд", а на полях помечено: "Образование, блин! Кругом одни псевдоинтеллектуалы" Справочник: "Потенциал группы совместно проживающих студентов безграничен" Граффити: "Станфордские общаги-это зверинец без смотрителя")

На полях также цитируются знаменитые математики прошлого - подлинные слова, которыми они сопровождали некоторые свои фундаментальные открытия. Отчего представляется уместным свести воедино высказывания Лейбница, Эйлера, Гаусса и других с высказываниями тех, кому предстоит продолжить их дело в будущем? Математика по-прежнему продолжает привлекать своих приверженцев-из многих нитей сплетается богатое полотно!

Книга содержит более 500 упражнений, разбитых на шесть категорий:

• разминочные упражнения, которые должен попытаться выполнить КАЖДЫЙ ЧИТАТЕЛЬ при первом чтении книги;
• обязательные упражнения, предназначенные для установления фактов, которые лучше всего усваиваются, если их выводить самостоятельно, а не читать о том, как это сделали другие;
• домашние задания, представляющие собой задачи для углубленного понимания материала той главы, к которой они относятся;
• контрольные работы, обычно охватывающие материал двух и более глав одновременно,-в основном они предназначены для выполнения дома (а не в аудитории при нехватке времени);
• конкурсные задачи, превышающие возможности, которые предполагаются у среднего студента, изучающего курс конкретной математики на базе этой книги,- они продвигают изложение в важных направлениях;
• исследовательские проблемы, разрешимые или неразрешимые человеком, но те из них, что предложены в книге, наверное следует попробовать решить (без ограничения времени) .

Ответы ко всем этим упражнениям приводятся в приложении А, зачастую с дополнительной информацией о родственных результатах. (Разумеется, ,,ответы" на исследовательские проблемы являются неполными, но даже в этих случаях могут оказаться полезными частичные результаты или указания.) Читателям не возбраняется заглянуть в ответы главным образом разминочных задач, но только ПОСЛЕ серьезных попыток решить задачу без заглядывания украдкой в ответы.

В приложении С мы постарались воздать должное первоисточникам каждого упражнения, поскольку составление той или иной поучительной задачи зачастую является весьма творческим процессом с некоторой долей везения. К сожалению, у математиков сложилась традиция заимствовать упражнения без выражения какой бы то ни было признательности; мы полагаем, что гораздо лучше противоположная традиция, практикуемая, например, в шахматных книгах и журналах (где заведен порядок специально оговаривать авторов, дату и место появления оригинальных шахматных задач). Как бы то ни было, мы не смогли выявить источники многих задач, ставших частью математического фольклора. Если кому-нибудь из читателей известно о происхождении того или иного упражнения, ссылка на которое нами пропущена или неточна, мы были бы рады узнать об этом подробнее, с тем чтобы восполнить подобный пробел в последующих изданиях этой книги.

К русскому изданию

Я С БОЛЬШИМ УДОВЛЕТВОРЕНИЕМ встретил известие о том, что перевод нашей книги опубликован в стране, где долгое время жил и создал свои основополагающие работы Леонард Эйлер, которому и посвящена книга.

Мне доставило подлинное удовольствие сотрудничество с Ириной Маховой и в ее лице с издательством "Мир" которое длится уже почти 20 лет. Было очень приятно увидеть, как элегантно Андрей Ходулёв, Ольга Лапко и их коллеги адаптировали полиграфические средства, разработанные мною для английского языка, под русские полиграфические традиции.

Я хотел бы отдать дань памяти Бориса Походзея, внесшего неоценимый вклад в перевод книги, работу над которым прервала его внезапная кончина. Во время моего визита в Санкт-Петербург в 1994 г. мы с Борисом посетили Александро-Невскую Лавру и возложили цветы на могилу Леонарда Эйлера.

Д.Э.Кнут, 1998

Начало
Полное содержание
Об авторах