Informatika_Методичка 2 часть

Ввод любых данных с клавиатуры не должен вызывать аварийного завершения работы программы.

5.Работа тестирующей программы организована в виде простейшего меню, позволяющего создавать таблицу, выполнять ее сортировку, показывать результат (вызов редактора), сохранять текущую матрицу в файле и заканчивать работу. При создании новой матрицы старая уничтожается (с запросом на сохранение в файле), т.е. в каждый момент времени в памяти находится не более одного объекта.

6.Любые необратимые действия с матрицей должны выполняться только после запроса на подтверждение.

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

Дополнительные:

8.Редактор реализован самостоятельно.

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

10.Возможность хранения в памяти нескольких таблиц одновременно.

11.Оценка любых других дополнительных возможностей программы в баллах оставляется на усмотрение преподавателя.

Варианты задания

1.Отсортировать строки матрицы в лексикографическом порядке по возрастанию. Сортировка простыми включениями.

2.Отсортировать столбцы матрицы в порядке невозрастания количества отрицательных элементов. Сортировка простыми включениями.

3.Отсортировать строки матрицы по неубыванию абсолютных величин сумм их элементов. Сортировка простыми включениями.

4.Отсортировать столбцы матрицы по неубыванию сумм положительных элементов. Сортировка простыми включениями.

5.Отсортировать строки матрицы в лексикографическом порядке по возрастанию. Сортировка бинарными включениями.

6.Отсортировать столбцы матрицы в порядке невозрастания количества отрицательных элементов. Сортировка бинарными включениями.

7.Отсортировать строки матрицы по неубыванию абсолютных величин сумм их элементов. Сортировка бинарными включениями.

8.Отсортировать столбцы матрицы по неубыванию сумм положительных элементов. Сортировка бинарными включениями.

9.Отсортировать строки матрицы в лексикографическом порядке по возрастанию. Сортировка простым выбором.

10.Отсортировать столбцы матрицы в порядке невозрастания количества

11

отрицательных элементов. Сортировка простым выбором.

11.Отсортировать строки матрицы по неубыванию абсолютных величин сумм их элементов. Сортировка простым выбором.

12.Отсортировать столбцы матрицы по неубыванию сумм положительных элементов. Сортировка простым выбором.

13.Отсортировать строки матрицы в лексикографическом порядке по возрастанию. Сортировка методом пузырька с ограничением.

14.Отсортировать столбцы матрицы в порядке невозрастания количества отрицательных элементов. Сортировка методом пузырька с ограничением.

15.Отсортировать строки матрицы по неубыванию абсолютных величин сумм их элементов. Сортировка методом пузырька с ограничением.

16.Отсортировать столбцы матрицы по неубыванию сумм положительных элементов. Сортировка методом пузырька с ограничением.

17.Отсортировать строки матрицы в лексикографическом порядке по возрастанию. Сортировка Шелла с заданной в виде локального константного массива последовательностью приращений.

18.Отсортировать столбцы матрицы в порядке невозрастания количества отрицательных элементов. Сортировка Шелла с заданной в виде локального константного массива последовательностью приращений.

19.Отсортировать строки матрицы по неубыванию абсолютных величин сумм их элементов. Сортировка Шелла с заданной в виде локального константного массива последовательностью приращений.

20.Отсортировать столбцы матрицы по неубыванию сумм положительных элементов. Сортировка Шелла с заданной в виде локального константного массива последовательностью приращений.

21.Отсортировать строки матрицы в лексикографическом порядке по возрастанию. Быстрая сортировка.

22.Отсортировать столбцы матрицы в порядке невозрастания количества отрицательных элементов. Быстрая сортировка.

23.Отсортировать строки матрицы по неубыванию абсолютных величин сумм их элементов. Быстрая сортировка.

24.Отсортировать столбцы матрицы по неубыванию сумм положительных элементов. Быстрая сортировка.

25.Отсортировать строки матрицы в лексикографическом порядке по возрастанию. Сортировка фон Неймана.

26.Отсортировать столбцы матрицы в порядке невозрастания количества отрицательных элементов. Сортировка фон Неймана.

27.Отсортировать строки матрицы по неубыванию абсолютных величин сумм их элементов. Сортировка фон Неймана.

28.Отсортировать столбцы матрицы по неубыванию сумм положительных элементов. Сортировка фон Неймана.

12

ИНДИВИДУАЛЬНОЕ ЗАДАНИЕ № 3

