Теория вычислительных процессов. Лабораторная работа №2

Задания

Функции: F(n), G(n) определены с помощью операционной семантики равенствами:
F(0)=I, G(0)=2, F(n)=G(n-I), G(n)=F(n-l) + G(n-I).

Найти значения F(3) и G(3).

2. Формальные языки Е и Т определены над алфавитом {а, *, &, <, >} с помощью денотационной семантики равенствами

Е = Т U * Т U Е & Т и Т= а U а* U <Е>.

Какие из следующих строк *а&*а*&а*; *а&<а&а*>; *<*а*&а>&<*а*>* принадлежат языку Е и какие не принадлежат.

3. Написать программу, используя аксиоматическую стратегию построения и проверки цикла. Дан массив B[0:n-1], n > 0. Присвоить переменной х наименьшее значение из B. Если наименьшее значение встречается в B более одного раза, выбрать любой из них.

Предусловие Q: n >0;

Постусловие R: x<= B[О: n-1] AND (j: 0<=j < n х = B[j]);

Инвариант Р: 0<=j<=n АND х<=B[0:n-l] AND (j :i<=j<n х=B[j]);

Ограничение t: i.

4. Написать программу, используя различные методы построение инвариантов циклов. Дан массив B[0:n-1], n > 0. Определить, состоит ли B[0: n-l] из одних нулей.

СибГУТИ, 2013 г., оценка: зачет