среда, 30 мая 2012 г.

Таблица соответствия алгоритмических и программных фрагментов


Фрагменты блок-схем алгоритмов
Назначение
Соответствующие фрагменты программ на языке Pascal
Начало и конец алгоритма.
Begin и End
Блок обработки (в нем вычисляются новые значения или производится вызов подпрограмм).
X := A + B
Ввод исходных данных или вывод результатов.
Read (x,y) или write (x,y)
Ветвление полное. Если значение переменной а больше b, то выполняется x=a, иначе x=b.
if a>b then x:=a else x:=b
Ветвление неполное. Если значение переменной a больше b, то выполняется x=a.
if a>b then x:=a
Цикл с предусловием. Пока значение условия i<6 истино выполняется тело цикла, то есть действия К=К+1 и i=i+2. Переменная i определяет количество повторений и называется счетчиком цикла.
   i:=1;
         while i<6 do
         begin
               k:=k+1;
               i:=i+2;
         end
   write (k);
Цикл с постусловием.Пока значение условия i>6 ложно выполняется тело цикла, то есть действия К=К+1 и i=i+0,1.Переменная i определяет количество повторений в цикле и называется счетчиком цикла.
   i:=1;
   repeat
         k:=k+1;
         i:=i+0.1;
   until i<6;
   write (k);
Цикл с постоянным приращением счетчика. В этом цикле изменение счетчика цикла i происходит только на единицу.Пока значение счетчика цикла меньше или равно 6 выполняется тело цикла, то есть дейст-вия K=K+S и I=i+1.
   for i:=1 to 6 do
      k:=k+s;
   write (k);

Алгоритмы и алгоритмизация. Заключение

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

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


Двумерный массив. Например, в двумерном массиве А, изображенном на рис. 34, элемент со значением 5 расположен на пересечении третьей строки и второго столбца. Этот элемент будет обозначаться как А(3,2). А элемент А(1,4) имеет значение , равное нулю. Такое представление набора значений позволяет выполнять обработку как отдельных значений в двумерном массиве, так и последовательности значений, расположенных в строках или столбцах.

В дальнейшем будем считать, что для двумерного массива A(N,М) в обозначении элемента А(i,j) первое значение i соответствует номеру строки и изменяется от1 до N, а j - номеру столбца и изменяется от 1 до М. В отличие от одномерного массива, в котором использовался только один номер для определения местоположения элемента и требовался только один цикл для ввода элементов, в двумерном массиве для обработки элементов необходимы два вложенных друг в друга цикла. Внешний цикл предназначен для изменения номера строки i, а второй, внутренний, - для изменения номера столбца j в текущей строке i.

На рис. 35 представлен простой алгоритм ввода элементов, построенный в виде структуры из вложенных циклов.

Рис. 35. Алгоритм ввода элементов двумерного массива

При рассмотрении в дальнейшем алгоритмов обработки элементов двумерного массива в целях сокращения их размера фрагмент ввода элементов будем заменять отдельным блоком ввода

Алгоритмы обработки одномерных символьных массивов


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

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

Рассмотрим алгоритмическое решение распространенной задачи определения в массиве символов слова с максимальной длиной. Пусть исходный массив А содержит N символов. Для определения слова с максимальной длиной будем использовать сравнение длины текущего слова М с длиной предыдущего слова МАХ. Длина слова определяется как содержащееся в нем количество символов. Для того, чтобы вывести слово с максимальной длиной, необходимо запомнить номер элемента S, с которого начинается это слово. Алгоритм поиска в символьном массиве слова с максимальной длиной приведен на рис. 32, а его таблица трассировки для массива (Дул теплый ветер)- в таблице 8.

Рис. 32.Алгоритм поиска в символьном массиве слова с максимальной длиной.

Таблица 8. Таблица трассировки алгоритма поиска слова с максимальной длиной при N= 16 в тексте : "Дул теплый ветер"

