1. Понятие алгоритма: рекурсивные функции, системы текстовых замен.

Алгоритм — конечная последовательность действий, приводящих к результату.

Терминистический — для любой последовательности шагов алгоритма, он заканчивается

за конечное число шагов.

Детерминированный — независимо от количества шагов результат определяется однозначно.

Детерминистический — нет никакой последовательности в выборе следующего шага.

Свойства алгоритма:

1.Конечность 2.Определенность 3.Результативность 4.Массовость

5.Состоит из конечного числа шагов 6.Эффективность

Алгоритм Евклида — Находит НОД двух чисел (вычитает наиб. и наим. и сравнивает)

Существование или не существование можно определить, если найти математический объект, который будет существовать тогда, когда существует алгоритм.

1) Оператор рекурсии строит рекурсивную функцию следующим образом: значение искомой функции при нулевом значении главного дополнительного аргумента считать значением функции f1, а для последующего значения главного дополнительного аргумента значение функции f2. Для предыдущего значения ГДА и для значения ВДА, совпадающего со значением искомой функции на предыдущем шаге : f(0)=f1;f(i)=fi(i,f(i)); Пример (для функции f(x)=x-1):

f::=R {φ0, ψ2, 1(x, y), x(y)}

f (0)=y0=0

f(1)=f2(0,0)= ψ2,1(0,0)=0

f(2)= f3(0,0)= ψ2,1(1,0)=1

2)Оператор подстановки и суперпозиции: Сначала вычисляются значения f1 и f2 и используют как аргумент для вычисления функции F: Ʈ(y)=λ(λ(y))=λ(y’)=y’’

3)Оператор минимизации или построения по первому нулю.

f::=μ{f1,y}; f(x1,..xn)= μ{f1(x1,..xn, y),y}

Замена s->t применение правила v->w, если есть слова a,v,w,z ЄV*, такие что справедливо: s=a*v*z; t=a*w*z

2.Системы счисления, переводы чисел из одной позиционной системы в другую.

Система счисления — совокупность правил наименований и записи числа.

Позиционные/Непозиционные — значение цифры числа зависит/не зависит от ее положения.

1. 2->10 2. 8->10. 3. 10->2 4. 2->8 5. 8->2 6.8->16.

3/4.Понятие подпрограммы, функции, возвращающей/не возвращающей значение в

С/С++, описание и использование.

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

Назначение:

1)Позволяет избегать дублирования программы, делает ее короче.

2)Делает структуру программы четкой и более понятной.

3)Подпрограммы позволяют расширять языки программирования, добавив новые

функции, операции, операторы, процедуры.

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

Пример.

Функция возвращающая сумму 2-х чисел:

#include <iostream>

Using namespace std;

Int sum(int x,int y){return x+y;}

Int main() {int a=5,b=6,c; C=sum(a,b); Cout<<”sum=”<<c<<endl; Cout<<”sum=”<<sum(a,b);

Return 0; }

В С\С++ используется один тип подпрограмм — функция, но они могут выдавать один результат и тогда обращение к ним — указатель функции и в этом случае обращение-операнд, и когда несколько результатов и выходные параметры-результаты, а в С — это функции не возвращающие значение.

Пример.

#include <stdio.h>

Void p (int k(по значению),int *d(по адресу указатель))

{ Int j;*d=1; For (j=2;j<=k;j++) *d=*d*j; Return; }