Алгоритм –это точно определенная, однозначная последовательность простых (элементарных) шагов, обеспечивающих решение любой задачи из некоторого класса. 4 страница

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

Списки. Список – это набор записей, выстроенных в определенной последовательности.

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

При этом физический порядок размещения записей не соответствует логическому – записи располагаются в любых свободных ячейках ОЗУ, причем не обязательно подряд. Такие структуры называются связными списками.

Их удобство состоит в гибкости структуры – без перезаписи остальных элементов можно легко добавлять новые или исключать имеющиеся – для этого достаточно изменить состояние поля указателя адреса (рисунок 4.2).

Указатель начала списка называется HeadPointer (HP), конца списка – NIL (пустой указатель).

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

Стеки. Стек – это список, в котором добавление и удаление элементов идет только на одном конце. Следствием такого ограничения является то, что последний добавленный элемент всегда будет удален первым – из-за этого стеки называют структурами LIFO (Last In, First Out).

Тот конец стека, где добавляются и удаляются элементы, называется вершиной. Другой конец называют основанием стека. Процесс добавления записи в стек называется проталкиванием (push), а процесс удаления - выталкиванием (рop).

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

Для реализации стека в памяти ОЗУ обычно резервируют блок смежных ячеек памяти достаточного размера, чтобы вместить стек с учетом его увеличения или уменьшения. Решение о размере этого блока зачастую является критическим.

По мере проталкивания и выталкивания записей вершина стека перемещается вперед и назад в пределах зарезервированного блока. Для того, чтобы отслеживать положение вершины, ее адрес хранится в дополнительной ячейке памяти, называемой указателем стека (Stack Pointer) (рисунок 4.3).

 

Контрольные вопросы

1. Приведите классификационные признаки и соответствующую классификацию данных.

2. Как размещаются в оперативной памяти элементарные данные?

3. Что такое массив? Как размещается массив в памяти компьютера?

4. Что представляет собой связный список?

5. Проиллюстрируйте на примере, как происходит добавление элемента в связный список? удаление элемента из списка?

6. Как выполняются операции добавления/удаления в двунаправленном связном списке?

7. Где используются стеки?

5 Хранение информации на внешних запоминающих устройствах. Файловые структуры

5.1 Особенности устройств, используемых для хранения
информации в компьютерах

Устройства, выполняющие операции, связанные с сохранением или считыванием данных на материальном носителе, называются внешними запоминающими устройствами (ВЗУ) или устройствами внешней памяти.

Любое ВЗУ реализует один из 2-х возможных принципов размещения информации – последовательный доступ или прямой доступ.

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

Для реализации прямого доступа на носителе должны быть обозначены (пронумерованы) области для записи информации – такие области называются блоками. Обратиться к данным для записи/считывания можно по номеру блока. Операция разбиения поверхности носителя на блоки называется форматированием – она производится в обязательном порядке и предшествует использованию носителя.

Блок обычно имеет строго определенную для одного носителя информации емкость, например, для дискеты блок 512 байт.

Блок может содержать только целое число физических записей – из-за этого часть блока длиной меньше чем размер записи оказывается пустой и не используется. Например, при длине записей по 150 байт в один блок размером 512 байт поместится 3 записи, а 62 байта останутся свободными.

На носителях большой емкости, например, жестком диске, блоки объединяются в группы – кластеры (обычно по 8 блоков). Адресация применяется по номерам кластеров (это уменьшает общее количество адресов и, следовательно, ускоряет поиск и доступ к информации).

При обмене между ВЗУ и ОЗУ данные пересылаются не отдельными записями, а блоками, размер которых совпадает с размером блока ВЗУ (рисунок

5.1).

 

Для организации обмена в ОЗУ выделяется специальная область – буфер обмена. Размер буфера устанавливается при конфигурировании ОС (BUFFERS =).

Обмен между ВЗУ и ОЗУ идет, минуя центральный процессор - в этом случае одновременно с обменом может производиться обработка данных.

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

При желании использовать данные с ВЗУ, во-первых, сначала весь информационный массив должен быть перенесен в ОЗУ (с ВЗУ никакой обработки не ведется); во-вторых, нужные данные в этом массиве отыскиваются последовательно.

