Основы программирования на языке TURBOPASCAL. Учебное пособие. Б. А. Крымов, А. О. Мовшин, С. В. Кулакова. Воронеж: ВГТА. 2000.
Литература
1. Информатика: Базовый курс / С.В. Сименович и др. – СПб.: Питер. 2001. – 640 с.
2. Информатика: Учебник. Под ред. проф. Н.В. Макаровой. – М.: Финансы и статистика. 1999 – 768 с.
3. Немнюгин С. Pascal: Учебный курс. – СПб.: Питер. 1999.
4. Марченко, А. И. Программирование в среде Turbo Pascal 7.0 [Текст] / А. И. Марченко, Л. А. Марченко. – Киев : Корона-принт, 2007. – 464 с.
5. Попов, В. Б. Turbo Pascal для школьников. [Текст] / В.Б. Попов. – М. : Финансы и статистика, 2007. – 528 с.
6. Фаронов, В. В. Turbo Pascal 7.0. Начальный курс. [Текст] / В. В. Фаронов. – М. : КноРус, 2007. – 575 с.
7. Фаронов, В. В. Turbo Pascal 7.0. Практика программирования. [Текст] / В. В. Фаронов. – М. : КноРус, 2007. – 415 с.
8. Информационные технологии. Учебное пособие. Н. Д. Писаренко, О. Ю. Никифорова, О. А. Лукинова. Воронеж: ВГТА. 2004.
9. Лекции по информатике. Электронный документ “Информатика”.
Основы программирования на языке TURBOPASCAL. Учебное пособие. Б. А. Крымов, А. О. Мовшин, С. В. Кулакова. Воронеж: ВГТА. 2000.
Тема 1.Информатика и информационные процессы
Основные понятия информатики
Во второй половине 20 века человечество вступило в новый этап своего развития. В этот период начался переход от индустриального общества к информационному. Процесс, обеспечивающий этот переход, получил название информатизации.
Информатизация – это процесс создания и всеобщего применения информационных средств и технологий, обеспечивающих достижение и поддержание такого уровня информированности всех членов общества, какой необходим и достаточен для кардинального улучшения качества труда и условий жизни в обществе. При этом информация становится важнейшим стратегическим ресурсом общества и занимает ключевое место в экономике, образовании и культуре.
Научным фундаментом процесса информатизации общества является учебный предмет информатика – техническая научная дисциплина о процессах сбора, хранения и переработки информации. Рассмотрим основные понятия информатики.
Сигналы и данные. Мы живем в материальном мире, состоящем из физических тел или полей, которые постоянно изменяются и взаимодействуют друг с другом. Эти взаимодействия сопровождаются обменом веществом и энергией. Каждый такой обмен имеет определённые внешние проявления, которые называются сигналом. Выработка сигналов сопровождаются появлением следов взаимодействий, в результате чего возникают определенные изменения свойств взаимодействующих объектов. Это явление называется регистрацией сигналов. Так образуются данные – зарегистрированные в каком-нибудь виде сигналы.
Информация и её носитель. Поскольку каждое изменение свойств определяется какой-нибудь особенностью события, в результате которого был выработан сигнал, то каждое данное несет определенные сведения, позволяющие что-то узнать об этих событиях. Так, анализ предметов, найденных в результате археологических раскопок, позволяет с достаточной достоверностью воссоздать особенности быта людей живших когда-то на этом месте; изучив следы на земле, опытный охотник-следопыт сможет подробно рассказать, что за животное здесь прошло, было ли оно спокойно или его потревожили, здоровое оно или больное и многое другое. Подобные сведения, полученные в результате переработки данных, называются информацией.
Иными словами, информация является некоторым связующим звеном между материальными объектами и нематериальным человеческим сознанием, благодаря которому люди получают возможность узнавать окружающий мир.
Следует подчеркнуть, что информация – категория нематериальная, и для своего существования и распространения в материальном мире нуждается в какой-либо материальной основе. Материальный объект или среда, которые служат для регистрации или передачи данных называют материальными носителями информации. Носителем информации могут быть весьма разнообразные предметы, в том числе и человеческая память. Достаточно длительное время в истории человечества универсальным носителем информации являлась бумага. В настоящее время широко используются электронные и оптические носители.
Как было сказано, благодаря материальному носителю информацию можно хранить и передавать на расстояние. При этом хранение информации связано с некоторой характеристикой носителя, которая не меняется с течением времени. Например, намагниченные области поверхности диска или написанные на бумаге буквы могут сохраняться в неизменном виде произвольное длительное время. Передача же информации – наоборот, связана с характеристикой, которая меняется с течением времени. Например, это может быть изменение амплитуды и частоты звуковых колебаний (так информация передаётся посредством человеческой речи) или изменение напряжения и частоты колебаний переменного тока в электрических проводах (так информация передается по телефону или телеграфу) и т.д. Последовательность сигналов, порождённая изменением во времени состояния носителя информации называется сообщением.
Алгоритм и знание. Однако, имея данные или сообщение, не всегда можно извлечь из них информацию. Например, прослушав передачу радиостанции на незнакомом языке, мы получаем данные в результате прослушивания, но не получаем информацию, т.к. никаких сведений мы из передачи не извлекли. Это произошло потому, что нам не известен язык, на котором велась передача. Иными словами, мы не знаем метода преобразования полученных данных в известные нам понятия. Следовательно, информация – это продукт взаимодействия данных и подходящего (адекватного) к ним метода переработки. В информатике такие методы называются алгоритмами.
Информация, полученная в результате переработки данных, воспринимается людьми, для которых эта информация предназначается – пользователями информации. В результате восприятия информации пользователи могут повышать свою осведомленность о чем-либо, т.е. они вырабатывают знания. Знание – такая форма развития осведомленности о каком-нибудь объекте или явлении, которую можно употребить с пользой для себя и окружающих. В результате получения новых знаний люди могут применить их на практике и разработать более совершенные средства воздействия на природу, изменяя ее для улучшения условий своей жизни.
Информационные процессы (кратко). Перечисленные понятия, их взаимосвязь и происходящие с ними изменения можно изобразить в виде схемы, приведенной на рис. 1.1.
В тех случаях, когда некоторое качество, характеризующее объект меняется с течением времени, используется термин «процесс». На схеме отражены основные изменения, происходящие с информацией, следовательно, эти изменения можно назвать информационными процессами. Какие же изменения могут происходить с нематериальной информацией? Очевидно, меняться может либо её содержание, либо материальная оболочка, посредством которой информация представлена. Поэтому различают два типа информационных процессов:
- изменение сообщений и данных с сохранением содержащейся в них информации;
- изменение сообщений и данных с преобразованием содержащейся в них информации.
К процессам первого типа относится передача информации в пространстве или времени (хранение информации). К процессам второго типа относятся создание информации, уничтожение информации и обработка с появлением новой информации или знания.
На схеме выделена область, определяющая место информатики в этом круговороте и составляющая ее предмет – процессы сбора, хранения и обработки данных. Часто вместе с перечисленными процессами рассматривают процесс передачи данных. Рассмотрим эти процессы подробнее.
Процесс сбора данных
Как было сказано в п. 1.1, каждое изменение свойств любого объекта имеет какую-нибудь особенность, в результате которой вырабатывается определенный сигнал. Съём и регистрация этих сигналов представляет собой процесс сбора данных. Он производится либо с помощью датчиков, встроенных в исследуемый объект, либо путем считывания данных с документов.
В общем случае сигналы, поступающие от объекта можно разделить на статические и динамические. Статические сигналы отражают устойчивое состояние объекта, не меняющееся во времени и обычно фиксируются в форме документов. Динамические сигналы меняются во времени и обычно представляются в форме электрических сигналов на выходе датчиков и контрольно-измерительных приборов.
По характеру изменения сигналы делятся на непрерывные и дискретные.
|
Непрерывные математически отображаются непрерывными функциями времени. Физически они представляют собой непрерывные значения тока или напряжения (см. рис. 1.2 – красная линия). Дискретные сигналы определяются конечным множеством значений тока или напряжения. Каждое из возможных значений дискретного сигнала можно обозначить каким-нибудь кодом и в таком виде хранить и использовать его в компьютере.
Схема процесса сбора данных при использовании датчика представлена на рис. 1.3. С объекта датчиком снимается непрерывный сигнал, который в преобразователе превращается в дискретный, а в шифраторе дискретный сигнал кодируется, например, в виде двоичного кода – последовательности из 0 и 1. Физически код представляет собой последовательность электрических импульсов, передаваемых по проводам. Наличие тока означает 1, отсутствие – 0. Полученные наборы данных собираются в накопителе – временное хранилище данных, из которого они выводятся по мере необходимости.
Существует несколько способов превращения непрерывного сигнала в дискретный, наиболее распространенные – квантование по уровню или по времени. В обоих случаях график исходного сигнала в виде плавной непрерывной кривой заменяется ступенчатой линией.
В первом способе весь диапазон значений непрерывного сигнала разбивается на несколько участков. Если величина сигнала попадает в какой-то i-й участок, то значение квантованного сигнала принимается равным граничному или среднему значению этого участка.
При втором способе на части разбивается временной интервал изменения сигнала. Значением квантованного сигнала на каждом j-м участке считается величина непрерывного сигнала в начале этого участка или в его середине (см. рис. 1.2.).
При съёме данных с документа преобразователь уже не нужен, т.к. исходный сигнал является дискретным, а роль накопителя выполняет непосредственно компьютер, в котором данные будут храниться. Схема процесса – на рис. 1.4.
Процесс хранения данных.
Напомним, что данными называются зарегистрированные в каком-нибудь виде сигналы. В данных содержатся сведения, характеризующие какой-либо объект или явление. Большинство данных не используется непосредственно, а подвергается обработке. Понятно, что эта обработка не может быть осуществлена немедленно после получения данных, а должно пройти определённое время, пока данных не накопится достаточное количество или в обработке каких-то конкретных данных не возникнет необходимость. Весь период времени между поступлением данных и началом их использования данные подвергаются хранению. Хранение данных – передача информации во времени.
 | |||
