Курс «Алгоритмы и структуры данных поиска» от ШАД. Книга: Никлаус Вирт «Алгоритмы и структуры данных

В процессе построения учебной программы наших образовательных проектов мы составили список специализированных книг, рекомендованных к изучению по каждой из дисциплин, - всего более 100 наименований на весь период обучения. Не станем таить и представим вам этот список, сопроводив краткими комментариями. Уместить такой объем информации в рамках одной статьи затруднительно, поэтому обзор рекомендованной Технопарком литературы разбит на четыре части - по числу семестров, с небольшой добавкой полезных книг, предложенных студентами. Ссылки в комментариях на дополнительное интересное чтиво только приветствуются.

Первый семестр призван «выровнять» знания студентов. Он содержит такие дисциплины, как алгоритмы и структуры данных, программирование на C++, а также обзорный курс по веб-технологиям. С книг по этим предметам и начнется обзор. Большая часть представленных книг относится к нестареющей «классике», являющейся собранием основополагающих концепций.

Веб-технологии

Виктор и Наталья совместно создали и разработали более 22 учебных курсов, в течение многих лет вели курс лекций в МИРЭА, МГТУ им. Н.Э. Баумана, а также в Центре информационных технологий.

Книга «Компьютерные сети. Принципы, технологии и протоколы» рекомендована Министерством образования РФ. Издание подойдет для тех, кто хотел бы получить базовые знания о принципах построения компьютерных сетей, понять особенности традиционных и перспективных технологий локальных и глобальных сетей, изучить способы создания крупных составных сетей и управления ими.

Крикет Ли - выпускник Калифорнийского университета в Беркли. После учебы он устроился в Hewlett-Packard, где проработал девять лет. В 1997 г. покинул HP и основал компанию Acme Byte & Wire, осуществляющую консультации и обучение в области DNS. На протяжении одного года Крикет работал директором по DNS-продуктам в Verisign Global Registry Services. В марте 2003 г. перешел в компанию Infoblox, создающую DNS- и DCHP-устройства, где занял пост вице-президента.

Пол Альбитц получил степень бакалавра наук в университете Висконсина и магистра наук в университете Пердью. Работал в Hewlett-Packard над версиями BIND для системы HP-UX версий 7.0 и 8.0. Он создал инструменты, используемые для управления доменом hp.com.

Книга «DNS and BIND» - словно Библия для системных администраторов. Материал в ней подается простым, доступным языком. Издание посвящено BIND 9.3.2 и BIND 8.4.7. BIND 9.3.2 включает усовершенствования безопасности и поддержки IPv6, а также ENUM, SPF, и использование доменных имен, содержащих буквы национальных алфавитов.

Здесь вы найдете всю необходимую информацию о принципах работы DNS, о структуре пространства доменных имен, об установке и настройке серверов имен, о программировании при помощи функций библиотеки DNS-клиента и о многом-многом другом.

Книга: «SQL для простых смертных»

Писатель, учитель и консультант Мартин Грабер несколько десятилетий назад создал полное введение в структурированный язык запросов, благодаря которому до сих пор можно легко научиться работать с SQL. «SQL для простых смертных» - руководство для любой реализации языка структурированных запросов, в котором приводится справочник по стандартному SQL, а также имеется описание общих свойств нестандартного SQL.

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

Книга: «Основы реляционных баз данных»
Авторы: Дженнифер Уидом, Джеффри Д. Ульман

Дженнифер Уидом - доцент факультетов информатики и электротехники Стэнфордского университета, активный участник исследований в области гетерогенных и полуструктурированных баз данных (БД), методов хранения данных и активных систем БД.

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

Книга «Основы реляционных баз данных» будет полезна всем, кто изучает базы данных. В ней рассмотрены стандарты SQL2, SQL3, ODMG, ODL/OQL, традиционный метод проектирования баз данных, а также анализируется множество аспектов программирования на языке SQL.

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

Книга: «jQuery. Подробное руководство по продвинутому JavaScript»
Авторы: Беэр Бибо, Иегуда Кац

Беэр Бибо - веб-разработчик с более чем 30-летним стажем программирования. Один из авторов книг «jQuery in Action», «Ajax на практике», «Ajax: библиотеки Prototype и Scriptaculous в действии».

Иегуда Кац разрабатывал веб-сайты для New York Times, Allure Magazine, Architectural Digest, Yoga Journal. Участник основной команды проекта jQuery, принимал участие в разработке Merb (альтернативы Ruby on Rails).

Издание «jQuery. Подробное руководство по продвинутому JavaScript» - действительно подробное справочное руководство по платформе для разработки веб-приложений, в котором описывается, как выполнять обход документов HTML, обрабатывать события, добавлять поддержку технологии Ajax в свои веб-страницы, воспроизводить анимацию, взаимодействие другими инструментами, платформами и методами создания модулей расширения для jQuery. Книга предназначена для тех, кто уже знаком с JavaScript и Ajax.

Книга: «Изучаем Python»

