Computer Science: основы программирования на Java, ООП, алгоритмы и структуры данных
Преподаватели Принстонского университета Роберт Седжвик и Кевин Уэйн создали универсальное введение в Computer Science на языке Java, которое идеально подходит как студентам, так и профессионалам. Вы начнете с основ, освоите современный курс объектно-ориентированного программирования, и перейдете к концепциям более высокого уровня: алгоритмам и структурам данных, теории вычислений и архитектуре компьютеров.
И главное — вся теория рассматривается на практических и ярких примерах: прикладная математика, физика и биология, числовые методы, визуализация данных, синтез звука, обработка графики, финансовое моделирование и многое другое.
«Наша главная цель — дать конкретные знания и навыки, необходимые для разработки эффективных решений любой задачи по программированию. »
Роберт Седжвик и Кевин Уэйн
Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
От научного редактора русского издания . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
От издательства . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
Глава 1. Основы программирования . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.1. Ваша первая программа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
Вопросы и ответы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
1.2. Встроенные типы данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
Выводы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
Вопросы и ответы (строки) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
Вопросы и ответы (целые числа) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
Вопросы и ответы (числа с плавающей точкой) . . . . . . . . . . . . . . . . . . . . . . . 60
Вопросы и ответы (переменные и выражения) . . . . . . . . . . . . . . . . . . . . . . . . 61
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
1.3. Условные переходы и циклы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
Выводы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
Вопросы и ответы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
1.4. Массивы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
Выводы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
Вопросы и ответы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
Упражнения повышенной сложности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
1.5. Ввод и вывод . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
Выводы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
Вопросы и ответы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
Упражнения повышенной сложности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
1.6. Пример: случайный серфинг . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
Выводы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196
Упражнения повышенной сложности. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .198
Глава 2. Функции и модули . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
2.1. Определение функций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200
Вопросы и ответы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225
Упражнения повышенной сложности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
2.2. Библиотеки и клиенты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
Вопросы и ответы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260
Упражнения повышенной сложности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263
2.3. Рекурсия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265
Выводы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292
Вопросы и ответы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294
Упражнения повышенной сложности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296
2.4. Пример: задача о протекании . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300
Выводы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318
Вопросы и ответы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322
Упражнения повышенной сложности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323
Глава 3. Объектно-ориентированное программирование . . . . . . . . . . . . . . 326
3.1. Использование типов данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327
Вопросы и ответы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 369
Упражнения повышенной сложности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372
3.2. Создание типов данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 375
Вопросы и ответы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 409
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 411
Упражнения повышенной сложности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 415
3.3. Проектирование типов данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 420
Вопросы и ответы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 459
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 462
Упражнения по проектированию типов данных . . . . . . . . . . . . . . . . . . . . . . . 463
Упражнения повышенной сложности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 465
3.4. Пример: моделирование задачи n тел . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 467
Вопросы и ответы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 477
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 477
Упражнения повышенной сложности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 478
Глава 4. Алгоритмы и структуры данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . 479
4.1. Быстродействие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 480
Выводы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 504
Вопросы и ответы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 505
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 507
Упражнения повышенной сложности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 512
4.2. Сортировка и поиск . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 515
Выводы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 539
Вопросы и ответы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 541
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 542
Упражнения повышенной сложности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 544
4.3. Стеки и очереди . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 547
Вопросы и ответы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 590
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 593
Упражнения для связных списков . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 596
Упражнения повышенной сложности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 597
4.4. Таблицы символов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 602
Вопросы и ответы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 634
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 635
Упражнения для бинарных деревьев . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 639
Упражнения повышенной сложности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 640
4.5. Пример: феномен «тесного мира» . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 646
Выводы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 676
Вопросы и ответы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 678
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 679
Упражнения повышенной сложности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 683
Глава 5. Теория вычислений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 687
5.1. Формальные языки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 690
Выводы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 729
Вопросы и ответы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 730
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 731
Упражнения повышенной сложности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 734
5.2. Машины Тьюринга . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 737
Вопросы и ответы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 752
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 752
Упражнения повышенной сложности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 755
5.3. Универсальность . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 755
Вопросы и ответы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 767
Упражнения повышенной сложности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 768
5.4. Вычислимость . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 774
Вопросы и ответы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 787
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 788
Упражнения повышенной сложности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 789
5.5. Вычислительная сложность . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 790
Главный вопрос . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 809
Вопросы и ответы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 827
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 829
Упражнения повышенной сложности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 835
Глава 6. Вычислительная машина . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 838
6.1. Представление информации . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 839
Выводы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 866
Вопросы и ответы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 867
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 870
Упражнения повышенной сложности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 873
6.2. Машина TOY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 874
Вопросы и ответы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 896
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 897
6.3. Программирование на машинном языке . . . . . . . . . . . . . . . . . . . . . . . . . . . . 900
Вопросы и ответы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 915
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 916
Упражнения повышенной сложности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 921
6.4. Виртуальная машина TOY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 923
Вопросы и ответы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 943
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 944
Упражнения повышенной сложности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 945
Глава 7. Построение вычислительного устройства . . . . . . . . . . . . . . . . . . . 948
7.1. Булева логика . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 949
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 960
Упражнения повышенной сложности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 961
7.2. Базовая модель электронной схемы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 963
Вопросы и ответы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 971
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 972
7.3. Комбинационные схемы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 973
Вопросы и ответы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1004
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1004
Упражнения повышенной сложности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1007
7.4. Последовательностные схемы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1010
Выводы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1025
Вопросы и ответы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1027
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1028
Упражнения повышенной сложности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1030
7.5. Цифровые вычислительные устройства . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1031
Вопросы и ответы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1052
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1053
Упражнения повышенной сложности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1053
Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1054
Глоссарий . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1057
API . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1066
Изучаем Python, том 1, 5-е издание3 280 ₽
Java. Полное руководство, 10-е издание4 430 ₽
Анализ ценных бумаг. 3-е издание5 690 ₽