Теория алгоритмов, формальных языков, грамматик и автоматов. Бильгаева Н.Ц. - 6 стр.

UptoLike

Составители: 

Алгоритмы, в соответствии с которыми решение поставленных задач сводится к
арифметическим действиям, называются численными алгоритмами.
Алгоритмы, в соответствии с которыми решение поставленных задач сводится к
логическим действиям, называются логическими алгоритмами.
Различают однозначные и многозначные алфавитные операторы.
Под однозначным алфавитным оператором понимается такой алфавитный оператор,
который каждому входному слову ставит в соответствие не более одного выходного слова.
Под многозначным алфавитным оператором понимается такой алфавитный оператор,
который каждому входному слову ставит в соответствие более одного выходного слова.
Алфавитный оператор, не сопоставляющий данному входному слову а
i
никакого
выходного слова b
j
(в том числе и пустого), не определен на этом слове.
Совокупность всех слов, на которых алфавитный оператор определен, называется
областью его определения.
Два алфавитных оператора считаются равными, если равны соответствующие им
алфавитные операторы и совпадает система правил, задающих действие этих алгоритмов на
выходные слова.
Два алгоритма считаются эквивалентными, если у них совпадают алфавитные
операторы, но не совпадают способы их задания (система правил). Обычно в теории
алгоритмов рассматриваются лишь такие алгоритмы, которым соответствуют однозначные
алфавитные операторы.
1.5. Задания для самостоятельной работы
Во всех заданиях необходимо разработать схемы алгоритмов и проанализировать
процесс реализации алгоритма, т.е. последовательность шагов, которая будет порождена при
применении алгоритма к конкретным исходным данным.
1. Разработать словесные алгоритмы вычитания из некоторого числа А
последовательности n чисел b
1
, b
2
, ..., b
n
:
а) алгоритм вычисления по формуле:
C=(...((A - b
1
) - b
2
) - ... - b
n
)
б) алгоритм вычисления по формуле:
=
=
n
1i
i
bAC .
2. Разработать алгоритм вычисления по формуле:
=
=
n
1i
kik
)mk1 ,ni1(baC.
3. Разработать алгоритм вычисления по формуле:
)mk1 ,mi1(baC
m
1k
iki
×=
=
.
4. Разработать алгоритм поиска максимального (минимального) элемента из
последовательности, заданной в виде одномерного массива А = {a
1
, a
2
, ... , a
k
}.
5. Разработать алгоритм определения количества одинаковых чисел в
последовательности, заданной в виде одномерного массива А={a
1
, a
2
, . . . , a
k
}.
6. Разработать алгоритм подсчета количества одинаковых элементов в матрице B
размерностью n × m. Размерность матрицы вводится с клавиатуры.
7. Разработать алгоритм умножения матрицы на вектор.
8. Разработать алгоритм умножения матрицы на матрицу.
9. Разработать алгоритм транспонирования матрицы.
10. Разработать алгоритм, реализующий операцию объединения следующих двух
множеств:
A = {a
1
, a
2
, . . ., a
k
} и B= {b
1
, b
2
, ... , b
n
}