II семестр (стр. 4 )

Метод сортировки устойчив, если он не меняет порядок элементов с одинаковыми ключами.

Сортировка «на том же месте» – без использования дополнительной памяти (Под дополнительной памятью понимают память, объем которой зависит от количества элементов структуры).

Эффективность сортировки определяется объемом дополнительной памяти, если сортировка не «на том же месте», и затратами времени.

Алгоритмы сортировки будем характеризовать двумя параметрами:

С - количество сравнений ключей, М - количество перестановок.

8.2 Алгоритмы сортировки

Три класса алгоритмов сортировки (включением, выбором, обменом)

8.2.1 Сортировка простым включением.

Всякая неупорядоченная последовательность данных может быть представлена как «упорядоченная часть» плюс «неупорядоченная часть». Действительно, «упорядоченной частью» может считаться подпоследовательность, состоящая из одного единственного первого элемента всей последовательности, остальные элементы представляют собой «неупорядоченную часть».

Пусть первые k элементов массива a упорядочены.

Первый элемент «неупорядоченной части» a[k+1] включается в «упорядоченную часть» на свое место следующим образом:

Значение a[k+1] записывается в переменную x. Далее «сдвигаются» на одну позицию в направлении возрастания индекса все элементы, большие чем x, до первого элемента, меньшего x. На «освободившееся» место записывается значение, хранящееся в x.

Procedure sort01(var a:Mass; N:integer);

var i, j:integer; x:Mem;

begin

for i:=2 to N do

begin

x:=a[i];

a[0]:=x;{Барьер!}

j:=i-1;

while x. key<a[j].key do begin a[j+1]:=a[j]; j:=j-1; end;

a[j+1]:=x;

end;

end;

Свойства:

·  Устойчивость;

·  Естественное поведение (если массив упорядочен, то меньше перестановок)

Смин=N-1; Сср=N2/4; Cмакс= N2/2; Ммин=2(N-1); Мср=N2/4; Ммакс= N2/2;

8.2.2 Сортировка бинарным включением

В отличие от сортировки простым включением, место размещения включаемой записи «вычисляется» с помощью бинарного поиска.

for i:=2 to N do

begin

x:=a[i]; l:=1; r:=i;

while l<r do

begin

m:=(l+r) div 2;

if x. key<a[m].key then r:=m else l:=m+1

end;

for j:=i-1 downto l do a[j+1]:=a[j];

a[l]:=x;

end;

Свойства: Неестественное поведение. Сср=N log2N; Mcp=N2

8.2.3 Сортировка простым выбором

Из неупорядоченной части выбирается самый «маленький» элемент и ставится в «конец» упорядоченной части.

for i:=1 to N-1 do

begin

k:=i;

x:=a[i];

for j:=i+1 to N do if a[j].key<x. key then begin k:=j; x:=a[j] end;

a[k]:=a[i];

a[i]:=x;

end;

Свойства: Число сравнений не зависит от начального порядка С=N2/2

Ммин=3(N-1); Mcp=N log2N; Mмакс=N2/4

8.2.4 Сортировка простым обменом (пузырек)

For i:=2 to N do

begin

for j:=N downto i do

if a[j-1].key>a[j].key then

begin

x:=a[j-1];

a[j-1]:=a[j];

a[j]:=x

end;

end;

Свойства: Сср= N2/2; Мср=0.75 N2

Улучшения: Запоминать, где был обмен

Шейкер-сортировка - чередование направлений второго цикла.

8.2.5 Сортировка Шелла

Понятие h - сортировки (сортируется последовательность элементов с шагом h, повторяется h раз со сдвигом)

Сортировка Шелла - применение h1,h2, hk - сортировки, причем hk=1

Рекомендуются последовательности: ...121, 40, 13, 4, 1 или... 31, 15, 7, 3, 1

Найти закономерности в этих последовательностях.

