Пособие написано по материалам вводного лекционного курса, который автор читает на математико-механическом факультете Санкт-Петербургского государственного университета студентам, специализирующимся по прикладной математике и информатике. Особое внимание уделяется связям между понятиями дискретного анализа, возникающими в разных разделах математики и современной информатики. В это издание включено много новых материалов, в связи с чем изменилась структура книги: появились новые главы и параграфы. Увеличено число упражнений. Текст дополнен алфавитным указателем и библиографическими рекомендациями.
Краткое содержание
Введение 1. Некоторые определения из теории множеств. 2. Строки фиксированной длины. 3. Элементарная теория вероятностей. 4. Строки переменной длины. 5. Сжатие и защита информации. 6. Информационный поиск и организация информации. 7. Предикаты и отношения. 8. Теория графов. 9. Экстремальные задачи. 10. Процессы. 11. Связи дискретного и непрерывного анализа.
В третьем издании второго тома представлено полное введение в теорию получисленных алгоритмов, причем случайным числам и арифметике посвящены отдельные главы. В книге даны основы теории получисленных алгоритмов, а также примеры этих алгоритмов. Тем самым установлено прочное связующее звено между компьютерным программированием и численным анализом.
В этой книге подробно рассмотрены структуры данных и алгоритмы, которые являются фундаментом современной методологии разработки программ. Показаны разнообразные реализации абстрактных типов данных, начиная от стандартных списков, стеков, очередей и заканчивая множествами и отображениями, которые используются для неформального описания и реализации алгоритмов.