Если вы хоть немного знаете, что такое Python, то и Марк Луц вам знаком. Он является одним из ведущих специалистов в мире по Питону, автором самых ранних и наиболее популярных публикаций. Лутц использует Питон и занимается его популяризацией уже более 20 лет, большую часть времени уделяя преподаванию и написанию книг по этому языку.

Четвертое издание «Изучаем Python» содержит основные типы объектов в языке, порядок их создания и работы с ними, а также включает методы работы с модулями и дополнительными объектно-ориентированными инструментами - классами. Приводятся описания моделей и инструкций обработки исключений, а также обзор инструментов разработки.

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

• 3-е издание «Learn Python the Hard Way» содержит хорошие курсы для начального изучения Питона и закрепления освоенного материала: http://learnpythonthehardway.org/ .
• Вы новичок в Django или программировании? Все, что вам надо знать о Django: http://www.djbook.ru/rel1.7/
• Учебник по созданию сайтов для начинающих, содержащий простые и легкие в освоении материалы: www.htmlbook.ru .

Алгоритмы и структуры данных

Книга: «Информатика. Основополагающее введение. Часть I»

Том I четырехтомника выдающегося немецкого ученого Манфреда Боя, лауреата премии Лейбница в области информатики, посвящен базовым понятиям информации и различным формам ее обработки. Манфред дает подробное объяснение алгоритмов (включая их классификацию, описание и исполнение), методов программирования, машинно-ориентированных языковых элементов. Книга содержит исчерпывающие объяснения по вопросам представления и обработки информации.

Книга: «Алгебраическая алгоритмика. С упражнениями и решениями»
Авторы: Клод Китте, Патрис Ноден

Два французских математика в книге, изобилующей формулами, дают ответ на вопрос «что и как можно вычислять?». Авторы упоминают «Искусство программирования» (о котором мы обязательно расскажем дальше) как главный источник вдохновения. Сходство между ними определенно прослеживается.
Книгу можно рекомендовать всем, кто применяет компьютерную алгебру и изучает ее. Трудно найти наиболее исчерпывающее издание по вычислению математических объектов.

Книга: «Алгоритмы и структуры данных»

Про таких людей обычно говорят: в представлении не нуждается. Мы все же кратко заметим, что Никлаус Вирт - ученый, инженер, лауреат премии Тьюринга, один из известнейших в мире теоретик языков программирования, создатель языков Паскаль, Модула-2, Оберон.

Книги Вирта по структурному программированию в образовании считаются обязательным стандартом.

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

Книга: «Структуры данных и алгоритмы»
Авторы: Альфред В. Ахо, Джон Э. Хопкрофт, Джеффри Д. Ульман

Альфред Ахо - канадский ученый-информатик, один из создателей интерпретируемого скриптового C-подобного языка AWK, автор и соавтор множества публикаций и книг по различным аспектам информатики.

Джон Хопкрофт - американский ученый, лауреат премии Тьюринга, исследователь теоретических аспектов информатики, в частности анализа алгоритмов и теории графов.

Джеффри Ульман - известный исследователь в области информационных технологий, один из авторов «классических» учебников по компиляторам, теории вычислений и базам данных.

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

Книги:
«Фундаментальные алгоритмы на C. Части 1-5. Анализ. Структуры данных. Сортировка. Поиск. Алгоритмы на графах»
«Алгоритмы на C++»

Глубокое исследование основополагающих концепций алгоритмов провел профессор Принстонского университета, автор многочисленных научных статей и серии учебников по алгоритмам Роберт Седжвик. В «Фундаментальных алгоритмах на C» подробно рассмотрены поиск в орграфах, неорграфах и сетях, построение минимальных остовных деревьев и кратчайших путей, вычисление потоков в сетях с различными характеристиками. Большое внимание уделяется рабочим характеристикам алгоритмов, а также их математическому выводу.

«Алгоритмы на C++» - это и продолжение, и переосмысление описания алгоритмов и структур данных, на этот раз выполненное на C++, хотя приведенные сведения являются фундаментальными и применимы к программированию на любом языке. В книгу добавлены новые алгоритмы, иллюстрации, комментарии и т.д.

Книга: «Структуры данных и алгоритмы в Java»

Роберт Лафоре пишет книги по программированию уже 30 лет. Благодаря его книгам неисчислимое количество программистов овладели технологиями объектно-ориентированного программирования.
Книга «Структуры данных и алгоритмы в Java» посвящена основам использования алгоритмов, с примерами, выполненными на Java, хотя для обучения достаточно владеть любым языком программирования. В книге подробно рассматриваются такие темы, как сортировка, абстрактные типы данных, связанные списки, рекурсия, древовидные структуры данных, хеширование, пирамиды, графы.

Книга: «Дискретный анализ»

Иосиф Романовский - в нашей подборке редкий представитель отечественных авторов. Профессор кафедры исследования операций СПбГУ, автор целого ряда эффективных алгоритмов для решения оптимизационных задач, включая компьютерную реализацию этих алгоритмов, написал популярные лекционные курсы по оптимальному программированию и программированию на ЭВМ алгоритмов оптимизации.