Другими словами, прямой доступ оказывается некой комбинацией произвольного и последовательного.

Емкость накопителей на дисках зависит от числа используемых дисков и плотности расположения дорожек и секторов.

Системы малой емкости состоят из одного пластмассового диска, покрытых с двух сторон тонким слоем магнитного материала. Это - дискеты, флоппи-диски, FDD. Обычные 3.5” дискеты способны вмещать 1,44 МБ.

Диски большой емкости состоят из 5-10 жестких дисков, установленных на общем шпинделе. Из-за того, что диски, используемые в этих устройствах, жесткие и само устройство называется жестким диском (Hard disk, HDD). Для большой скорости вращения головки чтения/записи в этих устройствах не соприкасаются с диском, а «плавают» над его поверхностью.

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

Чтобы оценить качество накопителя на диске, используется несколько параметров:

- время поиска – время, которое требуется, чтобы переместить головки чтения/записи с одной дорожки на другую;

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

- время доступа – сумма времени поиска и времени ожидания;

- скорость передачи – скорость, с которой данные могут быть переданы с диска или на диск.

Поскольку в жестком диске головки чтения/записи не касаются поверхности диска, скорость вращения на сегодняшний день составляет порядка 3000 – 4000 об/мин, в то время как на гибких дисках – 300 об/мин. Следовательно, скорость передачи жесткого диска значительно больше, чем у гибких дисков.

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

Другая распространенная технология хранения – компакт – диски (CD). Эти диски диаметром 12 см состоят из отражающего материала, покрытого прозрачным защитным слоем. Запись информации на них осуществляется посредством изменения структуры при помощи лазерного луча, который контролирует отличия структуры отражающего слоя диска по мере его вращения.

Технология производства CD первоначально применялась для звукозаписи, при этом используется формат CD-DA (CDA) (Compact Disk – Digital Audio).

CD, которые применяются сегодня для хранения данных, имеют этот же формат. А именно – информация на этих дисках хранится на единственной спиральной дорожке (похожа на грампластинку), но размещается эта дорожка внутри диска, а не на его поверхности.

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

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

Емкость обычного компакт-диска 650 МБ.

Однако новый формат DVD (Digital Versatile Disk – универсальный цифровой диск) имеет емкость порядка 10 ГБ. Пока, в основном формат DVD используется для записи фильмов.

 

5.2 Представление данных на внешних носителях

Основными информационными единицами при сохранении данных на внешних носителях являются:

- логическая запись;

- физическая запись;

- файл;

- каталог (папка).

Логическая запись при хранении на внешних носителях является той же информационной единицей, что и при хранении в ОЗУ. (Логическая запись – поименованная совокупность элементарных данных, имеющая смысловую завершенность).

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

Единственной характеристикой отдельной записи является ее длина, а допустимыми операциями – перенос на носитель и считывание с него.

После размещения данных на носителе они превращаются в физическую запись.

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

Объединение физических записей образует файл.

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

Комментарии к определению:

- оформленная совокупность записей означает, что помимо непосредственных записей файл всегда имеет имя (идентификатор) и признак конца файла (Eof, EndOfFile). По имени файл отыскивается на носителе; признак Eof необходим, поскольку по нему устанавливается ближайшее к данному файлу свободное место, в которое можно ввести запись следующего файла; а при пересылке в ОЗУ по нему определяется граница информационного массива;

- как единое целое – означает, что при обращении доступе к файлу отсутствует доступ к отдельным его записям; файл записывается и считывается только целиком. В ОС над файлами определен ряд операций: копирование, перемещение, переименование, удаление и т.п., но в конечном счете они сводятся только к операциям чтения/записи, а также изменениям в описании файлов;

- описание в системе – означает сохранение на носителе не только самих файлов, но и сведений о них и их размещений; эти сведения используются в операциях с файлами.

Любые файлы содержат данные, закодированные с помощью двоичного алфавита. Однако способы кодирования и назначение файлов может быть различными. По этой причине файлам приписывается еще одна характеристика – тип. Тип входит в идентификатор файла и указывается в виде расширения имени (Глава.doс, calc.exe и т.п.).

Принципиально различными по типам следует считать программные (исполняемые) файлы и файлы данных.