A(K)K=NA(K)=" "M>MAXMMAXSНовое S
 1 Д нет нет  1 0 1 1
 2 у нет нет  2   
 3 л нет нет  3   
 4 " " нет да да 0 3 3 4
 5 т нет нет  1   
 6 е нет нет  2   
 7 п нет нет  3   
 8 л нет нет  4   
 9 ы нет нет  5   
 10 й нет нет  6   
 11 " " нет да да 0 6 10 11
 12 в нет нет  1   
 13 е нет нет  2   
 14 т нет нет  3   
 15 е нет нет  4   
 16 р да нет нет 5   

Рассмотрите результат, приведенный в таблице 8, для конкретного входного символьного массива "Дул теплый ветер" без последнего столбца. Однако, после выполнения приведенного на рис. 32 алгоритма для предложения "Дул теплый ветер" будет выведено слово из 7 символов, начинающихся с пробела :" теплый". Значит, формулу определения номера символа S = K-1 , с которого начинается слово с максимальной длиной, следует изменить на S = K. При этом надо будет изменить содержание блока вывода результата: вместо A( S -MАХ), : A(S) следует использовать A( S -MАХ), : A(S-1). Таким образом, таблица трассировки показала наличие ошибок в алгоритме, изображенном на рис. 32. После внесения изменений этот алгоритм будет работать правильно (см. модернизированный алгоритм поиска в символьном массиве слова с максимальной длиной на рис. 33).

Рис. 33. Модернизированный алгоритм поиска в символьном массиве слова с максимальной длиной

Алгоритмы обработки упорядоченных массивов - Поиск элементов в упорядоченном массиве


Задача поиска значения Х в упорядоченном по возрастанию значений массиве A(1)Х, то все элементы, имеющие номера с S по n также больше Х в силу упорядоченности массива по возрастанию значений. Поэтому для дальнейшего поиска половину значений массива можно исключить из рассмотрения. В первом случае - левую, во втором случае - правую половину. Рассмотрим пример. Допустим, что требуется определить совпадает ли значение Х=12 с каким-либо элементом в упорядоченном массиве А и если совпадает, то определить порядковый номер S этого элемента. Иллюстрация применения метода бинарного поиска для поиска элемента Х=12 в массиве (2,3,4,6,10,12,20,30,35,45) приведена на рис. 30.
Элементы массива А (2,3,4,6,10,12,20,30,35,45).
Номера элементов 1 2 3 4 5 6 7 8 9 10.
Первое деление S=5, А(5)=10 А(5)<Х), исключаем левую половину.

Элементы массива А (2,3,4,6,10,12,20,30,35,45).
Номера элементов 1 2 3 4 5 6 7 8 9 10.
Второе деление S=8, А(8)=30 А(8)>Х), исключаем правую половину.

Элементы массива А (2,3,4,6,10,12,20,30,35,45).
Номера элементов 1 2 3 4 5 6 7 8 9 10.
Третье деление S=6, А(6)=12 А(6)=Х), элемент Х=12 найден.


Рис.30. Иллюстрация применения метода бинарного поиска.

На рис.31 представлен алгоритм, реализующий метод бинарного поиска в упорядоченном массиве.

Рис.31.Алгоритм поиска методом бинарного поиска.

Алгоритмы обработки упорядоченных массивов

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

Алгоритмы сортировки одномерных массивов - Сортировка методом парных перестановок


Самый простой вариант этого метода сортировки массива основан на принципе сравнения и обмена пары соседних элементов. Процесс перестановок пар повторяется просмотром массива с начала до тех пор , пока не будут отсортированы все элементы , т.е. во время очередного просмотра не произойдет ни одной перестановки. Для подсчета количества перестановок целесообразно использовать счетчик - специальную переменную В. Если при просмотре элементов массива значение счетчика перестановок осталось равным нулю, то это означает, что все элементы отсортированы (см.рис.29).

Рис.29. Алгоритм сортировки методом парных перестановок содержит два цикла, внутренний цикл выделен цветом

Алгоритмы сортировки одномерных массивов - Сортировка модифицированным методом простого выбора


Этот метод основывается на алгоритме поиска минимального элемента. В массиве А(1..n) отыскивается минимальный элемент, который ставится на первое место . Для того, чтобы не потерять элемент , стоящий на первом месте , этот элемент устанавливается на место минимального . Затем в усеченной последовательности, исключая первый элемент, отыскивается минимальный элемент и ставится на второе место и так далее n-1 раз пока не встанет на свое место предпоследний n-1 элемент массива А, сдвинув максимальный элемент в самый конец.

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