Пособие «Дискретный анализ» написано по материалам лекционного курса Иосифа Романовского. В нем акцент сделан на связи между понятиями дискретного анализа, возникающими в разных разделах математики и современной информатики.

Книга: «Конкретная математика. Основание информатики»
Авторы: Роналд Грэхем, Дональд Эрвин Кнут, Орен Паташник

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

В книге содержится более 500 упражнений различного уровня сложности, излагаемых в неформальном стиле и сопровождаемых «заметками на полях» от первых редакторов книги - студентов Стэнфорда. Рекомендуем всем изучающим и применяющим дискретную математику и информатику.

Книга: «Алгоритмы. Построение и анализ»
Авторы: Томас Х. Кормен, Чарльз Э. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн

Клиффорд Штайн - профессор, специалист в области компьютерных наук.

Рональд Линн Ривест - специалист по криптографии, автор симметричных алгоритмов шифрования RC2, RC4, RC, один из авторов алгоритма RSA.

Чарльз Эрик Лейзерсон - профессор Массачусетского технологического института, специализируется на теории параллельных, распределенных вычислений и практическом ее применении.

Томас Кормен - профессор, преподает в Дартмутском колледже, также занимает должность директора по написанию программ в этом учреждении.

Книга «Алгоритмы. Построение и анализ» - фундаментальный труд в области алгоритмов. В ней используются примеры псевдокода, который понятен любому, кто хоть в малой степени знаком с программированием, а пояснения принципов работы даны без излишней математической строгости и требуют лишь элементарных знаний.

Первое издание этой книги стало стандартным справочным руководством для профессионалов и учебным пособием для университетов. Дальнейшие издания получили многочисленные дополнения, множество новых упражнений и задач. Третье издание содержит Деревья ван Эмде Боаса и многопоточные алгоритмы.

Книга: «Искусство программирования. Том 1-4»

Профессор Кнут - один из самых уважаемых и цитируемых в мире авторов книг по программированию. Также он написал серию всемирно известных книг по основным алгоритмам и методам вычислительной математики. Дональд Кнут удостоен многочисленных премий и наград, а с 1996 г. присуждается премия его имени - за особый вклад в развитие основ информатики.

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

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

Книга: «Analytic Combinatorics»
Авторы: Филипп Флажоле, Роберт Седжвик

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

Книга «Analytic Combinatorics» является одним из наиболее свежих подходов к проблеме обеспечения возможности точных количественных предсказаний свойств больших комбинаторных структур. Авторы (среди которых и уже знакомый нам Роберт Седжвик) дают полный объем необходимой базовой математики, а также тщательно рассматривают как классические, так и современные приложения теории аналитической комбинаторики. В книге содержатся наглядные примеры приложений, упражнения и примечания.

Книга: «Комбинаторика для программистов»

Витольд Липский - польский специалист по программированию, профессор Парижского университета, обладатель докторской степени. Книга «Комбинаторика для программистов» охватывает широкий спектр комбинаторных и теоретико-графовых алгоритмов. Описание алгоритмов дано на Паскале. Стиль изложения - справочный: постановка задачи, алгоритм ее решения, комментарии, трудоемкость, примеры.

Книга: «Строки, деревья и последовательности в алгоритмах. Информатика и вычислительная биология»

Профессор Дэн Гасфилд преподает в университете Дэвиса, Калифорния. В круг его интересов входят исследования в области эффективности алгоритмов, связанных с комбинаторной оптимизацией. Гасфилд особо интересуется комбинаторными проблемами, возникающими в вычислительной молекулярной биологии (в частности? биоинформатики и геномики).

Книга «Строки, деревья и последовательности в алгоритмах. Информатика и вычислительная биология» будет интересна не только тем, кто интересуется биологией, но и всем, кто хочет самостоятельно познакомиться с современными алгоритмами обработки практической информации.

Книга: «Методы и алгоритмы вычислений на строках»

Профессор Уильям Ф. (Билл) занимался консультированием в области использования компьютерных технологий в бизнесе и правительственных организациях. Основная область его исследования - комбинаторные алгоритмы.

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

Книга: «Алгоритмические трюки для программистов»

Генри Уоррен более 40 лет проработал в IBM. Он трудился над рядом военных командно-управляющих систем и над проектом языка программирования SETL. С 1973 г. Уоррен занимается компиляторами и архитектурой компьютеров в исследовательском подразделении IBM.

Книга «Алгоритмические трюки для программистов» содержит множество трюков компьютерной арифметики, которые будут крайне полезны разработчикам библиотек и компиляторов, а также всем, кто хочет быстро создавать эффективный код. В книге представлены примеры работ с отдельными битами, байтами, вычисления различных целочисленных функций.

Книга: «Дискретная математика для программистов»

Федор Александрович Новиков - доцент кафедры прикладной математики Санкт-Петербургского государственного политехнического университета и кафедры технологий программирования Санкт-Петербургского государственного университета информационных технологий, механики и оптики. В учебнике «Дискретная математика для программистов» изложены основные разделы дискретной математики и описаны важнейшие алгоритмы на дискретных структурах данных.