Программные файлы содержат тексты программ в машинном коде, они могут быть загружены в ОЗУ и исполняться. Расширения программных файлов.com,.exe. Файлы данных формируются в результате работы какой-либо программы, они не являются исполняемыми и служат только в качестве хранилищ данных. Многие программные системы при формировании данных приписывают им вполне конкретные расширения – по ним можно установить, какой программой файл создан (.doc,.xls,.rtf,.bmp,.jpg,.pas,.bas,.c).

Тип файла, как и его собственное имя, является частью описания файла и сохраняется системой.

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

Таким образом, папки образуют иерархическую структуру – поэтому часто используют термин «дерево каталогов» (папок). При этом каталог, расположенный на вершине иерархии называется корневым.

В процессе работы над файлами и папками производят следующие операции:

· создание – в текущем каталоге создается новый экземпляр объекта, ему дается имя);

· копирование – копия объекта создается в другом каталоге или на другом носителе;

· перемещение – производится копирование объекта в другой каталог или на другой носитель, в исходном каталоге объект уничтожается;

· удаление – в исходном каталоге объект уничтожается;

· переименование – изменяется имя объекта;

· нахождение на диске по имени файла и содержащейся в нем строке символов;

· архивирование файлов.

5.3 Роль операционной системы

Создает и поддерживает файловые структуры, определяет максимальный уровень вложенности каталогов, а также производит все операции с файлами и каталогами часть ОС – файловая система.

На дисковых носителях имена файлов хранятся отдельно от физических записей. В определенном месте диска при его форматировании создается специальная область, в которой располагается таблица размещения файлов – FAT (File Allocation Table).

В эту таблицу заносятся имена и атрибуты файлов (дата и время создания, размер, атрибуты доступа), а также номер кластера, с которого начинается размещение файла.

Обращение к файлу происходит в 2 этапа: сначала с помощью файловой таблицы по имени файла находится номер кластера, а затем считывающая/записывающая головка ВЗУ устанавливается над ним и производит операции (рисунок 5.3)

FAT
Имена	Атрибуты	Адреса
… book.doc	12.03.2007
свободн. адрес

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

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

Процесс создания дескриптора называется открытием файла, а процесс удаления дескриптора – закрытием файла.

В DOS, UNIX операции над файлами и папками выполняются подачей из командной строки специальных команд. В семействе ОС Windows для этих целей служит специальная служебная программа Проводник (Explorer). Графический интерфейс позволяет осуществить эти же операции и другими способами, например, с использованием контекстного меню.

Значительная часть пользователей всех ОС предпочитают применять при работе с файлами специальные программы-оболочки. Наибольшей популярностью пользуются программы Norton Commander, Windows Commander.

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

Контрольные вопросы

1. Какие возможные принципы доступа к информации реализуют ВЗУ?

2. Для чего предназначена процедура форматирования?

3. Перечислите основные единицы хранения информации на ВЗУ.

4. Дайте определение понятиям «файл» и «папка».

5. Что такое дескриптор файла?

6 Основы алгоритмизации

6.1 Понятие алгоритма. Свойства алгоритма

Считается, что термин «алгоритм» произошел от фамилии узбекского математика IX века Мухаммада ибн-Муса аль–Хорезми ( в европейской фонетике – алхоризм, алгорифм, алгоритм), который впервые сформулировал правила четырех основных арифметических действий в десятичной системе счисления.

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

Алгоритм –это точно определенная, однозначная последовательность простых (элементарных) шагов, обеспечивающих решение любой задачи из некоторого класса.

Это нестрогое определение, поскольку в нем использованы другие неопределенные понятия – однозначность, элементарность и пр.

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

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

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

- результативность – алгоритм всегда приводит к конечному результату после конечного числа шагов;

- массовость – алгоритм применяется для решения некоторого класса (то есть многих) задач.

В 20-е гг. XX века уточнение определения алгоритма стало одной из центральных математических проблем. Попытки формулировки такого понятия привели к появлению в 30-х гг. теории алгоритмов как самостоятельной науки.

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

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

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

Пригоден ли для описания алгоритма обычный разговорный язык?

Любой естественный язык появился как средство общения людей. Именно поэтому ему присущи такие особенности как:

- изменчивость (непостоянство словарного запаса);

