Седжвик Р., Уэйн К. - Computer Science: Основы программирования на Java, ООП, алгоритмы и структуры данных (2018)

Предисловие.......................................................................................................... 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
Оглавление 7
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
8 Оглавление
3.3. Проектирование типов данных.......................................................................... 420
Вопросы и ответы................................................................................................. 459
Упражнения..........................................................................................................462
Упражнения по проектированию типов данных.......................................................... 463
Упражнения повышенной сложности ........................................................................465
3.4. Пример: моделирование задачи п тел ...............................................................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
Оглавление 9
Упражнения......................................................................................................... 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. Машина TO Y.................................................................................................. 874
Вопросы и ответы.................................................................................................896
Упражнения........................................................................................................ 897
10 Оглавление
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