Рис.27. Обобщенный алгоритм сортировки массива модифицированным методом простого выбора

Отметим, что для перестановки элементов местами необходимо знать их порядковые номера, алгоритм перестановки элементов массива был рассмотрен ранее (см. рис. 23). Алгоритмы ввода исходного массива и вывода этого же массива после сортировки изображены на рисунках 16 и 24 соответственно. Алгоритм поиска в массиве минимального элемента и его номера будет аналогичен рассмотренному в примере 10 алгоритму поиска максимального элемента, который представлен на рис.18. Однако, в этом алгоритме будут внесены изменения. Для того, чтобы определить какие изменения следует внести рассмотрим выполнение сортировки данным методом с акцентом на поиск минимального элемента на конкретном примере. Пусть исходный массив содержит 5 элементов (2,8,1,3,7). Количество просмотров согласно модифицированному методу простого выбора будет равно 4. Покажем в таблице 7, как будет изменяться исходный массив на каждом просмотре.

Таблица 7. Пример сортировки

Номер просмотра массива iИсходный массивМинимальный элементПереставляемый элементМассив после перестановки
НомерЗначениеНомерЗначение
 1 (2,8,1,3,7) 3 1 1 2 (1,8,2,3,7)
 2 1,(8,2,3,7) 3 2 2 8 1,(2,8,3,7)
 3 1,2,(8,3,7) 4 3 3 8 1,2,(3,8,7)
 4 1,2,3,(8,7) 5 7 4 8 1,2,3,7,8

Из данных, приведенных в таблице 7, следует, что поиск минимального значения в массиве на каждом просмотре осуществляется в сокращенном массиве, который сначала начинается с первого элемента, а на последнем просмотре массив, в котором ищется минимальный элемент начинается уже с четвертого (или n-1) элемента. При этом можно заметить, что номер первого элемента массива для каждого поиска и перестановки совпадает с номером просмотра i.

      Введем следующие обозначения :
      К- номер минимального элемента,
      J - номер элемента массива,
      М и А(К)- одно и тоже значение минимального элемента массива,
      i - номер переставляемого с минимальным элемента,
      А(i)- значение переставляемого элемента.

Тогда циклический алгоритм сортировки модифицированным методом простого выбора будет выглядеть следующим образом (рис.28).

Рис.28. Алгоритм сортировки массива модифицированным методом простого выбора


Алгоритмы обработки одномерных символьных массивов


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

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

Рассмотрим алгоритмическое решение распространенной задачи определения в массиве символов слова с максимальной длиной. Пусть исходный массив А содержит N символов. Для определения слова с максимальной длиной будем использовать сравнение длины текущего слова М с длиной предыдущего слова МАХ. Длина слова определяется как содержащееся в нем количество символов. Для того, чтобы вывести слово с максимальной длиной, необходимо запомнить номер элемента S, с которого начинается это слово. Алгоритм поиска в символьном массиве слова с максимальной длиной приведен на рис. 32, а его таблица трассировки для массива (Дул теплый ветер)- в таблице 8.

Рис. 32.Алгоритм поиска в символьном массиве слова с максимальной длиной.

Таблица 8. Таблица трассировки алгоритма поиска слова с максимальной длиной при N= 16 в тексте : "Дул теплый ветер"

A(K)K=NA(K)=" "M>MAXMMAXSНовое S
 1 Д нет нет  1 0 1 1
 2 у нет нет  2   
 3 л нет нет  3   
 4 " " нет да да 0 3 3 4
 5 т нет нет  1   
 6 е нет нет  2   
 7 п нет нет  3   
 8 л нет нет  4   
 9 ы нет нет  5   
 10 й нет нет  6   
 11 " " нет да да 0 6 10 11
 12 в нет нет  1   
 13 е нет нет  2   
 14 т нет нет  3   
 15 е нет нет  4   
 16 р да нет нет 5   

