Файлы в других языках

Аналогом операции в/в-да с текстовыми файлами в Фортране являются операции форматного в/в-да.

Примеры операторов:

read(N,F) p1,p2,… – форматный ввод

write(N,F) p1,p2,… – форматный вывод

где N – логический номер (некоторый аналог файловой переменной, целое число определяемое операционной системой), F – метка оператора формата:

read(5,200) a1

200 format (1X,E123)

в а1 читается значение формата 200.

Аналогом операций с типизированными ф-лами является в Fortran’e операции неформатного в/в-да:

read(N) p1,p2,… – неформатный ввод

write(N) p1,p2,… – неформатный вывод

Фортран не накладывает ограничения на то чтобы р1,р2,… были одного типа. Т.е. список ввода всегда должен быть таким же для вывода.

Для работы с файлами применяются специальные операции открытия и закрытия файлов: OPEN(UNIT=10, NAME=‘F.DAT’, TYPE=‘OLD’)

Кло-во параметров может быть 16.

Для открытия нового файла: OPEN(… TYPE=‘NEW’)

закрытия: CLOSE(UNIT = 10) //максимальное число парам-ов 16

Фортран поддерживает работу с ф-лами прямого доступа.

DEFINE FILE … - определяет структуру ф-ла прямого доступа

где N – логический номер, R – номер эл-та.

Многие операторы работы с ф-лами допускают использование дополнительных параметров обработки ошибок.

read(N, 200, ERR = 300, END = 310) p1, p2, …

…

300 …

…

310 …

где ERR, END – дополнительные параметры обработки ошибок.

Эти параметры могут быть использованы в операторе write и open.

Нетипизированных ф-лов в Фортране нет. Но возможна работа с такими ф-лами с применением библиотек:

ireadw(WCNT, BUF, DBLK, CHAN)

где WCNT – счётчик передаваемых слов по 2 байта, BUF – буфер, CHAN и DBLK – специальные системные параметры.

В Ассемблере:

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

3. Алгоритмы

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

Существует несколько форм описания алгоритмов:

1. словесное (для решения неформализованных задач)

2. запись с использованием математической либо другой специальной нотации

3. графическое изображение алгоритма

4. запись на метаязыке

5. запись на алгоритмическом языке

Название алгоритма может указывать либо на его назначение, либо на метод решения задачи.

3.1. Типы алгоритмов. Сложность алгоритмов.

Существует 2 типа алгоритмов: детерминированные и недетерминированные.

Детерминированные алгоритмы предполагают прямое решение задачи без использования повторов и выбора вариантов. Такой алгоритм не содержит элементов неопределённости. (Они всегда простые.)

Недетерминированные алгоритмы допускают повторы, выборы вариантов и использование метода проб и ошибок. Т.е. они содержат некоторый элемент неопределённости. Может использоваться такое понятие, как случайный выбор. Например, поиск оптимального маршрута через лабиринт, поисковый алгоритм нахождения экстремума ф-ции n переменных. (Это сложные алгоритмы.)

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

Некоторые задачи могут быть решены с использованием обоих типов алгоритмов. Например, задача нахождения нужной строки в таблице. Если индекс строки известен, то алгоритм обращения к этой строке является детерминированным. Если индекс строки неизвестен заранее, то для нахождения строки может быть применён алгоритм случайного поиска (недетерминированный) (строка ищется по какому-то признаку и строки перебираются случайным образом). Такой способ эффективен для больших таблиц. Также может использоваться последовательный поиск перебором (II-й недетерминированный алгоритм). При таком методе строка будет найдена за 2n итераций (n-число строк). Последовательный поиск эффективен для малых объёмов.

Сложность алгоритмов

Сложность алгоритма определяет зависимость времени работы алгоритма от объёма обрабатываемых данных.

Основные типы сложности алгоритмов:

1. Постоянная сложность – имеют алгоритмы, рассчитанные на обработку фиксированного объёма данных.

2. Линейная сложность (например, алгоритм обработки массива в памяти). Время работы такого алгоритма может быть оценено так: an+b, где n – количество элементов массива, a – время, необходимое для выполнения операций над отдельным элементом массива, b – время, затрачиваемое на выполнение вспомогательных операций.

3. Квадратичная сложность (например, алгоритм пузырьковой сортировки). (n-1) сравнений для определения I-го элемента,(n-2) – II-го элемента, (n-1)+(n-2)+…+3+2+1= . Для больших n время работы алгоритма ~ .

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

Пример оценки сложности по тексту программы (алгоритм сортировки) :

Procedure сортировка;

For k:=1 to n-1 do

Min:=A(k); lok:=k;

For i:=k+1 to n do

If min>A(i) then

Min:=A(i); loc:=I;

A(loc):=A(k); A(k):=min

End;

В данной прог-е внешний цикл исполняется n-1 раз, а внутренний исполняется в среднем раз.Общее число исполнений внутреннего цикла = . Для больших n количество исполнений ~ . Т.е. алгоритм обладает квадратичной сложностью.

Оценка сложности алгоритма умножения 2-х матриц размерности n*n:

For i:=1 to n do

For j:=1 to n do

C(i,j):=0;

For k:=1 to n do

C(i,j):=C(i,j)+A(i,k)*B(k,j);

Сложность ~ (т.к. 3 цикла).

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

Можно дать формальное определение сложности алгоритма, используя нотацию «большого О» и понятие порядка функции. Считается, что 2 ф-ции f(n) и g(n) одного порядка, если для больших n существует константа k: . И формально такое высказывание записывается так: f(n)=O(g(n)).

Сложность алгоритмов обозначается:

O(n) – для алгоритмов линейного поиска

O( ) - для пузырьковой сортировки

O( ) - для перемножения матриц

O( ) - для двоичного поиска