AMP версия сайта

Электронная библиотека

  • Современные работы
  • Бесплатно скачать книги
  • Высшая алгебра, геометрия
  • Математический анализ, ТФ
  • Дифференциальные уравнения
  • Численные методы алгоритмы
  • Математическая физика
  • Теория чисел и множеств
  • Специальные темы, книги
  • Общая высшая физика
  • Другие популярные издания
  • Программисту веб-дизайнеру

  • Документация - HTML, XML
  • Статьи пресс-релизы обзоры
  • Веб-дизайнеру - JavaScript
  • Другие материалы

  • Авторское право - помощь
  • Полиграфия, печать цвет
  • Библиография, статьи
  • Бесплатная электронная библиотека. Скачать книги DJVU, PDF бесплатно
    Н. Вирт, Алгоритмы + структуры данных = программы

    Бесплатно скачать книгу, объем 4.70 Мб, формат .djvu
    Фрагмент книги, касающийся программирования и алгоритмизации, 1991 год

    Глава 1. Фундаментальные структуры данных
    1.1. Введение
    1.2. Концепция типа для данных
    1.3. Простые типы данных
    1.4. Стандартные простые типы
    1.5. Ограниченные тисы
    1.6. Массивы
    1.7. Записи
    1.8. Записи с вариантами
    1.9. Множество
    1.10. Представление массивов, записей и множеств
    1.11. Последовательный файл

    Глава 2. Сортировка
    2.1. Введение
    2.2. Сортировка массивов
    2.3. Сортировка последовательных файлов

    Глава 3. Рекурсивные алгоритмы
    3.1. Введение
    3.2. Когда не нужно использовать рекурсию
    3.3. Два примера рекурсивных программ
    3.4. Алгоритмы с возвратом
    3.5. Задача о восьми ферзях
    3.6. Задача об устойчивых браках
    3.7. Задача оптимального выбора

    Краткая аннотация книги

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

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

    На словах все признают, что в основе программирования лежит творческий акт. У учеников нужно развивать способность творчески мыслить. И здесь огромна роль учителя, не столько рассказывающего о чем-то, сколько показывающего, как он делает то-то и то-то. Заметим, что в основе обучения и действий учителя лежит тот же творческий акт. Творчество не подвластно канонам, методикам и, тем более, технологиям. Представьте себе учебник по технологии физики или еще лучше по технологии математики, по технологии соответствующего мышления. Блестящие книги Пойи лишь подтверждают правило, что творчеству учат Учителя. При обучении "творческим специальностям" ученики не столько слушают, сколько смотрят, что и как делает учитель. Они наблюдают весь процесс его творчества.

    Но что же делать, если нужно обучать не десятки или сотни людей, а многие тысячи? В этом случае надо полагаться на "школы", во главе которых стоят такие крупные Учителя. В школах процесс обучения и воспитания опять-таки основан на показе, но носит более сложный характер и захватывает значительно большее количество учеников. В программировании таких школ несколько. Одна из зарубежных школ находится в Цюрихе, во главе ее стоит Н. Вирт. Именно отсюда пришел элегантный Паскаль, завоевавший почти весь мир, и отсюда же появляется книга, перевод которой читатель держит в руках.

    В ней обобщен авторский опыт многолетнего обучения программированию. Искусство автора проявилось в том, что в своей книге он подчеркивает основополагающие принципы программирования, а не конкретные особенности того или иного модного языка программирования. Благодаря этому его книге суждена долгая жизнь. Здесь почти нет никаких рецептов, рекомендаций, методик. Это набор примеров программ, про которые автор говорит: "Смотрите, как и почему я это делаю".

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

    В последние годы программирование для вычислительных машин стало не только средством, владение которым оказывается решающим для успешной работы во многих прикладных областях, а также и предметом научного изучения. Из ремесла программирование превратилось в академическую дисциплину. Первые крупные шаги в этом направлении были сделаны в работах Э. Дейкстры и К. Хоора. "Заметки по структурному программированию" Дейкстры определили новый взгляд на программирование как на предмет научного изучения и поле для интеллектуальной деятельности; этот подход получил название "революции" в программировании. В статье "Аксиоматическая основа программирования для вычислительных машин". Хоор продемонстрировал, что программы поддаются точному анализу, основанному на математических рассуждениях. В этих работах убедительно показано, что можно избежать многих ошибок программирования, если программисты со знанием дела будут применять те методы и приемы, которые они ранее использовали интуитивно и часто неосознанно. Основное внимание в них уделено построению и анализу программ, или, более конкретно, структуре алгоритмов, представленных текстами программ. Причем совершенно ясно, что систематический и научный подход к построению программ важен в первую очередь в случае больших программ со сложными данными. Таким образом, методы программирования включают также и все варианты структурирования данных. Программы представляют собой, в конечном счете конкретные формулировки абстрактных алгоритмов, основанные на конкретных представлениях и структурах данных. Важный вклад в упорядочение широкого разнообразия терминов и концепций, относящихся к структурам данных, был сделан Хоором в статье "О структурной организации данных". Стало ясно, что решения о структурировании данных нельзя принимать без знания алгоритмов, применяемых к этим данным, и наоборот, структура и выбор алгоритмов существенным образом зависят от структуры данных. Говоря короче, строение программ и структуры данных неразрывно связаны.

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

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

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

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

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

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

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

    Программирование - это искусство конструирования. Как можно научить конструкторской, изобретательской деятельности? Есть такой метод: выделить простейшие строительные блоки из многих уже существующих программ и дать их систематическое описание. Но программирование представляет собой обширную и разнообразную деятельность, часто требующую сложной умственной работы. Ошибочно считать, что ее можно свести к использованию готовых рецептов. В начестве метода обучения нам остается тщательный выбор и рассмотрение характерных примеров. Конечно, не следует считать, что изучение примеров всем одинаково полезно. При этом подходе многое зависит от сообразительности и интуиции обучающегося. Это особенно верно для относительно сложных и длинных примеров программ. Они не случайно включены в эту книгу. Длинные программы обычно часто встречаются на практике, и они лучше всего подходят для выявления того неуловимого, но важного свойства, которое называют стилем или дисциплиной. Кроме того, они служат упражнением в искусстве читать программы, которым часто пренебрегают по сравнению с искусством писать программы.

    Главным образом по этой причине в качестве примеров берутся целиком большие программы. Читателю показывается, как постепенно создается программа, ему даются различные "моментальные снимки" ее развития, причем эти разработки демонстрируют метод поэтапного уточнения деталей. Я считаю важным, рассматривая программы в их окончательном виде, уделять достаточно внимания деталям, поскольку именно в них кроются основные трудности в программировании. Представить алгоритмы в чистом виде и дать их математический анализ было бы интересно с чисто академической точки зрения, но было бы нечестно по отношению к программисту-практику. Поэтому я строго придерживался принципа представлять программы в их окончательном виде на том языке, на котором они могут реально выполняться в вычислительной машине.

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

    Настоящая книга представляет собой сжатое и переработанное изложение нескольких курсов программирования, прочитанных в Федеральном технологическом институте (ЕТН) в Цюрихе. Многими идеями и взглядами, изложенными в этой книге, я обязан беседам со своими сотрудниками в ЕТН. В частности, мне хотелось бы выразить благодарность м-ру Г. Сандмейеру за внимательное прочтение рукописи и мисс Хейди Тейлер за внимание и терпение при перепечатке текста.

    Наш высокочтимый г. Л. Эйлер делает нам в назидание следующее заявление. Он откровенно признает:

    III... что, являясь королем математиков, он все же вечно будет краснеть за вызов здравому смыслу и повседневному опыту, брошенный выводом из его формулы, согласно которой тело под действием силы притяжения к центру сферы внезапно изменит направление движения к центру;

    IV... что он сделает все возможное, чтобы больше не изменять разуму, доверяясь ошибочной формуле. Он на коленях молит прощения за то, что как-то, имея в виду парадоксальный результат, он заявил: "Вычислениям следует доверять больше, чем чувствам, даже если кажется, что это противоречит действительности";

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

    Вольтер, Памфлет доктора Акакия, ноябрь 1752 г.

    Примечание. Сохраняйте книги на планшет или смартфон и скачивайте их с Вашего AMP планшета или смартфона на компьютер. Удобное скачивание книг через мобильный планшет или смартфон (в память устройства) и на Ваш компьютер через AMP интерфейс. Быстрый Интернет без излишних тэгов. Материал носит неофициальный характер и приведен для ознакомления. Прямые ссылки на файлы книг запрещены.

    c 15/06/2015 страница посещена

    AMP версия сайта
    Мобильная версия

    Сайт для компьютера
    http://www.mat.net.ua