Рассмотрите результат, приведенный в таблице 8, для конкретного входного символьного массива "Дул теплый ветер" без последнего столбца. Однако, после выполнения приведенного на рис. 32 алгоритма для предложения "Дул теплый ветер" будет выведено слово из 7 символов, начинающихся с пробела :" теплый". Значит, формулу определения номера символа S = K-1 , с которого начинается слово с максимальной длиной, следует изменить на S = K. При этом надо будет изменить содержание блока вывода результата: вместо A( S -MАХ), : A(S) следует использовать A( S -MАХ), : A(S-1). Таким образом, таблица трассировки показала наличие ошибок в алгоритме, изображенном на рис. 32. После внесения изменений этот алгоритм будет работать правильно (см. модернизированный алгоритм поиска в символьном массиве слова с максимальной длиной на рис. 33).

Рис. 33. Модернизированный алгоритм поиска в символьном массиве слова с максимальной длиной 

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

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

Алгоритмы обработки одномерных числовых массивов

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

Доступ к любому элементу массива осуществляется по его номеру ( индексу ). Поэтому для обращения к элементу массива используют имя массива (номер элемента), например, А(5).

Одномерный массив.

Рис. 16. Алгоритм ввода элементов

Рассмотрим простой алгоритм ввода элементов одномерного числового массива A из 9 элементов. В этом циклическом алгоритме условие выхода из цикла определяется значением специальной переменной К, которая называется счетчиком элементов массива А (рис.16), эта же переменная К определяет количество итераций циклического алгоритма ввода элементов массива. На каждом шаге итерации переменная К(значение номера элемента массива А) изменяется на 1, то есть происходит переход к новому элементу массива. В дальнейшем, при рассмотрении алгоритмов обработкиодномерных массивов в целях устранения дублирования алгоритм ввода элементов массива будем заменять одним блоком, подразумевая, что он реализуется по схеме, циклического алгоритма, представленного на рисунке 16.

Пример 9

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

Пример 10

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

Алгоритмы обработки последовательностей чисел

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

Циклические алгоритмы


Циклические алгоритмы.


Цикл с предусловием начинается с проверки условия выхода из цикла. Это логическое выражение, например I<=6. Если оно истинно, то выполняются те действия, которые должны повторяться. В противном случае, если логическое выражение I<=6 ложно, то этот цикл прекращает свои действия.

Цикл с постусловием функционирует иначе. Сначала выполняется один раз те действия, которые подлежат повторению, затем проверяется логическое выражение , определяющее условие выхода из цикла, например, I>6 .Проверка его осуществляется тоже по-другому. Если условие выхода истинно, то цикл с постусловием прекращает свою работу, в противном случае - происходит повторение действий, указанных в цикле. Повторяющиеся действия в цикле называются "телом цикла". Разновидности циклов приведены на рис. 10 а),б).
a) Цикл с постусловием
б) Цикл с предусловием

Рис. 10. Виды циклических алгоритмов

Классическим примером циклического алгоритма служит алгоритм для вычисления степени числа Y=X? . Этот алгоритм может быть реализован на основе операции умножения. Табличное представление такого алгоритма, отражающего зависимость У от Х при изменении показателя степени n от 1 до 3, представлено в табл.3. В этой таблице показанны также реккурентные соотношения между У и Х, определяющие как на каждом шаге зависит значение У от значения Х и от значения У, вычисленного на предыдущем шаге.

Таблица 3. Реккурентные соотношения при вычислении Y=X^n

nYРеккурентные соотношения
1
Y[1]=X
Y=X
2
Y[2]=X*X или Y[2]=Y[1]*X
Y=X*X или Y=Y*X
3
Y[3]=X*X*X или Y[3]=Y[2]*X
Y=X*X*X или Y=Y*X

Разветвленные алгоритмы


Разветвленные алгоритмы. Ветвление.
ветвление
неполное ветвление
многоальтернативный выбор

Рис. 4. Структуры ветвления

Каждая управляющая структура ветвления имеет один вход и один выход. Ветвления содержат блок условия, в котором записывают логические условия, такие как А >С , X<= Y. В зависимости от значений переменных А, С в управляющей структуре ветвления на рис. 4 а) условие А >С принимает значение "истина" или "ложь" и процесс вычислений включает блок действия Z=A или Z=C. Аналогично происходит и в управляющей структуре неполного ветвления (рис. 4 б)). Только в этом случае , если условие X<= Y истинно, то выполняется действие С=Х, в противном случае никаких действий не выполняется.