Книга допущена Министерством образования и науки Российской Федерации в качестве учебного пособия для студентов высших учебных заведений, обучающихся по направлению подготовки дипломированных специалистов «Информатика и вычислительная техника».

Книга: «Дискретная математика для инженера»

Олег Петрович Кузнецов - заведующий сектором Института проблем управления РАН, доктор технических наук. В книге «Дискретная математика для инженера» изложены основные понятия теории множеств, общей алгебры, логики, теории графов, теории алгоритмов и формальных систем, теории автоматов. Издание представляет интерес для инженеров, специализирующихся в области автоматизированного управления и проектирования, вычислительной техники, информационных технологий и передачи информации.

Углубленное программирование на С++

Книга: «Приемы объектно-ориентированного проектирования. Паттерны проектирования»
Авторы: Эрих Гамма, Ричард Хелм, Ральф Джонсон, Джон Влиссидес

Эрих Гамма - программист из Швейцарии, ведущий разработчик фреймворка для выполнения юнит-тестов на джаве JUnit и кросс-платформенной интегрированной среды разработки ПО (Eclipse). Работал в IBM над проектом масштабируемой платформы с открытым кодом от для разработки ПО (Jazz).

Программист Ричард Хелм также работал в IBM, в исследовательском центре компании, занимающемся разработкой новых технологий.

Джон Влиссидес работал в Стэнфордском университете, а с 1991 г. - в исследовательском центре IBM. Является автором нескольких книг, многих статей и докладов по объектно-ориентированным технологиям, паттернам проектирования и моделированию программного обеспечения.

Авторы, известные как «банда четырех», подарили миру изящное решение типичных задач, возникающих в ООП. Книга состоит из двух частей: в первой рассказывается о возможностях и недостатках ООП, во второй части описаны 23 классических шаблона проектирования. Приводящиеся в книге примеры написаны на языках программирования C++ и Smalltalk.

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

Книга: «Рефакторинг с использованием шаблонов»

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

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

Кириевски ссылается на книгу Фаулера «Рефакторинг. Улучшение существующего кода», поэтому для более глубокого понимания способов ввода в архитектуру программы паттернов «Рефакторинг с использованием шаблонов» рекомендуется читать уже после. Дополнительных знаний вам не потребуется, и хотя все приводятся на джаве, в них не используются сложные особенности языка. Книга будет полезна как программистам среднего уровня, так профессионалам.

Книга: «Язык программирования C++. Вводный курс»
Авторы: Стенли Б. Липпман, Жози Лажойе, Барбара Му

Стэнли Б. Липпман работал с Бьёрном Страуструпом в исследовательской корпорации Bell Lab на ранних стадиях разработки C++. В 2001 г. Стэнли Липпман стал главным архитектором Visual C++ в Microsoft. Он также работал в Emergent Game Technologies, НАСА, Pixar и 2kQubits.

Жози Лажойе участвовала в работе над компилятором С++ в IBM Canada, а также возглавлял рабочую группу базового языка C++ в составе международной организации по стандартизации ANSI/ISO.

Барбара Му имеет почти 30-летний опыт программирования. На протяжении 15 лет она работала в компании AT&T, сотрудничала с Бьёрном Страуструпом, несколько лет руководила группой разработчиков C++.

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

По мере развития C++ в книгу вносятся соответствующие изменения. Помимо фундаментальных концепций, в новой версии книги приводятся наиболее эффективные приемы, позволяющие читателю создавать собственные программы еще до углубленного знакомства с особенностями языка.

Книга: «STL. Карманный справочник»

Рэй Лишнер в первую очередь известен в Delphi-коммьюнити как автор книг «Secrets of Delphi 2», «Hidden Paths of Delphi 3» и многих статей для таких журналов, как «Delphi Informant», «Dr. Dobb"s Journal». Но мы рекомендуем другую его книгу - «STL. Карманный справочник». Это действительно справочник по подмножеству стандартной библиотеки C++. В книге описана библиотека STL в современном виде - алгоритмы, итераторы и контейнеры стандартной библиотеки C++, а также ряд других элементов. Приводится краткая сводка по функциям, классам и шаблонам, образующим STL.

Книга: «Совершенный код. Мастер-класс»

Стив Макконнелл - программист, редактор и эксперт в области разработки ПО. Он дважды был удостоен премии Jolt Excellence за лучшую книгу года по разработке софта. По степени влияния на отрасль его сравнивали с Биллом Гейтсом и Линусом Торвальдсом.

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

«Совершенный код» - книга, которую должен прочитать каждый программист. И желательно сделать это несколько раз.

Книга: «C++ и STL. Справочное руководство»
Авторы: Дэвид Р. Мюссер, Жилмер Дж. Дердж, Атул Сейни

