pdm_02

				Релятивизованные кванторы
Определение.			Пусть P(x),Q(x)		формулы логики предикатов,
имеющие свободную переменную x, тогда :
( x)P( x) Q(x)			(	x)(P(x) Q(x)), (	x)P( x) Q(x) ( x)(P(x) Q(x)).
кванторы:
( x)P( x) Q(x) и (				x)P( x) Q(x) называют релятивизованными.

Для р. кванторов справедливы следующие выражения:

1. ( x)P( x) Q(x) ↔ ( x)P( x) Q (x) 2. ( x)P( x) Q(x) ↔ ( x)P( x) Q (x)

Доказательство :

(1) : ( x)P( x) Q(x) ↔ ( x)(P(x) Q(x)) ↔ ( x)(P (x) Q (x)) ↔ ↔ ( x)(P(x) → Q (x)) ↔ ( x)P( x) Q (x) ч.т.д.

(2) : ( x)P( x) Q(x) ↔ ( x)(P(x) → Q(x)) ↔ ( x)(P(x) Q (x)) ↔ ↔ ( x)(P(x) Q (x)) ↔ ( x)P( x) Q (x) ч.т.д.

31

Логические операторы и предикаты в программировании

Логические операторы и предикаты в программировании применяют для организации:

-условных циклов;

-условных нециклических переходов;

-непосредственного вычисления значений логических функций.

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

Операция	оператор С++
и	&&, and
или	||, or
не	!, not
эквивалентность	==
не эквивалентность	!=
больше	>
больше или равно	>=
меньше	<
меньше или равно	<=

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

Например, в php есть два вида эквивалентности: без учѐта типа (==), с учѐтом типа (===).

32

Применение бинарных операторов ветвления

для реализации счѐтчика

Начало

// C++ чтение строки, подсчѐт количества

Объявление и ввод

// пробелов и длины вывод строки без пробелов

i=0; nsize=10; nspace=0

#include <iostream>

int main() {

i++

// объявление переменных и констант

const int nsize = 10;

// макс. размер строки

да

нет

char sinput[nsize];

// строка символов

i<nsize

int nspace = 0, i;

// счѐтчики

std::cin.getline(sinput,nsize);

// читаем строку

// цикл перебора элементов строки

for( i = 0; i < nsize; i++ ) {

да

нет

sinput[i]==' '

if( sinput[i] == ' ' ) nspace++;

// счѐтчик пробелов

else if(sinput[i] == 0 ) break;

// прерывание цикла

else std::cout<<sinput[i];

// вывод не пробелов

}

nspace++

// вывод числа пробелов и длинны строки

std::cout <<std::endl

<<"white space: "<<nspace<<std::endl

нет

да

<<"line

size: "<<(i+1)<<std::endl;

sinput[i]==0

return 0;

}

Результат работы программы:

Вывод

sinput[i]

break

1 2 34567890

1234567

white space: 2 Вывод значений счѐтчиков

line size: 10

Завершение 33

Реализация счѐтчика на языке assembler

// C++ и assembler int main() {

// объявление переменных и констант

const int nsize = 10;	// макс. размер строки
int nspace, len;	// счѐтчики
char sinput[nsize];	// строка символов
std::cin.getline(sinput, nsize);
// вставка на assembler
asm {
xor eax, eax	// счѐтчик пробелов
xor esi, esi	// счѐтчик смещения
mov ecx, nsize	// счѐтчик цикла
// цикл перебора элементов строки
sloop:	// начало цикла
cmp sinput[esi], 0	// проверка конца строки
je l1;	// выход из цикла
	// если конец строки
cmp sinput[esi], (' ')	// проверка пробела
jne l2	// если не пробел
inc eax	// добавляем пробел
l2:
inc esi	// счѐтчик смещения
loop sloop	// конец цикла
l1:
// копируем значения регистров в переменные
mov nspace, eax	// число пробелов
mov len, esi	// длина строки
}

// вывод числа пробелов и длинны строки std::cout<<std::endl

<<"white space: "<<nspace<<std::endl <<"line size: "<<(len+1)<<std::endl;

return 0;

Результат работы программы:

1 2 345

white space: 2 line size: 8

Assembler – ближе всех прочих языков к машинному коду. Мнемоники (команды) assembler являются интерпретацией машинных кодов достаточно удобной для восприятия и запоминания человеком, в то время как в прочих языках программирования за каждой командой (оператором, функцией) скрываются целые микропрограммы. В assembler возможно применение макросов, в некотором смысле, аналогом команд высокоуровневых языков.

34

}

Поразрядные логические операторы

Оператор

и

или

не

искл. или

сдвиг

сдвиг

вправо

влево

побитовое

побитовое

побитовая

побитовое

деление

умножение

интерпретация

исключающее

умножение

сложение

инверсия

на 2n

на 2n

или

перенос

нет

нет

нет

нет

есть

есть

C++

&

|

~

^

>>

