ISBN 966-7343-29-5 К.305

УДК 531.0
ББК 22.311
  К.305

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

   Вы можете  найти на этой странице (программа отметит желтым цветом)
   Вы можете посмотреть  список книг по высшей математике с сортировкой по алфавиту.
   Вы можете посмотреть  список книг по высшей физике с сортировкой по алфавиту.

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

   Уважаемые дамы и господа !! Для того, чтобы без "глюков" скачать файлы электронных публикаций, нажмите на подчеркнутую ссылку с файлом ПРАВОЙ кнопкой мыши, выберите команду "Save target as ..." ("Сохранить объект как ...") и сохраните файл электронной публикации на локальный компьютер. Электронные публикации обычно представлены в форматах Adobe PDF и DJVU.

Глава 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 г.

 



 

 

Наши ссылки на веб-страницы, можно скопировать html-код ссылки


Книги по математике и физике, программы HTML, компьютерные технологии

Скачать книги - математика, бесплатно книги по высшей математике и физике по Интернет

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

 

   Вы можете использовать скачанные с веб-сайта книги и другие материалы только для личного ознакомления. Авторское право авторов книг и любых электронных приложений к ним (в том числе фото, видео, рукописи, архивы и прочее) не подлежит патентованию и подобным "искусственным" дополнительным мерам защиты авторского права - не патентуют рукописи, фотографии, видеоматериалы, формулы, графики, сводные таблицы, тексты монографий, черновики и оригинальные издания вне зависимости от того, находятся ли они в частных или государственных архивах любой страны. Вне зависимости от того, есть ли у книги или рукописи и автора какие-либо коды или нет, подписаны они или нет, известен автор или нет, является он(а) гражданином Украины или иностранцем - запрещено явным образом присваивать чужое авторское право и ставить чужие ФИО в чужих работах и трудах (в случае неуказанного, неустановленного или сомнительного авторства наиболее предпочтительно использовать анонимность - это корректно, этично и непротивозаконно, так как в этом случае истинные владельцы будут поданы в розыск и объективно установленны в своих правах независимой комиссией).

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

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

   Любое авторское право (особенно научное и творческое) никогда не патентуется, не отчуждается ни при каких обстоятельствах, не продается и не покупается и является неотъемлимым от его создателя при любых обстоятельствах - патентуются только уникальные инженерные и программные разработки, авторские алгоритмы, изобретения и подобные материалы, содержащие более 60% объективно признанных независимой государственной экспертной комиссией авторских инноваций. Незаконным является присвоение себе чужих архивов, черновиков, заметок, аудио, фото и видеоматериалов (даже если вы не знаете их автора или же непосредственно знакомы с создателем и правообладателем, это ничего не решает). Научное и творческое авторское право не отчуждается от автора и создателя и никогда не делегируется третьим лицам (особенно без профессии и неконтрафактных документов) - оно является наиболее строгим авторским правом, неотделимым от своего создателя, и не подлежит передаче, купле и продаже ни при каких обстоятельствах. Оно только может быть передано в возмездное или безвозмездное пользование БЕЗ ПРАВА НА ОТЧУЖДЕНИЕ. Главной особенностью научного и творческого авторского права является его обязательная частичная передача в безвозмездное пользование широким слоям заинтересованного населения - на этом сайте все научные книги бесплаты и свободны для скачивания без паролей, кодов и ограничений (я как владелец этого сайта и интернет-хостинг-провайдеры не несем ответственность за деятельность третьих лиц, возможные сбои и технические нарушения интернет-связи при пользовании сайтами по вине третьих лиц). Никаких искусственных препятствий, ограничений скорости, других "негативов" и препятствий мы не устанавливаем.

   Государство Украина имеет достаточную базу для обеспечения научных работ и научных исследований по всем законным направлениям научной деятельности. C 2010 г. в Украине любая наука и научные исследования являются объектами строгой государственной монополии и требуют наличия не только документально признанной в Украине профессии, но и высшего государственного образования, официально признанного в Украине.