- неоднозначность трактовки фраз различными людьми;

- избыточность.

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

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

Однако степень формализации определяется тем, кто(что) предполагается в качестве его исполнителя.

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

Если алгоритм предназначен для исполнителя «человек», то его запись может быть не полностью формализована; существенным в представлении оказывается понятность и наглядность – по этим причинам для записи алгоритма может быть использован естественный язык или язык графический.

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

Итак, в представлении алгоритма можно выделить две основные формы – символьную и графическую.

6.2 Символьная форма представления алгоритма

В символьном представлении наибольшее распространение получила строчная запись.

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

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

Псевдокод – ориентированный на исполнителя «человек» частично формализованный язык, позволяющий записывать алгоритм в форме, близкой к языкам программирования.

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

Основные примитивы (стандартные блоки) псевдокода, из которых строится представления алгоритма.

1. Присвоение значения описательному имени

Имя выражение; Имя:= выражение;,

где Имя – описательное имя (идентификатор), а выражение – определяет значение, которое присваивается этому имени.

Остаток Товара Начальный Остаток + Приход – Расход.

2. Ветвление – выбор одного из действий в зависимости от истинности или ложности какого-либо условия.

if (условие) then (действие 1) else (действие 2);

Если (условие) то (действие 1) иначе (действие 2);

if (високосный год) then ежедневная сумма годовая сумма /366

else ежедневная сумма годовая сумма /365;.

3. цикл (повторение) с предварительным условием – пока выполняется условие, выполнять действия (do):

while (условие) do (действие);

Пока (условие) повторять (действие);

while (есть билеты) do (продавать билеты).

4. внешнее оформление (proc – начало алгоритма)

end – завершение алгоритма)

Алг/ конец – в русской нотации.

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

Пример 1. Решение квадратного уравнения ax² + bx + c = 0

Алг Корни;

Задать a, b, c;

D:= b² - 4 × a × c;

Если D > 0

то (x₁:= (- b + )/2 a; x₂:= )

иначе

Если D = 0 то (x:= )

иначе (сообщить, что корней нет);

Конец.

 

Пример 2. Алгоритм Евклида – нахождение наибольшего общего делителя (НОД)

Словесное описание.

1. Задать числа a и b;

2. Если a = b, результатом считать a; закончить вычисления.

3. Если a > b, найти разность (a – b); новым значением a считать значение разности, перейти к п.1.

4. Если b > a, найти разность (b – a); новым значением b считать значение разности; перейти к п.1.

 

Алг Евклид;

Задать a, b;

Пока (a ¹ b) повторять

Если a > b то a a – b

иначе b b – a;

Результат (a);

Конец.

 

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

Еще один вид строчной записи – язык программирования.

Язык программирования – искусственный формализованный язык, предназначенный для записи алгоритма для исполнителя «компьютер».

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

Различают языки низкого уровня и высокого уровня.

К языкам первого типа относятся:

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

- ассемблер (макроассемблер) – язык символического кодирования. Операторами языка являются машинные команды, которым приписывается мнемоническое обозначение, а в качестве операндов используются не конкретные адреса в ОЗУ, а их символические имена (CLA – очистить аккумулятор, ADD а – добавить в регистр-аккумулятор значение а).

Запись алгоритма производится в текстовом редакторе. Следовательно, для преобразования текста в последовательность машинных кодов необходима еще одна промежуточная программа – транслятор (переводчик).

Ассемблер является машинно-зависимым языком, то есть записанная на нем программа может использоваться лишь на той технике (точнее том типе процессора), ассемблер которого был использован.

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

Примерами операторов, содержащихся во всех языках программирования, являются: операторы присваивания, условные операторы, операторы циклов; обязательно есть операторы ввода/вывода для организации взаимодействия с пользователем.

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

Примерами таких языков являются:

FORTRAN (Formula Translator) - язык решения сложных научных и инженерных задач (это был первый язык высокого уровня);

COBOL (Common Business Oriented Language) – язык для решения экономических и коммерческих задач;

LISP - решение задач искусственного интеллекта;

PROLOG – задачи логического вывода и т.п.

К универсальным языкам относятся C, PASCAL, Basic, JAWA, а также современные среды визуального программирования Delphi, Visual Basic и т.п.