Дэвид Р. Мюссер - преподаватель, работал с STL с момента ее зарождения: первая реализация библиотеки разработана при его непосредственном участии. Кроме того, он работал над тем, чтобы STL была включена в стандарт ANSI/ISO C++.

Жилмер Дж. Дердж - президент Toltec Software Services Inc., имеет большой опыт разработки приложений на C++, в том числе семь лет - в фирме General Electric Corporate R&D.

Атул Сейни - президент Fiorano Software Inc., производителя программного обеспечения для высокоскоростного обмена сообщениями, разрабатываемого на C++. Он стал первым, кто увидел коммерческий потенциал STL, и предложил свою компанию для продажи библиотеки еще до того, как она вошла в стандарт C++.

Книга «C++ и STL. Справочное руководство» включает небольшой учебный курс, подробное описание каждого элемента библиотеки и большое количество примеров. Книга содержит исчерпывающее описание итераторов, обобщенных алгоритмов, контейнеров, функциональных объектов и т.д. В ней также дается объяснение, как интегрировать STL с другими объектно-ориентированными методами программирования.

Книги:
«Решение сложных задач на С++»
«Новые сложные задачи на C++»
«Стандарты программирования на С+»

Герб Саттер - признанный эксперт по C++. Начал работать в Microsoft в качестве евангелиста платформы Visual C++ .NET и достиг должности архитектора ПО C++/CLI. 10 лет он был организатором и секретарем комитета по стандартизации ISO C++. Много лет регулярно публиковал нетривиальные задачи на C++ в серии под названием Guru of the Week. Позднее Саттер опубликовал развернутые версии многих задач в своих первых двух книгах «Решение сложных задач на C++».

Рекомендуем сразу три его книги, рассчитанные на читателя с достаточно глубоким знанием языка. В форме задач и их решений рассматриваются современные методы проектирования и программирования на C++. В книгах сконцентрирован многолетний опыт разработок C++: рассмотрены конкретные методики, приемы и идиомы программирования, особое внимание уделено вопросу проектирования, которое должно обеспечить максимальную надежность, безопасность, производительность и сопровождаемость создаваемого ПО.

Книга: «Алгоритмы на C++»

О Роберте Сеждвике мы уже рассказывали выше. В книге «Алгоритмы на C++» рассматриваются фундаментальные алгоритмы, структуры данных, сортировка и поиск, алгоритмы на графах, которые играют все более важную роль во множестве приложений, таких как сетевая связность, конструирование электронных схем, составление графиков, обработка транзакций и выделение ресурсов.

В книге подробно описаны массивы, связные списки, строки, деревья и другие базовые структуры данных. Внимание читателя акцентируется на абстрактных типах данных (АТД), на модульном программировании, на ООП и классах C++, приводится более 100 алгоритмов сортировки, выбора, реализаций АТД очереди с приоритетами и реализаций АТД таблицы символов (для поиска).

Книги:
«Язык программирования С++»
«Программирование. Принципы и практика использования C++»

Невозможно представить подборку книг о C++ без учебников самого автора языка. Бьёрн Страуструп - настоящая легенда, а «Язык программирования C++» является одной из самых широко читаемых книг в своей области. Книги Страуструпа отличает непревзойденное мастерство в области технической документации. Это безусловный канон по возможностям языка.

Первое издание книги «Язык программирования С++» выпущено 29 лет назад. Второе было опубликовано в 1991 г., третье - в 1997 г. Улучшенная версия третьего издания, выпущенная в твердой обложке, получила название «Специальное издание» и отличалась от ранних выпусков третьего издания двумя дополнительными приложениями («Локализация» и «Безопасность исключений и стандартная библиотека»), примерно 1 тыс. исправлений и уточнений, а также дополненным алфавитным указателем. Четвертое издание книги, которая включает в себя C++11, выпущено в 2013 г.

Если вы программируете на С++, то прочесть эту книгу нужно прямо сейчас.

Книга: «Рефакторинг. Улучшение существующего кода»
Авторы: Мартин Фаулер, Кент Бек, Джон Брант, Уильям Апдайк, Дон Робертс

Программист Кент Бек создал такие методологии разработки ПО, как экстремальное программирование и разработка через тестирование. Он является одним из пионеров введения в практику шаблонов проектирования ПО, создания методологии разработки через тестирование, а также коммерческого использования языка Smalltalk. Совместно с Эрихом Гамма создал фреймворк для тестирования JUnit.

Уильям Апдайк написал докторскую диссертацию по рефакторингу объектно-ориентированных сред (в университете штата Иллинойс), послужившую основой первой крупной публикации на данную тему.

Книга «Рефакторинг. Улучшение существующего кода» рассказывает о процессе рефакторинга, описывает принципы углубленного изучения кода с целью его улучшения. В книгу включены более 70 методов рефакторинга, для каждого из которых описываются мотивация и техника испытанного на практике преобразования кода с примерами на Java.

«Must read» для всех разработчиков.

Книга: «Полный справочник по C++»

Шилдт - писатель, ученый и программист, был членом комитета ANSI, который принимал стандарты С, и комитета ISO, принимавшего стандарты C++. Автор интерпретатора Little C - примера рекурсивного нисходящего парсера.