Цель работы: приобрести навыки создания и использования абстрактных типов данных (АТД) на основе методологии объектного программирования. Развить опыт работы с модулями и опыт конструирования алгоритмов над абстрактными типами данных. Развить и закрепить навыки разработки интерфейса «человек-компьютер».

Содержание задания

1.Реализовать абстрактный тип данных (стек, дек, очередь и т.п., в зависимости от варианта), инкапсулированный в объектном типе данных.

2.Создать подпрограмму обработки указанного АТД.

3.Составить программу, обеспечивающую тестирование разработанных подпрограмм.

4.Подготовить несколько наборов данных для полного тестирования программы.

Рекомендации к программе

1.Требования к межпрограммному интерфейсу стандартны. Все подпрограммы должны быть написаны в стиле защитного и структурного программирования.

2.Способ реализации классов абстрактных типов данных должен обеспечивать достаточную эффективность использования памяти (динамический класс памяти). Реализация алгоритма должна быть максимально эффективна по времени и памяти.

3.Любые необратимые действия с объектом должны выполняться только после запроса на подтверждение.

4.При сдаче программы преподавателю следует приготовить несколько тестовых файлов для наиболее полного тестирования. Набор тестовых файлов должен обеспечить работу каждой ветви алгоритма. Также необходимо обеспечить граничные испытания, испытания в исключительных ситуациях и на так называемых нулевых примерах.

Требования к программе

Основные:

1.АТД из варианта реализован как класс и находится в отдельном модуле.

2.Алгоритм обработки АТД не является методом класса и не находится в модуле, в котором реализован АТД. Иными словами, алгоритм должен быть реализован как независимая функция.

3.Данные для тестирования хранятся в типизированных файлах.

4.Обработка ошибок фатальная.

13

Дополнительные:

1.Сообщения об ошибках читаются из специального файла.

2.Обработка ошибок не фатальная. При возникновении ошибки предлагается загрузить другой источник данных.

3.Обработка ошибки производится по маске.

4.Все классы реализованы на основе списков.

Варианты задания

1.Дан дек строковых элементов. Составить новый дек, записывая в него элементы исходного дека, изымая их поочередно слева и справа.

2.Дана очередь целых чисел. С помощью вспомогательной очереди удалить из исходной все четные числа.

3.Дан дек, элементами которого являются символы; проверить, является ли слово в деке перевертышем.

4.Даны две очереди целых чисел, элементы которых упорядочены по неубыванию. Составить из их элементов третью очередь, упорядоченную по невозрастанию.

5.Дан стек целых чисел. Переставить его элементы так, чтобы от дна до вершины шли сначала нечетные числа, потом четные.

6.Даны два стека целых чисел. Элементы в стеках упорядочены от дна к вершине в первом стеке по невозрастанию, во втором - по неубыванию. Создать третий стек, состоящий из всех элементов первых двух, упорядоченных по невозрастанию.

7.Дан стек символов. Инвертировать последовательность элементов в стеке, добавляя до и после заданного символа кавычки.

8.Дана очередь целых чисел. Изъять из неё все отрицательные числа и поместить в новую очередь в порядке, обратном исходному.

9.Дана очередь строковых элементов. Изъять из неё все повторения заданной строки и поместить в новую очередь в порядке, обратном исходному.

10.Дан дек целых чисел. Переставить его элементы так, чтобы слева направо шли сначала отрицательные числа, потом неотрицательные.

14

ИНДИВИДУАЛЬНОЕ ЗАДАНИЕ № 4

Цель работы: приобрести и развить навыки составления подпрограмм и их локального тестирования. Изучить способы передачи параметров, включая передачу параметров-подпрограмм. Изучить методы приближенного вычисления интегралов Римана и оценки точности вычислительных методов.

Содержание задания

1.Составить подпрограмму вычисления определенного интеграла Римана для достаточно гладкой подынтегральной функции, используя составную квадратурную формулу с равномерным разбиением и автоматическим выбором шага.

2.Провести тестирование разработанной подпрограммы.

3.Составить программу вычисления нескольких заданных интегралов.

Теоретические сведения. Интерполяционные квадратурные формулы

Решение ряда прикладных задач приводит к необходимости вычисления определенных интегралов, либо не выражающихся через элементарные или специальные функции, либо таких, в которых интегрируемые функции не указаны явно (таблично заданные, функции, определяемые алгоритмами):

b

I f (x)dx . (1)

a

