Гид по Computer Science, расширенное издание E-Book

Вильям Спрингер

• Herausgeber: Питер
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Russisch

Seitenzahl: 228

Veröffentlichungsjahr: 2023

Beschreibung

Колосс на глиняных ногах – так можно назвать программиста без подготовки в области Computer Science. Уверенное владение основами позволяет «не изобретать велосипеды» и закладывать в архитектуру программ эффективные решения. Всё это избавляет от ошибок и чрезмерных затрат на тестирование и рефакторинг. Не беда, если вы чувствуете себя не у дел, когда другие программисты обсуждают аппроксимативный предел. Даже специалисты с опытом допускают ошибки из-за того, что подзабыли Computer Science. Расширенное издание бестселлера содержит все главные, а также продвинутые вопросы компьютерных наук: - типы и структуры данных; - алгоритмы; - графы; - теория сложности; - приемы эффективного решения задач; - безопасность; - железо и софт; - операционные системы; - сети; - базы данных и многое другое

Leseprobe

Вильям Спрингер

Гид по Computer Science, расширенное издание

Литературный редактор Н. Хлебина

Художник В. Мостипан

Корректор Е. Павлович

Вильям Спрингер

Гид по Computer Science, расширенное издание. — СПб.: Питер, 2021.

ISBN 978-5-4461-1825-0

© ООО Издательство "Питер", 2021

Все права защищены. Никакая часть данной книги не может быть воспроизведена в какой бы то ни было форме без письменного разрешения владельцев авторских прав.

Оглавление

Введение

Зачем нужна эта книга

Чего вы не найдете в издании

Дополнительные ресурсы

Что дальше

От издательства

Часть I. Основы Computer Science

1. Асимптотическое время выполнения

1.1. Что такое алгоритм

1.2. Почему скорость имеет значение

1.3. Когда секунды (не) считаются

1.4. Как мы описываем скорость

1.5. Скорость типичных алгоритмов

1.6. Всегда ли полиномиальное время лучше?

1.7. Время выполнения алгоритма

1.8. Насколько сложна задача?

2. Структуры данных

2.1. Организация данных

2.2. Массивы, очереди и другие способы построиться

2.3. Связные списки

2.4. Стеки и кучи

2.5. Хеш-таблицы

2.6. Множества и частично упорядоченные множества

2.7. Специализированные структуры данных

3. Классы задач

Часть II. Графы и графовые алгоритмы

4. Введение в теорию графов

4.1. Семь кенигсбергских мостов

4.2. Мотивация

4.3. Терминология

4.4. Представление графов

4.5. Направленные и ненаправленные графы

4.6. Циклические и ациклические графы

4.7. Раскраска графа

4.8. Взвешенные и невзвешенные графы

5. Структуры данных на основе графов

5.1. Двоичные деревья поиска

5.2. Сбалансированные деревья двоичного поиска

5.3. Кучи

6. Хорошо известные графовые алгоритмы

6.1. Введение

6.2. Поиск в ширину

6.3. Применение поиска в ширину

6.4. Поиск в глубину

6.5. Кратчайшие пути

7. Основные классы графов

7.1. Запрещенные подграфы

7.2. Планарные графы

7.3. Совершенные графы

7.4. Двудольные графы

7.5. Интервальные графы

7.6. Графы дуг окружности

Часть III. Неграфовые алгоритмы

8. Алгоритмы сортировки

8.1. Малые и большие алгоритмы сортировки

8.2. Сортировки для малых наборов данных

8.3. Сортировка больших наборов данных

8.4. Сортировки без сравнения

Часть IV. Методы решения задач

9. А если в лоб?

10. Динамическое программирование

10.1. Задача недостающих полей

10.2. Работа с перекрывающимися подзадачами

10.3. Динамическое программирование и кратчайшие пути

10.4. Примеры практического применения

11. Жадные алгоритмы

Часть V. Теория сложности вычислений

12. Что такое теория сложности

13. Языки и конечные автоматы

13.1. Формальные языки

13.2. Регулярные языки

13.3. Контекстно свободные языки

13.4. Контекстно зависимые языки

13.5. Рекурсивные и рекурсивно перечислимые языки