Свойство: Доказано, что i-отсортированная последовательность остается i-отсортированной после к-сортировки.

Мср=N1.2

8.2.6 Быстрая сортировка Хоара

«Разделение» массива

i:=1;

j:=N;

Выбор медианы x

repeat

while a[i].key<x. key do i:=i+1;

while x. key<a[j].key do j:=j-1;

if i<=j then

begin

w:=a[i];

a[i]:=a[j];

a[j]:=w;

i:=i+1;

j:=j-1

end;

until i>j;

procedure sort(l, r:integer);

var i, j:integer; x, w:Mem;

begin

i:=l; j:=r; x:=a[(l+r) div 2];

«разделение»

if l<j then sort(l, j);

if i<r then sort(i, r);

end;

8.2.7 Алгоритм сортировка последовательных файлов слиянием.

М-серия – уже упорядоченная последовательность из М элементов

Слияние двух М-серий - дает 2М-серию.

Картинка!

Ссылка на стр.106 Вирта. Там таблица эффективностей алгоритмов сортировки.

Лекция 9

О дискретном представлении чисел в ЭВМ.

9.1 Приближенные числа

Числа, заданные с погрешностью (или с заданной точностью)

Пример:

Вычислить

Обозначим

Приближения:

1). - с точностью 0.02;

2) с точностью 0.003

7/5	64/15625=0.004196..	1/125=0.008000	1.000
17/12	15625/2985354=0.005238	1/216=0.0046296	-1/6=-0.1666...

Выводы:

1. Ошибки переносятся и могут быть усилены.

2. Тождественные математические соотношения могут дать различные результаты.

3. Нужно уметь выбирать «лучшую» формулу.

9.2 Источники погрешностей

Конечность десятичного представления в ЭВМ.

Данные из эксперимента (систематические ошибки, случайные ошибки).

Итерационные методы вычислений.

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

Распространение ошибок в арифметических действиях.

9.3 Классификация погрешностей

Погрешность округления.

Неустранимая погрешность (определяется областью неопределенности).

Погрешность метода.

9.4 Терминология

- точное значение величины; - приближенное значение величины.

- абсолютная погрешность; - относительная погрешность.

- число, такое, что - граница абсолютной погрешности.

- число, такое, что - граница относительной погрешности.

принадлежит интервалу или ;

Интервал - область неопределенности - неустранимая погрешность.

Если оказалось, что , то говорят, что произошла потеря точности.

Машинный ноль - это минимальное число, которое ЭВМ отличает от нуля.

Исчезновение порядка - результат оказался меньше машинного нуля.

Переполнение арифметического устройства, или просто переполнение - результат больше (по модулю) максимального числа, которое может воспринимать ЭВМ.

9.5 Распространение ошибок в арифметических операциях

Основные правила (неустранимая погрешность):

а).

а’)

б).

в).

г).

д).

Пример 1

=2520; =2518;

Это означает, что

Пример 2

.

Относительная погрешность =

=

Объяснение примера п.3

=

=

=

Задачи

Указать абсолютную и относительную погрешность, а также область неопределенности при округлении приближенных величин до 2 знаков после запятой:

1998.1998, 14. 3.1 0.0001

Получить относительные погрешности при вычислении значений арифметических выражений:

,

,

.

Для всех переменных граница абсолютной погрешности задана величиной 0.01.

Лекция 10

Рекомендуемая литература:

1.  , , Клецкова -77 для ПЭВМ ЕС. "Финансы и статистика", 1991.

2.  FORTRAN для персонального компьютера (справочное пособие), "Arist", 1991.

3.  , , Шура-Бура программ на фортране. "Ф и С", 1984.

4.  , , Ярошевский -ловушки при программировании на фортране.

FORmula TRANslation (станд.66, станд.77(*))

*Излагается стандарт Фортран-66