1.Формулы Ньютона-Котеса — это интерполяционные квадратурные формулы, в которых узлы расположены на одинаковом расстоянии друг от друга. Они особенно удобны для интегрирования таблично заданных функций. Рассмотрим простейшее из них.

1.1. Формулы прямоугольников. Для вычисления интеграла (1) заменим подынтегральную функцию f (x) постоянной функцией L0 ( x) , равной

значению f (x) в одной из точек отрезка.

Если выбрана точка a , т. е. крайняя левая точка отрезка, то

L0 (x) f (a) ,

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

Если выбрана точка b и, т.е. крайняя правая точка отрезка, то

L0 (x) f (b) ,

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

Если выбрана центральная точка отрезка, т.е. точка (a b)2 , то

15

L0 (x) f ((a b)2) ,

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

Вычисляя определённый интеграл от полученного приближения, получаем квадратурные формулы прямоугольников:

b
f (x)dx (b a) f (a)	левых;	(2)
a
b
f (x)dx (b a) f (b)	правых;	(3)

a

b

f (x)dx (b a) f ((a b)2) центральных. (4)

a

Формулы левых и правых прямоугольников являются точными для многочленов нулевой степени, а формула центральных прямоугольников является точной для многочленов не только нулевой, но и первой степени (s=1).

Однако, для других функций применение формул (2) – (4) не даёт высокой точности. Построение составных квадратурных формул прямоугольников осуществляется следующим образом. Интервал интегрирования разбивается равномерно на p отрезков. Применяя на каждой

части одну из формул (2) – (4), получаем приближенное значение интеграла. Например, составная формула центральных прямоугольников имеет вид:

b	p
f (x)dx I p	h f (a (i 0.5)h) , (5)
a	i 1

где h (b a) p – длина элементарного интервала.

Справедливы следующие оценки							погрешности				формулы (5). Если
f (x) дважды непрерывно дифференцируема, то
I I p			(b a)3					a,b			(6)
			24 p2			f	( ),
или
		(b a)2			b				1
I I p						f (x)dx o (				) .	(7)
			24 p 2						p 2
					a

В (7) выписан главный член погрешности, имеющий порядок p ( s 1) , и второстепенный член, которым при достаточно больших значениях p можно

пренебречь по сравнению с главным при условии, что последний не равен нулю.

16

Пусть f (x) имеет кусочно-непрерывную m -ую производную и f m (x) M m . Тогда справедливы оценки погрешности.

	I I p			(b a)2	M1 , при m 1,	(8)
				4 p
	I I p			(b a)3	M 2 , при m 2 .	(9)
				24 p 2

1.2. Формула трапеций. Заменим подынтегральную функцию f (x) линейной функцией L1 (x) , проведенной через точки a; f (a) и b; f (b) :

L (x) f (a)	x b	f (b)	x a
			b a .
1	a b

Вычисляя определённый интеграл от полученного приближения, получаем квадратурную формулу трапеций, точную для многочленов первой степени

( s 1):

	b	(b a)	f (a) f (b) .
	f (x)dx			(10)
		2
	a

Разбивая отрезок a,b на p равных частей и применяя на каждый из них (10), получаем составную квадратурную формулу трапеций:

	b				h		p 1
			p
I		f (x)dx I			2	f (a) f (b) 2		f (a ih) .
	a						i 1

Для дважды непрерывно дифференцируемых функций следующие оценки погрешности формулы (11)

(11)

f (x) справедливы

I I p

(b a)3

f ( ),

a, b

(12)

12 p 2

(b a)2

b

1

I I p

f (x)dx o (

) .

(13)

12 p 2

p 2

a

Для функций, имеющих кусочно-непрерывную m -ую производную,

имеем оценки

I I p

(b a)2

M1 , при m 1,

(14)

4 p

I I p

(b a)3

M 2 , при m 2 .

(15)

12 p 2

17

1.3. Формула Симпсона. Заменим подынтегральную функцию f (x)

квадратичной функцией (параболой) L2 (x) , проведённой через точки a; f (a) ,
b; f (b) , c; f (c) , где c (a b) 2 :
L (x) f (a)	(x c)(x b)	f (c)	(x a)(x b)	f (b)	(x a)(x c)	.
2	(a c)(a b)		(c a)(c b)		(b a)(b c)

Вычисляя определенный интеграл от полученного приближения, получаем квадратурную формулу Симпсона, точную для многочленов не только второй, но и третьей степени