<<

asm

and

or

not

xor

shr

shl

and

or

xop

0101 0011

0101 0011

0101 0011

1001 0101

1001 0101

1001 0101

0001 0001

1101 0111

1100 0110

not

shl

shr

0101 0011

1001 1001 << 2

1001 1001 >> 2

0110 0100

0010 0110

1010 1100

Assembler обычно имеет в своѐм составе многообразие поразрядных логических операторов имеющих некоторые различия, например: циклический сдвиг (rol, ror), линейный арифметический сдвиг (sal, sar) и 35 др.

Пример применения поразрядных логических операторов в языке C++

Оптимизация алгоритма однородного рекурсивного фильтра, исходная программа

//C++

//определение данных

const int	nsd =	2048;	// длина массива данных
unsigned char data[nsd];			// массив данных
const int	nwidth = 8;		// ширина окна фильтра
const int	nsr =	nsd - nwidth + 1; // длина массива данных
unsigned char result[nsr];			// массив данных
float sum	= 0.5	* (float)nwidth;	// переменная суммирования
// начало	расчѐта
for (int i = 0;		i < nsd; i++) {
data[i]	= // заполняем значениями массив исходных данных

(unsigned char)(64 * sin(float(i) / 10) + 16 * sin(M_PI_2 * i) + 128.0);

}

//однородный рекурсивный фильтр

//формируем первый отсчѐт

for (int i = 0; i < nwidth; i++) { sum += (float)data[i];

}

result[0] = (unsigned char)floor(sum / (float)nwidth);

// формируем последующие отсчѐты

int j =	1;	//	счѐтчик отсчѐтов result[]
for (int i		= nwidth; i < nsd;	i++) {
sum =	sum + (float)data[i] - (float)data[i - nwidth];
result[j++] = (unsigned char)floor(sum / (float)nwidth);
}			36

Оптимизированная программа

//C++

//определение данных const int nsd = 2048; unsigned char data[nsd]; const int npow = 3;

const int nwidth = 1 << npow; const int nsr = nsd - nwidth + 1; unsigned char result[nsr];

unsigned int sum = 1 << (npow - 1); unsigned int div;

//длина массива данных

//массив данных

//степень

//ширина окна фильтра 2^npow

//длина массива данных

//массив данных

//переменная суммирования

//переменная для сдвига (деления)

//начало расчѐта

//заполняем значениями массив for (int i = 0; i < nsd; i++) {

data[i] = // заполняем значениями массив исходных данных

(unsigned char)(64 * sin(float(i) / 10) + 16 * sin(M_PI_2 * i) + 128.0);

}

//однородный рекурсивный фильтр

//формируем первый отсчѐт

for (int i = 0; i < nwidth; i++) { sum += (unsigned int)data[i];

}

div = sum;

//сдвиг на npow бита вправо (деление на nwidth) result[0] = (unsigned char)(div >> npow);

//формируем последующие отсчѐты

int j = 1;

for (int i = nwidth; i < nsd; i++) {

	sum = sum + (unsigned char)data[i] - (unsigned char)data[i - nwidth];
	div = sum;
	result[j++] = (unsigned char)(unsigned char)(div >> npow);
	// сдвиг на npow бита вправо (деление на nwidth)	37
}

Обсуждение оптимизации

Оптимизация базировалась на предположениях:

-вычисления с целыми числами происходят быстрее, чем с числами с плавающей точкой; -операция побитового сдвига выполняется быстрее, чем дающее

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

Для получения результатов времени выполнения алгоритмы заключались в цикл (по 16385 итераций), запускались по 5 раз, далее выбиралось наименьшее пользовательское время, т.е. время вычислительного процесса алгоритма (User time). При компиляции оптимизация отключается.

38

Оптимизированный вариант выполняет задачу ~9.4 раза быстрее.

Список литературы

1.Набенин А. А. Дискретная математика. – М.: Научный мир, 2010. 512 с.: ил.

2.Андерсон Дж. А. Дискретная математика и комбинаторика. : Пер с англ. – М. Издательский дом «Вильямс», 2004. – 960 с.: ил. – Паралл. тит. англ.

3.Новиков Ф. А. Дискретная математика для программистов: Учебник для вузов. 3-е изд.

–СПб.: Питер, 2009. – 384 с.: ил.

4.Пирогов В. Ю. Ассемблер для Windows. Изд. 4-е перераб. и доп. – СПб.: БХВ-

Петербург, 2007. – 896 с.: ил. + CD-ROM.

5.Юров В. И. Assembler. Учебник для вузов. 2-е изд. – СПб.: Питер, 2011. – 637 с.: ил.

6.Прата С. Язык программирования С++. Лекции и упражнения, 6-е изд.: Пер. с англ.

–М.: ООО «И.Д. Вильямс», 2013. – 1248 с.:

ил. – Парал. тит. англ.

Константин Васильев. Портрет Достоевского. 1973 г.

39