«Полный справочник по C++» содержит все ключевые слова, функции, классы и свойства языка, соответствующие стандарту ANSI/ISO. В нем освещаются все аспекты языка, включая его основу - язык С.

АЛГОРИТМЫ + СТРУКТУРЫ ДАННЫХ = ПРОГРАММЫ

Монография известного швейцарского специалиста по системному программированию, знакомого советским читателям по переводу его книги «Систематическое программирование. Введение.» (М.: Мир. 1977). Она содержит описание и анализ основных алгоритмов, методов построения программ. Книгу можно использовать и как руководство по применению языка Паскаль в задачах математического обеспечения ЭВМ.

Для научных работников, преподавателей, аспирантов и студентов, специализирующихся по математическому обеспечению ЭВМ.

Б-дерево бинарное 295

- - симметричное 298 Буквы латинские 24 Буфер 54

Бэйер 282, 289, 295, 298

Варианты в записях 35 Вес дерева 264 Ветвь 223

Возврат 9, 168, 325

Вольтер 13

Восстановление при ошибках 373 Время патентное 58 Выборочное изменение 28 Выравнивание 46 Выражение 17

Индексное 27

Высота дерева 220

Гаусс 169 Гильберт156

Глубина дерева 220 Горизонтальное распределение 134

Готлиб 267

Грамматический разбор 10, 328

Нисходящий 323

- - целеориентированный 328 Граф распознавания 328

- синтаксический 328

- - детерминированный 332 Графы 19 Данные 11

Дейкстра 7, 12

Дерево 10, 19, 219

АВЛ-сбалансированное 248

Бинарное 223

Вырожденное 220

- идеально сбалансированное 226

- лексикографическое 238

Оптимальное 263

Поиска 231

- сильно ветвящееся 223

Сортировки 91

- упорядоченное 220

Фибоначчи 249 2-3 дерево 295

Диаграмма зависимости 361 Дизъюнкция логическая 23 Диски магнитные 57 Дискриминант типа 36 Длина пути 220

Взвешенная 261

Внешнего 220

- - внутреннего 220 Доступ последовательный 53

Прямой 58

- случайный 25 Заглядывание вперед 55, 68 Заголовок списка 314

Задача об устойчивых браках 174

- о восьми ферзях 169

О ходе коня 164

- оптимального выбора 182

- поиска медианы 103

- построения школьного расписания

Запись (record) 8, 31, 48

- с вариантами 36 Запись бесскобочная 377

Инфиксная 230

Польская 377

Постфиксная 230

Искусственный интеллект 163 Итерация 9, 99, 154 Карта (индексов) 123, 128 Квантиль 105

Ключ 76, 303

Ключей преобразование 303 Ключи переменной длины 318

Кнут 77, 86, 134, 144, 264

Кольца 19 Конкатенация 51, 52, 54 Константа 17 Конструктор 20

Записи 32

Массива 26

Контекстная зависимость 322 Конфликт 304 Конфликтов разрешение 304 Конъюнкция логическая 23 Координаты 15, 31, 36

Декартовы 15, 36 Корень дерева 220

Коэффициент заполнения 312

- использования памяти 46

Кривая Гильберта 156

Серпинского 158

Кустарники 299

Ландис 248, 249

Магнитная 108

Лист дерева 220

Лорин 77 Лукасевич377 Мак-Вити 179 Мак-Крейт 289

Мантисса 15

Массив 19, 25, 44

Матрица 29 Машина ПЛ/0 373 Медиана 101, 103 Метасимволы 320

Метод деления пополам 28

Пузырька 84

- рассеянных таблиц 307 Множеств объединение 40

Пересечение 40

Разность 40

Сложение 40

- умножение 40 Множество 15, 19, 38 Множество-степень 38

Множеству принадлежность 40

Моррис 306

Нотация 52 Область переполнения 306 Обход дерева 229

Оператор варианта 37

- присоединения 34, 286

Процедуры 190

Условный 190

Цикла 29

С параметром 190

С предисловием 190 Операции булевские 23

Над файлами 54

Отношений 40

- преобразования 20 I/O-операции 62 Операция 17, 18, 19 Описание 17

Опробирование квадратичное 307

Линейное 306

Открытая адресация 306 Очередь 198 Ошибки наведенные 373

Память для программы 373

Оперативная 295

Паскаль 8, 11, 16, 19, 62

Переменная буферная 55 Переменные 17, 23 Переупорядочение списка 209 Пирамида 91

ПЛ/0 331, 349 ПЛ/1 20

Поддерево 223 Поиск бинарный 28 -- в списке 202

Медианы 103

- по дереву с включением 233

- по списку самоорганизующийся

Поле 48 Поле признака 36

Порядок Б-дерева 282

Частичный 211

- числа 15 Последовательность 16, 19, 52 Потомок 220 Поэтапное уточнение 11, 67, 344 Правила подстановки 320

Порождающие 320