14. Машины Тьюринга

14.1. Чисто теоретический компьютер

14.2. Построение машины Тьюринга

14.3. Полнота по Тьюрингу

14.4. Проблема остановки

Часть VI. Доказательства

15. Приемлемые доказательства

15.1. Введение в доказательства

15.2. Терминология

16. Методы доказательства

16.1. Конструктивное доказательство, доказательство методом исчерпывания вариантов

16.2. Доказательство от противного

16.3. Доказательство методом индукции

16.4. Доказательство на основе закона контрапозиции

17. Сертификаты

Часть VII. Безопасность и конфиденциальность

18. Введение в безопасность

18.1. Конфиденциальность

18.2. Целостность

18.3. Доступность

18.4. Цели

19. Введение в криптографию

19.1. Современная криптография

19.2. Терминология

19.3. Абсолютно безопасный обмен данными

19.4. Квантовое распределение ключей

20. Криптографическая система с открытым ключом

20.1. Использование открытого и закрытого ключей

20.2. Алгоритм RSA

20.3. Соображения производительности

21. Аутентификация пользователя

Часть VIII. Аппаратное и программное обеспечение

22. Аппаратные абстракции

22.1. Физическое хранилище

22.2. Данные и методы ввода/вывода

22.3. Память

22.4. Кэш

22.5. Регистры

23. Программные абстракции

23.1. Машинный код и язык ассемблера

23.2. Низкоуровневые языки программирования

23.3. Высокоуровневые языки программирования

24. Компьютерная арифметика

24.1. Битовый сдвиг

24.2. Битовые И и ИЛИ

24.3. Битовое НЕ

24.4. Битовое исключающее ИЛИ

25. Операционные системы

25.1. Управление процессами

25.2. Управление хранилищем

25.3. Ввод/вывод

25.4. Безопасность

26. Распределенные системы

26.1. Ложные допущения относительно распределенных вычислений

26.2. Коммуникация

26.3. Синхронизация и согласованность

27. Встроенные системы

28. Сети и Интернет

28.1. Уровни протоколов

28.2. Протоколы TCP/IP и UDP

28.3. Доставка сообщения

28.4. Алгоритмы маршрутизации

29. Базы данных

29.1. Реляционные базы данных (РБД)

29.2. Иерархические базы данных (ИБД)

Часть IX. Углубленные темы

30. Основная теорема о рекуррентных соотношениях

31. Амортизированное время выполнения

32. Расширяющееся дерево

34.1. Концепции

32.2. Zig

32.3. Zig-zig

32.4. Zig-zag

33. Декартово дерево

34. Искусственный интеллект

34.1. Типы искусственного интеллекта

34.2. Подобласти ИИ

34.3. Примеры

35. Квантовые вычисления

35.1. Физика

35.2. Теоретические соображения

35.3. Практические соображения

Послесловие

Приложения

A. Необходимая математика

Б. Классические NP-полные задачи

Б.1. SAT и 3-SAT

Б.2. Клика

Б.3. Кликовое покрытие

Б.4. Раскраска графа

Б.5. Гамильтонов путь

Б.6. Укладка рюкзака

Б.7. Наибольшее независимое множество

Б.8. Сумма подмножества

Рекомендуем прочитать

Введение

Зачем нужна эта книга

Многие из моих знакомых разработчиков пришли в профессию из самых разных областей. У одних — высшее образование в области Computer Science; другие изучали фотографию, математику или даже не окончили университет.

В последние годы я заметил, что программисты все чаще стремятся изучить Compu­ter Science по ряду причин:

• чтобы стать хорошими программистами;

• чтобы на собеседованиях отвечать на вопросы про алгоритмы;

• чтобы удовлетворить свое любопытство в области Com­puter Science или наконец перестать сожалеть о том, что в свое время у них не было возможности освоить этот предмет.

Эта книга для всех вас.

Многие найдут здесь темы, интересные сами по себе. Я попытался показать, в каких реальных (неакадемических) ситуациях эти знания будут полезны. Хочу, чтобы, прочитав эту книгу, вы получили такие же знания, как после изучения базового курса по Computer Science, а также научились их применять.