( s 3):

	b	(b a)	f (a) 4 f (c) f (b) .
	f (x)dx			(16)
		6
	a
	Разбивая отрезок a,b	на p равных частей, и		применяя на каждом

элементе разбиения (16), получаем составную квадратурную формулу Симпсона:

	b				h
			p
I		f (x)dx I			6	f (a)
	a

p

f(b) 4

i 1

p 1

f(a (i 0.5)h) 2

i 1

f (a ih) . (17)

Для подынтегральных функций, имеющих непрерывную четвертую производную, справедливы формулы

	I I p			(b a)5		f (4) ( ),	a, b			(18)
				2880p 4
	I I p		(b a)4		b	f (4) (x)dx o (		1	) .	(19)
			2880p 4					p 2
					a

Для функций, имеющих кусочно-непрерывную m -ую производную, имеем оценки

5

(b a)2

I I p

M1 , при m 1,

(20)

36

p

I I p

(b a)3

M 2 , при m 2 .

(21)

81p 2

I I p

(b a)4

M

3 , при m 3,

(22)

576p

3

I I p

(b a)5

M

4 , при m 4 .

(23)

2880p 4

18

s 2n 1,

		2.	Формулы Гаусса. Пусть рассматривается квадратурная формула с n
узлами
				b		n
			I f (x)dx Aj f (x j ).							(24)
				a		j 1
		Здесь
			Aj	b a	q j ,	x j	a b		b a		t j ,
			2			2				2
q j	;t j	n	- система коэффициентов и			узлов		для		интервала 1;1 , обычно
		j 1

приводимых в справочниках.

В формулах Ньютона - Котеса узлы располагались на одинаковом расстоянии друг от друга, а коэффициенты строились исходя из интерполяционного правила. Можно ли повысить степень точности квадратурной формулы при другом расположении узлов? Какова наивысшая степень точности квадратурной формулы с n узлами?

Можно показать, что для любого n существует единственная квадратурная формула наивысшей алгебраической степени точности

узлы которой различны и расположены на (a, b) , а коэффициенты определяются с помощью интерполяционного правила (формула Гаусса). Приведём значения коэффициентов и узлов для небольших значений n :

n 2 : q1 q2 1;

t1 t2 0,57735026918962576451;

n 3 : q1 q3 0,55555555555555555556;

q2 0,88888888888888888888 ;

t1 t3 0,77459666924148337704;

t2 0 ;

n 4; q1 q4 0,34785484513745385737;

q2 q3 0,65214515486254614263;

t1 t4 0,86113631159405257522 ;

t2 t3 0,33998104358485626480.

19

На основе рассматриваемых правил можно аналогично предыдущему строить составные квадратурные формулы Гаусса:

	b			p	n
	I f (x)dx I p		h	q j f a (i 0.5)h 0.5ht j		. (25)
	a		2 i 1		j 1
Здесь	h (b a) p -	длина			элементарного интервала, на котором

применяется квадратурная формула (4); a (i 0.5)h - центр i -го элементарного интервала.

Если подынтегральная функция имеет непрерывную производную порядка 2n, то справедливы формулы:

I I p		(n!)4		(b a)2n 1			f (2n) ( ),	a, b (26)
		(2n 1)((2n)!)3		p 2n
I I p		(n!)4		(b a)2n	b		f (2n) (x)dx o (		1	) . (27)
		(2n 1)((2n)!)3		p 2n					p 2n
					a

Приведём в качестве примера некоторые оценки для функций, имеющих кусочно-непрерывную m -ю производную, при числе узлов формулы Гаусса n 4.

I I p

6.9 10 2

(b a)2

M

1 , при m 1,

(28)

p

I I p

2.74 10 3

(b a)3

M

2 , при m 2 .

(29)

p 2

I I p

1.48 10 4

(b a)4

M

3 , при m 3,

(30)

p3

I I p

8.44 10 6

(b a)5

M

4 , при m 4 .

(31)

p 4

I I p

5.63 10 6

(b a)9

M 8 , при m 8.

(32).

p8

Как следует из приведённых формул при недостаточной гладкости подынтегральных функций (m=1, 2) простейшая формула Ньютона-Котеса - формула прямоугольников – имеет несколько лучшую оценку погрешности по сравнению с другими составными квадратурными формулами при фиксированном объёме вычислений. Однако, для достаточно гладких подынтегральных функций формулы Гаусса значительно превосходят по точности все другие квадратурные формулы.

20