В книге даны краткие сведения о современных отечественных и зарубежных микроЭВМ индивидуального пользования. Описаны основные версии бейсика, наиболее распространенного языка программирования персональных ЭВМ (ПЭВМ), отечественных микро- и мнниЭВМ (Электроиика-60, Электроника-, ДЗ-28, Искра-226, диалоговых вычислительных комплексов ДВК-1, ДВК-2 и др.). Изложены основы программирования на бейсике. Основное внимание уделено общему математическому, алгоритмическому и программному обеспечению расчетов на ПЭВМ. В справочник включена обширная Библиотека прикладных программ на бейсике (более 300 программ), обеспечивающих реализацию основных численных методов, вычисление большинства специальных функций и решение ряда практиеских задач в различных областях науки и техники.

Для инженеров, научно-технических работников и студентов втузов.

Дьяконов В. П. Справочник по алгоритмам и программам иа языке бейсик для персональных ЭВМ : Справочник. - Москва. Издательство Наука. Гл. ред. физ.-мат. лит., 1989.- 240 с. - ISBN 5-02-014530-0.

Предисловие
Как пользоваться справочником
Глава 1. Основные характеристики и возможности персональных ЭВМ
§ 1.1. Современные типы персональных ЭВМ и их возможности
§ 1.2. Карманные персональные ЭВМ (Pocket Computers)
§ 1.3. Персональные ЭВМ среднего класса (Home Computers)
§ 1.4. Профессиональные ЭВМ и вычислительные микросистемы индивидуального пользования
§ 1.5. Периферийное оборудование персональных ЭВМ

Глава 2. Бейсик - основной язык программирования персональных ЭВМ
§ 2.1. Алфавит и основные операторы языка бейсик
§ 2.2. Модификации языка бейсик
§ 2.3. Арифметические и алгебраические операции, работа в режиме калькулятора
§ 2.4. Элементарное программирование на языке бейсик
§ 2.5. Специальные вопросы программирования на языке бейсик
§ 2.6. Перевод программ с одной версии языка бейсик на другую

Глава 3. Алгоритмы и программы элементарных вычислений
§ 3.1. Операции с действительными числами
§ 3.2. Операции и функции с комплексными числами и переменными
§ 3.3. Вычисление степенных многочленов и дробно-рациональных функций
§ 3.4. Вычисление ортогональных многочленов
§ 3.5. Операции с матрицами
§ 3.6. Вычисление факториалов и комбинаторика
§ 3.7. Преобразования координат и векторный анализ

Глава 4. Алгоритмы и программы реализации основных численных методов
§ 4.1. Решение систем линейных уравнений
§ 4.2. Интерполяция и экстраполяция
§ 4.3. Решение нелинейных и трансцендентных уравнений
§ 4.4. Решение систем нелинейных уравнений
§ 4.5. Решение алгебраических уравнений с действительными и комплексными коэффициентами
§ 4.6. Поиск экстремумов функций одной и множества переменных
§ 4.7. Численное дифференцирование и вычисление коэффициентов чувствительности
§ 4.8. Вычисление определенных интегралов
§ 4.9. Вычисление определенных интегралов специального вида
§ 4.10. Решение систем дифференциальных уравнений
§ 4.11. Гармонический синтез
§ 4.12. Вычисление собственных значений и векторов матриц

Глава 5. Спектральный, статистический, корреляционный и регрессионный анализ
§ 5.1. Спектральный анализ на основе дискретного преобразования Фурье
§ 5.2. Специальные виды спектрального анализа
§ 5.3. Статистический анализ и подготовка гистограмм
§ 5.4. Реализация метода Монте-Карло
§ 5.5. Корреляционный анализ
§ 5.6. Регрессионный анализ (приближение функций по методу наименьших квадратов)
§ 5.7. Сглаживание данных эксперимента

Глава 6. Вычисление специальных функций
§ 6.1. Методы вычисления специальных функций
§ 6.2. Интегральные показательные функции
§ 6.3. Интегральные синус и косинус
§ 6.4. Гамма-функции (включая неполные)
§ 6.5. Функции Бесселя (включая модифицированные)
§ 6.6. Функции Эйри
§ 6.7. Интегралы Френеля
§ 6.8. Эллиптические интегралы
§ 6.9. Функции Струве, Ангера и Вебера
§ 6.10. Гипергеометрические функции
§ 6.11. Дилогарифм
§ 6.12. Функции Кельвина
§ 6.13. Функции Дебая и Зиверта
§ 6.14. Интеграл вероятности и родственные ему функции
§ 6.15. Некоторые статистические функции

Глава 7. Прикладные программы технических и экономических расчетов
§ 7.1. Типовые электротехнические расчеты
§ 7.2. Расчет индуктивных элементов
§ 7.3. Расчет емкостных элементов и конденсаторов
§ 7.4. Расчет линий передачи и Задержки
§ 7.5. Расчет усилителей
§ 7.6. Расчет активных фильтров
§ 7.7. Расчет нелинейных и ключевых электронных устройств
§ 7.8. Расчеты в механике и термодинамике
§ 7.9. Финансово-экономические расчеты

