Обложка Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики
Id: 11029
3999 руб.

Конкретная математика.
Основание информатики

1998. 703 с. ISBN 5-03-001793-3. Букинист. Состояние: 4+. Увеличенный формат (175мм x 265мм).
  • Твердый переплет

Аннотация

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

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

Полное содержание

От Фибоначчи до Эрдёша

Предисловие

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

Значения обозначений

1 Возвратные задачи

1.1 Задача о ханойской башне

1.2 Задача о разрезании пиццы

1.3 Задача Иосифа Флавия

Упражнения

2 Исчисление сумм

2.1 Обозначения сумм

2.2 Суммы и рекуррентности

2.3 Преобразование сумм

2.4 Кратные суммы

2.5 Общие методы суммирования

2.6 Исчисление конечного и бесконечного

2.7 Бесконечные суммы

Упражнения

3 Целочисленные функции

3.1 Пол/потолок: определения

3.2 Пол/потолок: применения

3.3 Пол/потолок: рекуррентности

3.4 'mod': бинарная операция

3.5 Пол/потолок: суммы

Упражнения

4 Элементы теории чисел

4.1 Отношение делимости

4.2 Простые числа

4.3 Простые примеры

4.4 Факториальные факты

4.5 Взаимная простота

4.6 Отношение сравнимости

4.7 Независимые остатки

4.8 Дополнительные примеры

4.9 Фи- и мю-функции

Упражнения

5 Биномиальные коэффициенты

5.1 Основные тождества

5.2 Необходимые навыки

5.3 Специальные приемы

5.4 Производящие функции

5.5 Гипергеометрические функции

5.6 Гипергеометрические преобразования

5.7 Частичные гипергеометрические суммы

5.7 Механическое суммирование

Упражнения

6 Специальные числа

6.1 Числа Стирлинга

6.2 Числа Эйлера

6.3 Гармонические числа

6.4 Гармоническое суммирование

6.5 Числа Бернулли

6.6 Числа Фибоначчи

6.7 Континуанты

Упражнения

7 Производящие функции

7.1 Теория домино и размен

7.2 Основные маневры

7.3 Решение рекуррентных соотношений

7.4 Специальные производящие функции

7.5 Свертки

7.6 Экспоненциальные производящие функции

7.7 Производящие функции Дирихле

Упражнения

8 Дискретная вероятность

8.1 Определения

8.2 Математическое ожидание и дисперсия

8.3 Производящие функции случайных величин

8.4 Бросание монеты

8.5 Хеширование

Упражнения

9 Асимптотика

9.1 Иерархия

9.2 Символ О

9.3 Операции с О

9.4 Два асимптотических приема

9.5 Формула суммирования Эйлера

9.6 Завершающее суммирование

Упражнения

А Ответы к упражнениям

В Список литературы

С Первоисточники упражнений

Указатели

Именной указатель

Предметный указатель

Указатель таблиц

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

разминочные упражнения, которые должен попытаться выполнить КАЖДЫЙ ЧИТАТЕЛЬ при первом чтении книги;

обязательные упражнения, предназначенные для установления фактов, которые лучше всего усваиваются, если их выводить самостоятельно, а не читать о том, как это сделали другие;

домашние задания, представляющие собой задачи для углубленного понимания материала той главы, к которой они относятся;

контрольные работы, обычно охватывающие материал двух и более глав одновременно,-в основном они предназначены для выполнения дома (а не в аудитории при нехватке времени);

конкурсные задачи, превышающие возможности, которые предполагаются у среднего студента, изучающего курс конкретной математики на базе этой книги,- они продвигают изложение в важных направлениях;

исследовательские проблемы, разрешимые или неразрешимые человеком, но те из них, что предложены в книге, наверное следует попробовать решить (без ограничения времени) .

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

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

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

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

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

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

Д.Э.Кнут, 1998