| |||
Свойства данных. Для понимания особенностей процесса хранения рассмотрим основные свойства, которыми обладают данные.
1. Важнейшим из их свойств является тип данных. Тип данных определяет:
- множество значений, которые может принимать данное;
- форму представления данных в ЭВМ;
- совокупность операций, допустимых над данными;
- правила доступа к ним (т.е. извлечения с места хранения).
Допустимый набор типов данных и их особенности определяются программной системой, имеющейся в компьютере и работающей с данными. Ясно, что чем более широким и гибким оказывается набор используемых типов данных, тем больше возможностей предоставляется пользователю в решении задач представления, хранения и применения данных.
2. Следующим признаком является деление данных на простые (одиночные) и сложные (структурированные). Данные простого типа содержит только одну компоненту – одно число или один символ. Данные сложных типов могут содержать несколько компонент простого типа. Таким образом, простые данные являются теми «кирпичиками», путём объединения которых строятся сложные данные.
3. В зависимости от того, на каком этапе обработки данные используются, они подразделяются на исходные (входные), промежуточные и выходные. К исходным относятся данные, необходимые для исполнения программы и вводимые в неё до или в процессе работы. Эти данные могут быть предварительно записаны на некотором носителе и вводиться с него, а также могут поступать по линии связи от каких-то датчиков или с других компьютеров, а могут вводиться непосредственно пользователем программы с помощью устройства ввода (клавиатуры).
Промежуточные данные формируются в ходе исполнения программы и, чаще всего, пользователю недоступны. Они не отображаются на устройствах вывода, но существуют во внутренней или внешней памяти компьютера.
Выходные данные являются конечным результатом работы программы – ради них и производится обработка входных данных. Выходные данные, предназначенные для человека, представляются в требуемом для него формате (тексты, рисунки, звуки и т.д.).
Способы представления данных в компьютере.Для представления значений простых данных во внутренней памяти компьютера используют так называемое машинное слово – совокупность двоичных элементов, обрабатываемых как единое целое в устройствах и памяти компьютера. С технической точки зрения машинное слово объединяет запоминающие элементы, служащие для записи 0 или 1 (одного двоичного разряда) в единую ячейку памяти. Первый микропроцессор Intel-4004, созданный в конце 1970 года фирмой Intel работал с 4-разрядными ячейками. В настоящее время наибольшее распространение получили компьютеры с 32-разрядными ячейками (см. рис. 1.5), однако существуют компьютеры и иной разрядности. Доступ к машинному слову в операциях записи и считывания осуществляется по номеру ячейки памяти, который называется адресом ячейки.
| № разряда | 31-й разряд | 30-й разряд | 29-й разряд | 28-й разряд | … | … | … | 2-й разряд | 1-й разряд | 0-й разряд |
| Содержимое | … | … | … |
Рис. 1.5. 32-разрядное машинное слово
Для представления символов (литерных данных) машинное слово делится на группы по 8 разрядов, в каждую из которых записывается двоичный код символа. Ясно, что в 32-разрядном машинном слове можно записать 4 символа. В представлении целых чисел используется уже все 32 разряда, а для представления одного вещественного (дробного) числа, например, в языке PASCAL используются целых две ячейки.
Пусть в задаче требуется обработать большое количество однотипных данных. Это можно сделать различными способами.
Например, первый способ: запрашивать данные по одному и обрабатывать. Т.е. последовательность действий такая:
1. Ввести значение переменной Х
2. Обработать переменную Х
3. Повторить шаг 1.
Недостаток: на текущий момент доступно только одно текущее значение, для повторной обработки придется запросить все данные повторно.
Второй способ: объявить столько переменных, сколько данных понадобится:
1. Ввести значения переменных X, Y, A, B,…..
2. Обработать переменные Х, Y, A, B,…..
Недостаток: обрабатывать все данные надо одинаково, и программа будет содержать повторяющийся набор однотипных действий, отличающихся только именем переменной, хранящей очередное значение.
Поэтому необходимы структуры, позволяющие хранить однотипные данные и одинаково их обрабатывать. Именно по этой причине в современных компьютерах используются сложные (структурированные) данные. Наиболее простой структурой является массив. Массив – это структура данных одинакового типа, упорядоченных по номерам. Для его хранения во внутренней памяти компьютера отводится непрерывная область, содержащая столько ячеек, сколько необходимо для размещения всех элементов массива.
Другой часто используемой структурой данных является логическая запись. Логическая запись – разнородная совокупность простых данных, имеющая смысловую завершённость. Иными словами, логическая запись объединяет не любые разрозненные по своему содержанию (смыслу) данные, а те, которые характеризуют некий объект. Пример записи – строка списка студентов:
| Фамилия | Год рождения | Год поступления в ВУЗ | Курс | Номер зачётной книжки |
Рис. 1.6. Пример логической записи
Простые данные, совокупность которых образует запись, называются полями записи. Данные в виде совокупности логических записей могут храниться во внутренней памяти компьютера, но чаще они используются для представления данных во внешней памяти. В этом случае они объединены в файл. Файл – совокупность однородных записей, хранящихся во внешней памяти компьютера. Файлы могут объединяться в каталоги. В операционных системах семейства Windows каталоги называются папками.
Основные фазы процесса хранения информации:
- организация информационных массивов;
- запись данных на носитель;
- реализация алгоритмов ввода, поиска, обновления и вывода информации.
Начиная со средины 60-х годов 20 века, для хранения информации все шире используют так называемые базы данных – централизованные хранилища информации, доступные многим пользователям. Они предоставляют широкий спектр операций по хранению, поиску и манипулированию данными.
При долговременном хранении больших объемов данных используют так называемое сжатие или архивацию данных – запись данных в таком формате, при котором они занимают меньше места, чем при обычном формате хранения.
Устройства хранения информации. Устройства, выполняющие операции, связанные с сохранением и считывания данных на материальном носителе называются внешними запоминающими устройствами (ВЗУ) или устройствами внешней памяти. Любое ВЗУ реализует один из двух возможных принципов размещения информации – последовательный или прямой доступ. В первом случае записи размещаются одна за другой, т.е. последовательно. Считывание записей также производится последовательно, и для того, чтобы отыскать нужную запись, требуется просмотреть все предыдущие. В настоящее время в качестве устройств последовательного доступа используются стримеры.
<TBODY>Стример (англ. tape streamer) — устройство для резервного копирования больших объёмов информации. В качестве носителя здесь применяются кассеты с магнитной лентой. Стримеры позволяют записать на небольшую кассету с магнитной лентой огромное количество информации. Встроенные в стример средства аппаратного сжатия позволяют автоматически уплотнять информацию перед её записью и восстанавливать после считывания, что увеличивает объём сохраняемой информации. Недостатком стримеров является их сравнительно низкая скорость записи, поиска и считывания информации.</TBODY>
Для реализации прямого доступа на носителе должны быть пронумерованы области записи информации, такие области называются блоками. Обратиться к данному, записанному в определённом блоке, можно по номеру блока. Операция разбиения поверхности носителя на блоки называется форматированием, она обязательно делается перед использованием носителя.
К устройствам прямого доступа относятся магнитные диски и компакт-диски.
Рис. 1.7. Винчестерский накопитель со снятой крышкой корпуса
Рис. 1.8. Поверхность магнитного диска
Накопитель на жёстких магнитных дисках (англ. HDD — Hard Disk Drive) или винчестер — это наиболее массовое запоминающее устройство большой ёмкости, в котором носителями информации являются круглые алюминиевые пластины – платтеры, обе поверхности которых покрыты слоем магнитного материала. Используется для постоянного хранения информации — программ и данных. Информация записывается по концентрическим дорожкам (трекам), которые делятся на секторы. Сектор хранит минимальную порцию информации, которая может быть записана на диск или считана. Ёмкость сектора постоянна и составляет 512 байтов.
Накопитель на компакт-дисках (CD-ROM)состоит из прозрачной полимерной основы диаметром 12 см и толщиной 1,2 мм. Одна сторона покрыта тонким алюминиевым слоем, защищенным от повреждений слоем лака. Двоичная информация представляется последовательным чередованием углублений (pits — ямки) и основного слоя (land — земля). Участки CD, на которых записаны символы "0" и "1", отличаются коэффициентом отражения лазерного луча, посылаемого накопителем CD-ROM. Эти отличия улавливаются фотоэлементом, и общий сигнал преобразуется в соответствующую последовательность нулей и единиц.
Достоинства CD-ROM:
· При малых физических размерах CD-ROM обладают высокой информационной ёмкостью, что позволяет использовать их в справочных системах и в учебных комплексах с богатым иллюстративным материалом
· Считывание информации с CD происходит с высокой скоростью, сравнимой со скоростью работы винчестера;
· CD просты и удобны в работе, практически не изнашиваются;
· CD не могут быть поражены вирусами;
· С CD-ROM невозможно случайно стереть информацию;
· Стоимость хранения данных (в расчете на 1 Мбайт) низкая.
Процесс передачи данных
Необходимость в передаче данных возникает, когда объекты, между которыми происходит обмен информацией, территориально удалены друг от друга. В современных информационных системах обмен происходит с использованием коммуникационной сети. На рис. 1.9 изображена структура (строение) современного канала связи, используемого в процессе передачи данных.
Основные проблемы процесса передачи данных:
1) согласование физических характеристик сигнала (частота, амплитуда) с физическими характеристиками непрерывного канала связи для обеспечения минимального затухания сигнала при его передаче на большие расстояния;
2) сведение к минимуму потери информации при передаче по дискретному каналу, на который воздействуют помехи;
3) решение задачи маршрутизации, т.е. доставление информации адресату по каналу передачи данных в максимально короткий срок.
Поясним суть этих проблем и укажем методы их решения.
1). Физической средой передачи данных является канал связи, в котором элементы данных передаются в виде электрических сигналов. Он называется непрерывным каналом, т.к. проходящие в нем сигналы описываются непрерывными функциями времени. Большинство непрерывных каналов не могут передавать сигналы без их предварительного преобразования. Для такого преобразования в структуре канала предусмотрено специальное преобразующее устройство. Для телефонных каналов связи это устройство называется модем (от слов «модулятор» и «демодулятор»). С помощью модулятора происходит воздействие на входной сигнал, благодаря чему он смещается в диапазон таких частот, для которых наблюдается наименьшее затухание амплитуды сигнала в выбранном непрерывном канале, поэтому модулированный сигнал проходит по каналу с минимальной потерей мощности. Демодулятор осуществляет обратное преобразование, т.е. переход от модулированного сигнала к обычному.
2). Для того, чтобы сообщение можно было передать по каналу связи, его надо закодировать, т.е. преобразовать в совокупность таких сигналов, которые удобно передавать на расстояние. Модулятор, непрерывный канал и демодулятор (на другом конце канала) образуют дискретный канал, на вход которого подаются сообщения в виде набора закодированных сигналов, а на выходе эти сообщения считываются и декодируются. Кодирование и декодирование производится шифратором и дешифратором, каждый из которых снабжен устройством защиты от ошибок, которое производит эти преобразования так, чтобы свести к минимуму искажение информации от помех, воздействующих на канал. Достигается эта минимизация за счет применения специальных помехоустойчивых кодов. В них в основное сообщение встраиваются специальные контрольные символы. Если сообщение будет содержать ошибку, то ее можно будет распознать и исправить. Подобной помехозащищенностью обладают, в частности, и естественные языки. В них каждое слово содержит больше информации, чем необходимо передать. Благодаря подобной избыточности информации можно восстанавливать пропущенные буквы в кроссвордах или старинных рукописях.
3). Необходимость решения задачи маршрутизации возникает из-за того, что каналы связи имеют ограниченную пропускную способность, т.е. существует некоторый предел количества информации, которое по ним можно передать. С другой стороны, коммуникационные сети проектируются так, что между двумя фиксированными узлами можно проложить несколько возможных маршрутов. В процессе функционирования сети загруженность ее отдельных участков постоянно меняется. Поэтому при передаче каждого сообщения производится поиск такого пути (маршрута) прохождения сигнала, по которому можно передать сообщение в кратчайший срок и без потери информации.
Процесс обработки данных
Обработка – процесс преобразования информации к такому виду, из которого можно получить знание.
Преобразования, производимые в процессах сбора, передачи и хранения (кодирование, сжатие и т.д.) – это перезапись одной и той же информации, представление ее в разных формах. Ничего нового из этой информации не появляется. В процессе же обработки из имеющейся информации появляется нечто новое.
Пример 1.1. Лошадь и мул несли по несколько мешков с мукой. Лошадь жаловалась на тяжёлую поклажу. «Что ты жалуешься? – отвечал ей мул, – Ведь если я возьму у тебя один мешок, моя ноша станет вдвое тяжелее твоей. А вот если бы ты сняла с моей спины один мешок, твоя поклажа стала бы одинакова с моей». Сколько же мешков несла лошадь, и сколько нёс мул?
Для того чтобы ответить на этот вопрос, надо решить систему уравнений:
(1.1)
Решить ее, т.е. обработать данную информацию, можно, например, методом Крамера.
Шаг 1. Вычислим определитель матрицы системы D = 2×(1) – (–1)×(–1) = 1. Он не равен 0, значит, система имеет решение.
Шаг 2. Вычислим определители для каждого неизвестного: DЛ = 3 + 2 = 5; DМ = 4 + 3 = 7.
Шаг 3. Вычисляем каждое неизвестное: 
; 
.
Ответ: Мул нёс 7 мешков, а лошадь – 5.
Иными словами, процесс обработки информации состоит из отдельных шагов. В результате выполнения каждого шага возникает порция новой информации.
Как было сказано в п. 1.1, описание пошагового процесса обработки информации называется алгоритмом.
Более подробно об алгоритмах поговорим в следующей теме.
Тема 2.Алгоритмизация и программирование
2.1. Алгоритм и его свойства
Что такое алгоритм.<TBODY>Алгоритм – точная и понятная инструкция исполнителю совершить некую последовательность действий, направленных на решение поставленной задачи. </TBODY>
Название "алгоритм" произошло от латинской формы имени среднеазиатского математика аль-Хорезми – Algorithmi, написавшего популярную в эпоху средневековья книгу о правилах выполнения арифметических действий, т.е. об алгоритмах вычисления произведения, частного и т.д.
<TBODY>Исполнитель алгоритма – это некоторый абстрактный (воображаемый) или реальный объект, способный выполнить действия, предписываемые алгоритмом. В информатике универсальным исполнителем алгоритмов является компьютер.
Основные свойства алгоритма. Слова “инструкция” или “предписание” близки по смыслу слову “алгоритм”, однако они не тождественны ему. Дело в том, что не всякая инструкция может быть названа алгоритмом, поскольку он должен обладать рядом обязательных свойств, которыми произвольное предписание обладать не обязано. Перечислим эти свойства.
1) Конечность – любой алгоритм должен заканчиваться после выполнения конечного (т.е. не бесконечного) числа шагов.
Если алгоритм содержит цикл, т.е. повторяющуюся группу команд, то в алгоритме должно присутствовать некое условие, при выполнении которого следует прерывание цикла.
Например, еще древние греки знали метод приближенного извлечения квадратного корня из произвольного числа а > 0. Пусть х(0) – некоторое начальное приближение к 
. Для вычисления каждого следующего приближения построим рекуррентную формулу:
, k = 0, 1, … (2.1)
называемую алгоритмом Герона.
Вычислим с его помощью 
, взяв х(0) = 1.5. Последовательно получим х(1) = 1.4166667; х(2) = 1.4142157; х(3) = 1.4142136; х(4) = 1.4142136. Теоретически эти вычисления можно продолжать бесконечно, получая все более точный результат, поэтому формула (2.1), строго говоря, алгоритмом не является.
Для того, чтобы ее с полным правом можно было назвать алгоритмом, надо указать условие окончания вычислений. Например, можно таким условием считать совпадение определенного количества N цифр в двух последовательных значениях х(k) и х(k+1). Доказано, что в этом случае при использовании формулы (2.1) у всех последующих приближений первые N цифр будут такими же, как у х(k+1). В приведенном примере у х(3) и х(4) совпали первые N = 8 цифр. Следовательно, ответ получен с точностью 10–7, и если она нас устроит, то вычисления можно заканчивать.
2) Определенность – каждая команда алгоритма должна быть четкой, однозначной и не оставлять места для произвола.
Благодаря этому свойству выполнение алгоритма носит чисто механический характер и не требует никаких дополнительных указаний или сведений о решаемой задаче.
Например, не является алгоритмом такая инструкция: слегка подогрейте в маленькой кастрюле немного коньяку, добавьте специи по вкусу. Здесь слова “слегка”, “немного” и т.д. носят неопределенный характер, который каждый исполнитель может трактовать по-своему.
3) Эффективность – все операции, которые необходимо произвести в алгоритме, должны быть достаточно простыми, чтобы их в принципе можно было выполнить точно и за разумное время с помощью карандаша и бумаги. Например, нельзя считать простой операцией решение алгебраического уравнения 12-й степени. Поэтому, если в инструкции присутствует такая команда: найти решение уравнения х12 + 5х11 + 15х10 + 22х5 + 15258 = 0, то такая инструкция эффективной не является, а, следовательно, ее нельзя считать алгоритмом.
4) Результативность – любой алгоритм должен после своей работы выдавать какой-нибудь результат.
Возможна ситуация, что поставленная задача вообще не имеет решения. В этом случае алгоритм должен заканчиваться выдачей сообщения: “нет решения”.
5) Массовость – алгоритм решения задачи разрабатывается в общем виде, т.е. он должен быть применим для некоторого класса задач, различающихся лишь исходными данными. При этом исходные данные могут выбираться из некоторой области, которая называется областью применимости алгоритма.
2.2. Формы записи алгоритма
На практике наиболее распространены следующие формы представления алгоритмов:
· словесная – запись на естественном (“человеческом”) языке;
· графическая – изображение команд в виде графических символов;
· программная – текст на языке программирования.
Словесный способ записи алгоритмов. Это <TBODY>описание последовательных этапов (шагов) обработки данных. Алгоритм задается в произвольном изложении на естественном языке. </TBODY>
Пример 2.1. Записать алгоритм нахождения наибольшего общего делителя (НОД) двух натуральных чисел.
Предлагается следующий алгоритм – алгоритм Евклида.
1. Задать два числа.
2. Если числа равны, то взять любое из них в качестве ответа и остановиться, в противном случае продолжить выполнение алгоритма.
3. Заменить большее из чисел разностью большего и меньшего из чисел.
4. Повторить алгоритм с шага 2.
Описанный алгоритм применим к любым натуральным числам и должен приводить к решению поставленной задачи. Убедимся в этом, определив с помощью этого алгоритма наибольший общий делитель чисел 125 и 75:
1. m = 125, n = 75.
2. m > n, значит
3. Новое m = 125 – 75 = 50, n = 75. Возврат к 2.
2. n > m, значит
3. Новое n = 75 – 50 = 25, m = 50. Возврат к 2.
2. m > n, значит
3. Новое m = 50 – 25 = 25, n = 25. Возврат к 2.
2. m = n. Значит ОТВЕТ = 25.
Словесный способ не имеет широкого распространения по следующим причинам:
· описания не формализованы (нет строгих правил);
· страдают многословностью записей;
· допускают неоднозначность толкования отдельных предписаний.
Графический способ записи алгоритмов. Графический способ представления алгоритмов является более наглядным по сравнению со словесным.
| Таблица 2.1. | ||
| <TBODY>Название символа | Обозначение и пример заполнения | Пояснение |
| Процесс |  | Вычислительное действие или последовательность действий |
| Решение |  | Проверка условий |
| Модификация |  | Начало цикла |
| Ввод-вывод |  | Ввод-вывод в общем виде |
| Пуск-останов |  | Начало или конец алгоритма |
<TBODY>При графическом представлении алгоритм изображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий.</TBODY> Такое представление называется блок-схемой алгоритма.
В блок-схеме каждому типу действий соответствует геометрическая фигура, представленная в виде блочного символа. Блочные символы соединяются линиями переходов, определяющими очередность выполнения действий.
В таблице 2.1. приведены наиболее часто употребляемые символы.
Блок "процесс" применяется для обозначения действия или последовательности действий, измен<