Приложение 1. Подготовка к работе системы подготовки программ на базе микроЭВМ Электроника-ДЗ-28
Приложение 2.

Номера ошибок и их содержание для систем подготовки программ на базе микроЭВМ Электроника-ДЗ-28
Приложение 3. Подготовка ПЭВМ FX-702P к работе
Приложение 4. Номера ошибок и их содержание для ПЭВМ FX-702P
Приложение 5. Программная реализация некоторых численных методов частного применения
§ П5.1. Построение полинома по его действительным корням
§ П5.2. Обращение матрицы, вычисление определителя и решение систем линейных уравнений с разными векторами свободных членов
§ П5.3. Решение системы линейных уравнений методом отражения
§ П5.4. Решение системы линейных уравнений методом простых итераций
§ П5.5. Решение системы линейных уравнений методом Зейделя
§ П5.6. Решение системы линейных уравнений с переопределенной матрицей
§ П5.7. Приближенное вычисление нормального решения системы линейных уравнений с вырожденной матрицей
§ П5.8. Решение системы нелинейных уравнений методом простых итераций
§ П5.9. Вычисление спектра реакции нелинейной системы с аналитически заданной передаточной характеристикой на гармоническое воздействие
§ П5.10. Регрессия для 16 видов парных зависимостей у (х)
§ П5.11. Сплайн-аппроксимация, интерполяция и экстраполяция
§ П5.12. Пакет программ с матричными операторами
§ П5.13. Приближение функций по Чебышеву
Список литературы
Предметный указатель

ПРЕДИСЛОВИЕ

Прогресс в экономике, промышленности, науке и технике, в сфере образования сейчас во многом зависит от массового внедрения вычислительной техники. Не случайно задача повышения «компьютерной грамотности» населения стала государственной и политической задачей. Ее решение возможно благодаря интенсивному развитию нового поколения вычислительных средств - микроЭВМ индивидуального пользования или персональных ЭВМ (ПЭВМ).

Уже сейчас у нас в стране в пользовании находятся многие десятки тысяч таких ЭВМ - от настольных отечественных вычислительных микросистем индивидуального пользования (на базе микроЭВМ Электроника-60, Электроника-ДЗ-28, Электроника-ТЗ-59, Искра-226 и др.) и диалоговых вычислительных комплексов (ДВК-1, ДВК-2, ДВК-3) до зарубежных карманных компьютеров (Pocket Computers FX-702P, PC-1211, РС-1500 и др.). Осваивается производство дешевых и массовых домашних компьютеров (Home Computers) типа Агат, Элек-троника-БК-0010 и др.

Однако пока даже существующий парк таких ЭВМ используется недостаточно эффективно. Главная причина этого в том, что пользователями ПЭВМ являются в основном непрофессионалы в области вычислительной техники и вычислительной математики. Они слабо знакомы с эксплуатацией ЭВМ, языками и основами их программирования, разнообразными численными методами. Литературы, где все эти вопросы, с учетом специфики персонального использования ПЭВМ, рассматривались бы одновременно, пока практически нет. Многие ПЭВМ поставляются пользователям с весьма краткими (и рассчитанными на профессионалов) описаниями, часто без библиотек прикладных программ. В результате ПЭВМ нередко превращается в «черный ящик» на столе пользователя, таинственные возможности которого остаются нераскрытыми.

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

По построению справочник похож на ранее изданную книгу автора , посвященную расчетам на программируемых микрокалькуляторах (ПМК). Более того, сохранена значительная часть контрольных примеров . Это, по мнению автора, облегчит массовой категории пользователей ПМК освоение новой, гораздо более мощной вычислительной техники - ПЭВМ.

В справочнике кратко описаны основные типы отечественных и зарубежных ПЭВМ, их периферийное оборудование и основной язык программирования - бейсик (BASIC) .Рассмотрен ряд типовых версий бейсика, от простых до расширенных, содержащих команды обработки символьных переменных, косвенной адресации и построения графиков. Даны основы программирования на бейсике и перевода программ с одной версии бейсика на другую.

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

Справочник ориентирован на научно-технических работников, инженеров, техников и студентов вузов и техникумов. Поскольку подобное справочное руководство подготовлено впервые, автор отдает себе отчет в том, что книга не лишена недостатков, и с благодарностью примет советы и замечания по ее содержанию. Автор выражает глубокую благодарность рецензенту доктору технических наук, профессору С. В. Черемных, кандидату технических наук, доценту Т. А. Самойловой, Т. А. Калаевой и всем коллегам, оказавшим помощь автору в подготовке программ и рукописи. Пожелания по книге следует направлять по адресу: 117071 Москва В-71, Ленинский просп., 15. Главная редакция физико-математической литера­туры издательства «Наука».

В. П. Дьяконов

Скачать книгу Дьяконов В. П. Справочник по алгоритмам и программам на языке Бейсик для персональных ЭВМ. Издательство «Наука», Москва, 1989