Проще говоря, цель этой книги — помочь вам стать более квалифицированным и опытным программистом благодаря лучшему пониманию Computer Science. Мне не под силу втиснуть в одну книгу 20-летний стаж преподавания в колледже и профессиональный опыт... однако я постараюсь сделать максимум того, на что способен. Надеюсь, что вы найдете здесь хотя бы одну тему, о которой сможете сказать: «Да, теперь мне это понятно» — и применить знания в своей работе.

Разослав на рассмотрение черновой вариант книги, я получил множество однотипных отзывов. Слишком много материала. Слишком сложно для восприятия. Слишком устрашающе.

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

Чего вы не найдете в издании

Смысл книги состоит в том, чтобы читатель смог лучше понимать Computer Science и применять знания на практике, а вовсе не в том, чтобы полностью заменить четыре года обучения.

В частности, это не книга с доказательствами. Действительно, начиная с части VI, рассмотрены методы доказательства, однако стандартные алгоритмы обычно приводятся здесь без доказательств. Идея в том, чтобы читатель узнал о существовании этих алгоритмов и научился их использовать, не вникая в подробности. В качестве книги с доказательствами, написанной для студентов и аспирантов, я настоятельно рекомендую Introduction to Algorithms1 («Алгоритмы. Вводный курс») Кормена (Cormen), Лейзерсона (Leiserson), Ривеста (Rivest) и Стейна (Stein) (этих авторов обычно объединяют под аббревиатурой CLRS).

Это и не книга по программированию: вы не найдете здесь рекомендаций, когда использовать числа типа int, а ко­гда — double, или объяснений, что такое цикл. Предполагается, что читатель сможет разобраться в листингах на псевдокоде, используемых для описания алго­ритмов2. Цель книги — связать концепции Computer Science с уже знакомыми читателю методами программирования.

Дополнительные ресурсы

Для тех, кто хочет подробнее изучить ту или иную тему, я включил в сноски ссылки на дополнительные материалы. Кроме того, по адресу http://www.whatwil­liamsaid.com/books/ вы найдете тесты для самопроверки к каждой главе.

Что дальше

Я был намеренно краток и старался опускать детали, которые, будучи интересными сами по себе, не требуются для понимания описываемых концепций. В следующих книгах я собираюсь более подробно остановиться на некоторых областях, представляющих особый интерес.

Чтобы предложить тему для следующей книги, подписаться на рассылку или просто задать вопрос, посетите мой сайт: http://www.whatwilliamsaid.com/books. С нетерпением жду ваших сообщений.

От издательства

Ваши замечания, предложения, вопросы отправляйте по адресу [email protected] (издательство «Питер», компьютерная редакция).

Мы будем рады узнать ваше мнение!

На веб-сайте издательства www.piter.com вы найдете по­дробную информацию о наших книгах.

1Cormen T.H., Leiserson C.E., Rivest R.L., Stein C. Introduction to Algorithms, 3rd Edition. The MIT Press, 2009.

2Все программы в этой книге написаны на псевдокоде на осно­ве языка С.

Часть I. Основы Computer Science

2. Структуры данных

2.1. Организация данных

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

• Необходим ли произвольный доступ, или достаточно последовательного?

• Будут ли данные при записи всегда добавляться в конец списка, или нужна возможность вставлять значения в середину?

• Допускаются ли повторяющиеся значения?

• Что важнее: наименьшее возможное время доступа или строгая верхняя граница времени выполнения каждой операции?

Ответы на все эти вопросы определяют то, как должны храниться данные.

2.2. Массивы, очереди и другие способы построиться

Возможно, самая известная структура данных — это массив, набор элементов, проиндексированных ключом. Элементы массива хранятся последовательно, причем ключ имеет форму смещения относительно начальной позиции в памяти, благодаря чему можно вычислить положение любого элемента по его ключу. Именно по­этому индексы массива13 обычно начинаются с нуля; первый элемент массива находится на нулевом расстоянии от начала, следующий — на расстоянии одного элемента от начала и т.д. «На расстоянии одного элемента» может означать один байт, одно слово и т.д., в зависимости от размера данных. Важно, что каждый элемент массива занимает одинаковое количество памяти.