В управляющей структуре многоальтернативный выбор в блоке условия записывается переменная, в данном случае Х, которая может принимать различные значения (рис. 4в)). Если значение пременной Х совпадет с одним из значений в блоке действия, то выполняется действия , записанные в этом блоке. Например, если Х=1, то выполнится действие У=1. Если значение Х не совпало ни с одним из значений, указанных в блоках справа, то выполняется действие в блоке слева, которого также как и в неполном ветвлении может и не быть.

Визуальные алгоритмы


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

Рис. 2. Основные блоки визуальных алгоритмов

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

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

Композиция (следование).

Альтернатива.

Итерация.

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

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

Рис. 3. Пример линейного визуального алгоритма

Основные средства представления алгоритмов

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

Алгоритм, реализующий решение задачи, можно представить различными способами: с помощью графического или текстового описания, в виде таблицы значений. Графический способ представления алгоритмов имеет ряд преимуществ благодаря визуальности и явному отображению процесса решения задачи. Алгоритмы, представленные графическими средствами, получили название визуальные алгоритмы. Текстовое описание алгоритма является достаточно компактным и может быть реализовано на абстрактном или реальном языке программирования в виде программы для ЭВМ. Таблицы значений представляют алгоритм неявно, как некоторое преобразование конкретных исходных данных в выходные. Табличный способ описания алгоритмов может быть с успехом применен для проверки правильности функционирования разработанного алгоритма на конкретных тестовых наборах входных данных, которые вместе с результатами выполнения алгоритма фиксируются в "таблицах трассировки".

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

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


Слово "алгоритм" появилось в 9-м веке и связано с именем математика Аль-Хорезми, который сформулировал правила выполнения четырех арифметических действий над многозначными числами.

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

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

Алгоритм.

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

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

Формальное решение задачи


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

Модель. Моделирование.

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

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

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

Анализ постановки задачи и ее предметной области


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

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

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

Различают исходные данные трех видов: постоянные, условно-постоянные и переменные.
  • Постоянные исходные данные;
  • Условно-постоянные данные;
  • Переменные данные;
На этом этапе важно не только классифицировать данные по отношению к процессу решения, но определить их наименование, тип, структуру и ограничения, накладываемые на значения. Желательно также определить допустимые и недопустимые операции по отношению к различным типам исходных данных. Классификация данных по структурному признаку

Рисунок 1. Классификация данных


На рис.1 представлена классификация данных.

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

Структурированные данные отличаются от простых тем, что к ним применимо другое отношение: одно имя - много значений. Если все элементы, входящие в такую структуру, однотипны, то такая структура называется однородной, в противном случае - неоднородной. Классическим примером однородной структуры является массив, являющийся последовательностью однотипных значений, таких как, например, (2,51,3,7,88). Неоднородная структура в отличие от однородной содержит значения различных типов, относящихся к одному понятию или объекту, и, значит, такое структурированное данное несет в себе больше информации. Для представления неоднородных структур используютзапись. Запись - это структура, предназначенная для представления данных различного типа. Запись состоит из поименованных полей, каждое из которых должно содержать значение определенного типа. 

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

Таблица 1. Пример записи

 Имя поля: Город
 Имя поля: Количество жителей
 Тип поля: Строка символов Тип поля: Число
 Значение: Москва Значение: 8 578 676

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

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

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

Навигация по файловой структуре


 Организация файловой системы
 Обслуживание файловой структуры
 Создание и именование файлов
 Особенности Windows 95 и Windows 98.
 Копирование и перемещение файлов
 Создание каталогов
 Удаление файлов и каталогов (папок)
 Навигация по файловой структуре
 Управление атрибутами файлов