10.0 Бланк для записи текста программы на Фортране

	6	…………………………………………………….…….	73 74 ………79 80
		Операторы	Комментарий
		Оператор не уместился на строке,	Комментарий
	*	Вот его продолжение	Комментарий
7 7 7		Помеченный оператор	Комментарий
С		Это строка-комментарий	Комментарий

10.1 Элементы языка

Алфавит:

ABCDEFGHIJKLMNOPQRSTUVWXYZ

+ - * /

( )

. , : '

=

&

$ (на отечественных клавиатурах заменен символом ☼ – конвертируемый рубль)

пробел

любые символы в комментариях и текстовых константах.

Символические имена – идентификаторы (слова, состоящие из букв и цифр, начинающиеся с буквы, содержащие не более 6 символов).

Переменная – <символическое имя, тип, значение>

Массив – заранее определенное конечное множество однотипных переменных, обладающих одним и тем же именем, последовательно расположенных в памяти ЭВМ.

Переменная с индексом – элемент массива. С помощью индекса осуществляется выделение конкретной переменной из массива. Индексом может служить данное (выражение) целого типа, заключенное в круглые скобки.

Константа – частный случай переменной, в которой имя определяет и тип и значение.

10.2 Типы данных и операции

Константы: (цц = цепочка цифр)

Тип	Обозначение	Описание
Целый	I	[+/-]цц
Действительный	F	[+/-]цц. цц
	E	[+/-]ццE[+/-]цц
	E	[+/-]цц. ццE[+/-]цц
	D	[+/-]цц. ццD[+/-]цц
Логический	L	.TRUE. .FALSE.
Комплексный	C	(действительный, действительный)
текстовой(*)	T	'любая послед. символов не более 127'
Шестнадцатеричный (*)	#	[+/-]16#цепочка цифр и букв A..F

Операции:

·  арифметические

1.  + – сложение

2.  - – вычитание

3.  * – умножение

4.  / – деление

5.  ** – возведение в степень.

·  отношения

1.  .GT. – больше

2.  .GE. – больше или равно

3.  .LT. – меньше

4.  .LE. – меньше или равно

5.  .EQ. – равно

6.  .NE. – не равно.

·  логические

1.  .NOT. – логическое отрицание

2.  .AND. – логическое умножение (конъюнкция)

3.  .OR. – логическое сложение (дизъюнкция)

4.  .EQV. – логическая эквивалентность (*)

5.  .NEQV. – логическая неэквивалентность (*)

·  текстовые // - конкатенация

Выражение: Осмысленная конструкция, в которой операции (арифметические, логические, текстовые) связывают (арифметические, логические, текстовые) величины (константы, переменные).

Метки: 1..99999

Комментарии: Часть текста программы, игнорируемая транслятором.

10.3 Описание переменных и констант

Тип и длина	Константы	Переменные
Целый, 4	I	Неявное IJKLMN	INTEGER INTEGER*4
Целый, 2	-	INTEGER*2
Действительный, 4	E	F	Неявное кроме IJKLMN	REAL REAL*4
Действительный, 8	E	D	REAL*8 DOUBLE PRECISION
Комплексный, 8	(E, E)	COMPLEX, COMPLEX*8
Комплексный, 16	(D, D)	COMPLEX*16
Логический, 4	.TRUE. .FALSE.	LOGICAL, LOGICAL*4
Логический, 2	-	LOGICAL*2
Текстовой, n<127	nHxxx...x ‘xxx...x’	CHARACTER*n (*)

10.4 Арифметические операции

А#B	I2	I4	R4	R8	C8	C16
I2	I2	I4	R4	R8	C8	C16
I4	I4	I4	R4	R8	C8	C16
R4	R4	R4	R4	R8	C8	C16
R8	R8	R8	R8	R8	-	C16
C8	C8	C8	C8	-	C8	C16
C16	C16	C16	C16	C16	C16	C16

Старшинство (приоритет) операций: 1) **, 2) *, / 3). +, -