ПЗУ таких компьютеров, можно условно рассматривать как аналог операционной системы. Ее автоматический запуск осуществляется аппаратно. При подаче питания процессор обращается к фиксированному физическому адресу ПЗУ (его можно изменять аппаратно с использованием логических микросхем), с которого начинается запись программы инициализации операционной системы.
Организация файловой системы
Все современные дисковые операционные системы обеспечивают создание файловой системы, предназначенной для хранения данных на дисках и обеспечения доступа к ним. Принцип организации файловой системы — табличный. Поверхность жесткого диска рассматривается как трехмерная матрица, измерениями которой являются номера поверхности, цилиндра и сектора. Под цилиндром понимается совокупность всех дорожек, принадлежащих разным поверхностям и находящихся на равном удалении от оси вращения. Данные о том, в каком месте диска записан тот или иной файл, хранятся в системной области диска в специальных таблицах размещения файлов (FAT-таблицах). Поскольку нарушение FAT-таблицы приводит к невозможности воспользоваться данными, записанными на диске, к ней предъявляются особые требования надежности, и она существует в двух экземплярах, идентичность которых регулярно контролируется средствами операционной системы.
Наименьшей физической единицей хранения данных является сектор. Размер сектора равен 512 байт. Поскольку размер FAT-таблицы ограничен, то для дисков, размер которых превышает 32 Мбайт, обеспечить адресацию к каждому отдельному сектору не представляется возможным. В связи с этим группы секторов условно объединяются в кластеры. Кластер является наименьшей единицей адресации к данным. Размер кластера, в отличие от размера сектора, не фиксирован и зависит от емкости диска.
Операционные системы MS-DOS, OS/2, Windows 95 и Windows NT реализуют 16-разрядные поля в таблицах размещения файлов. Такая файловая система называется FAT16. Она позволяет разместить в FA T-таблицах не более 65 536 записей (216) о местоположении единиц хранения данных и, соответственно, для дисков объемом от 1 до 2 Гбайт длина кластера составляет 32 Кбайт (64 сектора). Это не вполне рациональный расход рабочего пространства, поскольку любой файл (даже очень маленький) полностью оккупирует весь кластер, которому соответствует только одна адресная запись в таблице размещения файлов. Даже если файл достаточно велик и располагается в нескольких кластерах, все равно в его конце образуется некий остаток, нерационально расходующий целый кластер.
Для современных жестких дисков потери, связанные с неэффективностью файловой системы, весьма значительны и могут составлять от 25% до 40% полной емкости диска, в зависимости от среднего размера хранящихся файлов. С дисками же размером более 2 Гбайт файловая система FAT16 вообще работать не может.
В настоящее время только операционная система Windows 98 обеспечивает более совершенную организацию файловой системы — FAT32 с 32-разрядными полями в таблице размещения файлов. Для дисков размером до 8 Гбайт эта система обеспечивает размер кластера 4 Кбайт (8 секторов).
Обслуживание файловой структуры
Несмотря на то что данные о местоположении файлов хранятся в табличной структуре, пользователю они представляются в виде иерархической структуры — людям так удобнее, а все необходимые преобразования берет на себя операционная система. К функции обслуживания файловой структуры относятся следующие операции, происходящие под управлением операционной системы:
•          создание файлов и присвоение им имен;
•          создание каталогов (папок) и присвоение им имен;
•          переименование файлов и каталогов (папок);
• копирование и перемещение файлов между дисками компьютера и между каталогами (папками) одного диска;
• удаление файлов и каталогов (папок);
• навигация по файловой структуре с целью доступа к заданному файлу, каталогу (папке);
- управление атрибутами файлов.
Создание и именование файлов
Файл — это именованная последовательность байтов произвольной длины. Поскольку из этого определения вытекает, что файл может иметь нулевую длину, то фактически создание файла состоит в присвоении ему имени и регистрации его в файловой системе — это одна из функций операционной системы. Даже когда мы создаем файл, работая в какой-то прикладной программе, в общем случае для этой операции привлекаются средства операционной системы.
По способам именования файлов различают “короткое” и “длинное” имя. До появления операционной системы Windows 95 общепринятым способом именования файлов на компьютерах IBM PC былосоглашение 83. Согласно этому соглашению, принятому в MS-DOS, имя файла состоит из двух частей: собственно имени и расширения имени. На имя файла отводится 8 символов, а на его расширение — 3 символа. Имя от расширения отделяется точкой. Как имя, так и расширение могут включать только алфавитно-цифровые символы латинского алфавита.
Соглашение 83 не является стандартом, и потому в ряде случаев отклонения от правильной формы записи допускаются как операционной системой, так и ее приложениями. Так, например, в большинстве случаев система “не возражает” против использования некоторых специальных символов (восклицательный знак, символ подчеркивания, дефис, тильда и т. п.), а некоторые версии MS-DOS даже допускают использование в именах файлов символов русского и других алфавитов. Сегодня имена файлов, записанные в соответствии с соглашением 83, считаются “короткими”.
Основным недостатком “коротких” имен является их низкая содержательность. Далеко не всегда удается выразить несколькими символами характеристику файла, поэтому с появлением операционной системы Windows 95 было введено понятие “длинного” имени. Такое имя может содержать до 256 символов. Этого вполне
достаточно для создания содержательных имен файлов. “Длинное” имя может содержать любые символы, кроме девяти специальных: \ /:*?"<> |. В имени разрешается использовать пробелы и несколько точек. Расширением имени считаются все символы, идущие после последней точки.
Наряду с “длинным” именем операционные системы Windows 95 и Windows 98 создают также и короткое имя файла — оно необходимо для возможности работы с данным файлом на рабочих местах с устаревшими операционными системами.
Особенности Windows 95 и Windows 98.
Использование “длинных” имен файлов в операционных системах Windows 95 и Windows 98 имеет ряд особенностей.
1. Если “длинное” имя файла включает пробелы, то в служебных операциях его надо заключать в кавычки. Рекомендуется не использовать пробелы, а заменять их символами подчеркивания.
2. В корневой папке диска (на верхнем уровне иерархической файловой структуры) нежелательно хранить файлы с длинными именами — в отличие от прочих папок в ней ограничено количество единиц хранения, причем чем длиннее имена, тем меньше файлов можно разместить в корневой папке.
3. Кроме ограничения на длину имени файла (256 символов) существует гораздо более жесткое ограничение на длину полного имени фата (в него входит путь доступа к файлу, начиная от вершины иерархической структуры). Полное имя не может быть длиннее 260 символов.
4. Разрешается использовать символы любых алфавитов, в том числе и русского, но если документ готовится для передачи, с заказчиком (потребителем документа) необходимо согласовать возможность воспроизведения файлов с такими именами на его оборудовании.
5. Прописные и строчные буквы не различаются операционной системой. Для нее имена Письмо.txt и письмо-txt соответствуют одному и тому же файлу. Однако символы разных регистров исправно отображаются операционной системой, и, если для наглядности надо использовать прописные буквы, это можно делать.
6. Программисты давно научились использовать расширение имени файла для передачи операционной системе, исполняющей программе или пользователю информации о том, к какому типу относятся данные, содержащиеся в файле, и о формате, в котором они записаны. В ранних операционных системах этот факт использовался мало. По существу, операционные системы MS-DOSанализировали только расширения .ВАТ (пакетные файлы с командами MS-DOS), .EXE, .COM (исполнимые файлы программ) и .SYS (системные файлы конфигурации). В современных операционных системах любое расширение имени файла может нести информацию для операционной системы. Системы Windows 95/98 имеют средства для регистрации свойств типов файлов по расширению их имени, поэтому во многих случаях выбор расширения имени файла не является частным делом пользователя. Приложения этих систем предлагают выбрать только основную часть имени и указать тип файла, а соответствующее расширение имени приписывают автоматически.
Создание каталогов (папок)
Каталоги (папки) — важные элементы иерархической структуры, необходимые для обеспечения удобного доступа к файлам, если файлов на носителе слишком много| Файлы объединяются в каталоги по любому общему признаку, заданному их созда-телем (по типу, по принадлежности, по назначению, по времени создания и т. п.)| Каталоги низких уровней вкладываются в каталоги более высоких уровней и являются для них вложенными. Верхним уровнем вложенности иерархической структуры является корневой каталог диска.
Все современные операционные системы позволяют создавать каталоги. Правила присвоения имени каталогу ничем не отличаются от правил присвоения имени файлу, хотя негласно для каталогов не принято задавать расширения имен. Мы знаем, что в иерархических структурах данных адрес объекта задается маршрутом (путем доступа), ведущим от вершины структуры к объекту. При записи пути доступа к файлу, проходящего через систему вложенных каталогов, все промежуточные каталоги разделяются между собой определенным символом. Во многих операционных системах в качестве такого символа используется “\” (обратная косая черта).
Особенности Windows 95 и Windows 98. До появления операционной системы Windows 95 при описании иерархической файловой структуры использовался введенный выше термин каталог. С появлением этой системы был введен новый термин — папка. В том, что касается обслуживания файловой структуры носителя данных, эти термины равнозначны: каждому каталогу файлов на диске соответствует одноименная папка операционной системы. Основное отличие понятий папка и каталог проявляется не в организации хранения файлов, а в организации хранения объектов иной природы. Так, например, в Windows 95 и Windows 98 существуют специальные папки, представляющие собой удобные логические структуры, которым не соответствует ни один каталог диска.
Копирование и перемещение файлов
В неграфических операционных системах операции копирования и перемещения
файлов выполняются вводом прямой команды в поле командной строки. При этом
указывается имя команды, путь доступа к каталогу-источнику и путь доступа к
каталогу-приемнику.
В графических операционных системах существуют приемы работы с устройством
позиционирования, позволяющие выполнять эти команды наглядными методами.
Удаление файлов и каталогов (папок)
Средства удаления данных не менее важны для операционной системы, чем средства их создания, поскольку ни один носитель данных не обладает бесконечной емкостью. Существует как минимум три режима удаления данных: удаление, уничтожение и стирание, хотя операционные системы обеспечивают только два первых режима (режим надежного стирания данных можно обеспечить лишь специальными программными средствами).
Удаление файлов является временным. В операционных системах Windows 95 и Windows 98 оно организовано с помощью специальной папки, которая называется Корзина. При удалении файлов и папок они перемещаются в Корзину. Эта операция происходит на уровне файловой структуры операционной системы (изменяется только путь доступа к файлам). На уровне файловой системы жесткого диска ничего не происходит — файлы остаются в тех же секторах, где и были записаны. Уничтожение фатов происходит при их удалении в операционной системе MS-DOS или при очистке Корзины в операционных системах Windows 95/98. В этом случае файл полностью удаляется из файловой структуры операционной системы, но на уровне файловой системы диска с ним происходят лишь незначительные изменения. В таблице размещения файлов он помечается как удаленный, хотя физически остается там же, где и был. Это сделано для минимизации времени операции. При этом открывается возможность записи новых файлов в кластеры, помеченные как “свободные”.
Для справки укажем, что операция стирания фатов, выполняемая специальными служебными программами, состоит именно в том, чтобы заполнить якобы свободные кластеры, оставшиеся после уничтоженного файла, случайными данными. Поскольку даже после перезаписи данных их еще можно восстановить специальными аппаратными средствами (путем анализа остаточного магнитного гистерезиса), для надежного стирания файлов требуется провести не менее пяти актов случайной перезаписи в одни и те же сектора. Эта операция весьма продолжительна, и поскольку массовому потребителю она не нужна, то ее не включают в стандартные функции операционных систем.
Навигация по файловой структуре
Навигация по файловой структуре является одной из наиболее используемых функций операционной системы. Удобство этой операции часто воспринимают как удобство работы с операционной системой. В операционных системах, имеющих интерфейс командной строки, навигацию осуществляют путем ввода команд перехода с диска на диск или из каталога в каталог. В связи с крайним неудобством такой навигации, широкое применение нашли специальные служебные программы, называемые файловыми оболочками.
Как и операционные системы, файловые оболочки бывают неграфическими и графическими. Наиболее известная неграфическая файловая оболочка для MS-DOS — диспетчер файлов Norton Commander, а роль графической файловой оболочки для MS-DOS в свое время исполняли программы Windows 1.0 и Windows 2.0, которые постепенно развились до понятия операционной среды (в версиях Windows 3.x) и далее до самостоятельной операционной системы (Windows 95/98).