Контрольные вопросы к главе 1

Контрольные вопросы к главе 1

1.  Дайте определение терминам «алгоритм» и «алгоритмический процесс».

2.  Сформулируйте основные задачи теории алгоритмов.

3.  В чём заключается теоретический аспект теории алгоритмов?

4.  В чём заключается практический аспект теории алгоритмов?

5.  Перечислите основные свойства алгоритмов и дайте их интерпретацию.

6.  Дайте характеристику понятия «корректность алгоритма».

7.  Какие существуют методы доказательства корректности алгоритмов?

8.  Какие известны классические теории алгоритмов?

9.  Что такое алгоритмически неразрешимые проблемы? Приведите примеры.

10.  Какие существуют методы описания алгоритмов?

Контрольные вопросы к главе 2

1.  Дайте характеристику понятия «сложность алгоритма».

2.  Поясните смысл оценки сложности алгоритмов в терминах O – нотации.

3.  В чём заключается отличие P и NP классов алгоритмов?

4.  Какие аналитические функции используются для оценки скорости роста сложности алгоритмов?

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

6.  Какова сложность рекурсивных алгоритмов?

7.  Как оценивается сложность линейно-независимых последовательных фрагментов программы?

8.  Как оценить сложность вложенных циклов в программе?

9.  Какое влияние оказывают константы в формулах оценки сложности алгоритма?

10.  Дайте характеристику алгоритмов, обладающих логарифмической сложностью.

Задачи

Задача 1. Используя O - символику найти время выполнения процедуры в наихудшем случае, как функции от N.

Procedure mystery(n:integer);

var i, j,k:integer;

Begin

for i:=1 to n-1 do

for j:=i+1 to n do

for k:=1 to j do

begin

{группа операторов с общим временем выполнения O(1)}

end;

End;

Задача 2. Используя O - символику найти время выполнения процедуры в наихудшем случае, как функции от N.

Procedure veryodd(n:integer);

var i, j,x, y:integer;

Begin

for i:=1 to n do

if odd(i)then {проверка на четность}

begin

for j:=1 to n do

x:=x+1;

for j:=1 to i do

y:=y+1;

end;

End;

Задача 3. Расположить функции в порядке роста степени сложности и показать графически их временную сложность:

1) N; 2) ; 3) log(N); 4) log(log(N)); 5) log2N;

6) N/log(N); 7) ×log2N; 8) ; 9) 10) 17N0

Задача 4. Используя W и O - символику найти верхнюю и нижнюю границы для временной сложности Т(N) в простом виде для функции, которая возвращает наибольший из элементов, стоящих в позициях от i до i+N-1 в целочисленном массиве А, допуская что N=2m.

Function max(i, n:integer):integer;

var m1, m2: integer;

Begin

if n=1 then Result:= A[i]

else

begin

m1:=max(i, n div 2);

m2:=max(i+n div 2, n div 2);

if m1<m2 then Result:= m2

else Result:= m1;

end;

End;

Задача 5. Определить вычислительную сложность T(N) рекурсивного алгоритма нахождения N-го числа Фибоначи (известно, что Fn=Fn-1+Fn-2). Определить порядок роста сложности в терминах О - нотации. Построить быстрый алгоритм расчета чисел Фибоначи.

Function Fibonacci(n:integer):longint;

Begin

if (n=0) then Result:=0

elseif (n=1) then Result:=1

else Result:=Fibonacci(n-1)+Fibonacci(n-2);

End;

Задача 6. Определить вычислительную сложность T(N) алгоритма и оценить

порядок роста сложности в терминах О - нотации, полагая, что а - целое число.

Function power(a, n:integer):longint;

Begin

if (n=0) then Result:=1;

x:=power(a, n div 2);

if (n-четное) then Result:=x*x

else Result:=a*x*x;

End;

Задача 7. Построить алгоритм вычисления функции f(x)=NN cо сложностью порядка O(log N).

Задача 8. Построить алгоритм вычисления функции f(x)=2M, где M=2N cо сложностью порядка O(N).

Задача 9. Определить временную сложность умножения двух N-разрядных чисел f(N, b)=x*y в системе счисления по основанию

b -->(10; 8; 2), используя алгоритм циклического сложения, например,

5*4=5+5+5+5, и учитывая, что сложение/умножение одного разряда числа имеет сложность O(1).

Задача 10. Определить временную сложность умножения двух больших N-разрядных чисел f(N)=x*y в десятичной системе счисления, используя алгоритм представления числа в показательной форме, например,

127*211=127*1+127*10+127*200, и учитывая, что сложение/умножение одного разряда числа имеет сложность O(1).

Контрольные вопросы к главе 3 «Методы разработки алгоритмов»

1.  Дайте сравнительную характеристику метода «подъёма» и метода «разделяй и властвуй» разработки быстрых алгоритмов.

2.  В чём заключается смысл балансировки при разделении задач на подзадачи в методе «разделяй и властвуй»?

3.  В чём суть метода «программирование с отходом назад»?

4.  В чём сходство и отличия методов «вершин и границ», «αβ –отсечения» и «программирование с отходом назад»?

5.  Что такое «эвристика»? Дайте характеристику эвристическим алгоритмам.

6.  В чём заключается метод динамического программирования?

7.  Поясните смысл «жадной» стратегии при разработке алгоритмов.

Задачи

Задача 1. Постройте быстрый алгоритм умножения N матриц произвольных размеров.

Задача 2. Постройте алгоритм сортировки пяти произвольных чисел a, b,c, d,e, используя не более семи операций сравнения.

Задача 3. Построить алгоритм проверки, является ли заданная последовательность чисел периодической, и определения периода повторения чисел.

Задача 4. Палиндром – такое сочетание цифр, которые читаются одинаково слева направо и справа налево. Например, 121, 55, 4884. Построить алгоритм нахождения всех палиндромов в заданном диапазоне от А до С.

Задача 5. Счастливым будем считать такое число из шести цифр, в котором сумма левых трех цифр равна сумме правых трех цифр. Например, 457961 = > (4+5+7=9+6+1). Построить алгоритм поиска всех шестизначных счастливых чисел и определить их количество.

Задача 6. Найти все совершенные числа в интервале от А до С. Совершенным называется натуральное число, которое равно сумме своих делителей, за исключением самого числа, например: 28=1+2+4+7+14

Задача 7. Найти все дружественные числа в заданном интервале от А до С. Дружественными числами называются пара натуральных чисел M и N, для которых сумма всех делителей числа M (кроме самого числа M) равна N, а сумма всех делителей числа N (кроме самого числа N) равна M. Например, числа 220 и 284 – дружественные. Сумма делителей числа 220: 1+2+4+5+10+11+20+22+44+55+110=284, а сумма делителей числа 284: 1+2+4+71+142=220

Задача 8. Разложить число N на простые делители, подсчитав при этом, сколько раз встречается один и тот же простой делитель, а также вычислить сумму этих делителей.

Задача 9. Дано натуральное число N. Предполагается, что имеются монеты достоинством 1, 2, 5, 10, 20, 50, 100 рублей. Построить алгоритм размена числа N наименьшим числом монет.

Задача 10. Получить все M – значные натуральные числа в записи которых нет двух (и более) одинаковых цифр. Подсчитать их количество.

Задача 11. Построить алгоритм получения всех натуральных чисел Nm в заданном диапазоне от А до С, таких, что Nm=i2+j2, где i, j – натуральные числа, меньшие N. Например, 25 = 32+42.

Задача 12. Построить алгоритм получения всех натуральных чисел Nm в заданном диапазоне от А до С, таких, что Nm=i3+j3, где i, j – натуральные числа, меньшие N. Например, 9 = 23+13.

Задача 13. Построить алгоритм поиска для заданного числа N такого наименьшего числа S, что S=aN+bN.

Задача 14. Определить частоты вхождения в число N! (N<=100) всех цифр из которых состоит значение N!.

Задача 15. Найти все такие числа N (N<=100), что у числа N! Сумма цифр – простое число.

Задача 16. Найти все такие числа N (N<=100), что у числа N! Сумма цифр – квадрат целого числа.

Задача 17. Построить алгоритм получения всех перестановок для заданных M натуральных чисел. Например: (1,2,3), (2,1,3), (2,3,1), (1,3,2), (3,1,2), (3,2,1).

Задача 18. Построить алгоритм получения всех сочетаний из N чисел по M в группе. Например, для трех чисел 1,2,3 группы по два: (1,2), (1,3), (2,3)

Задача 19. Построить алгоритм получения магического квадрата N*N, состоящего из чисел от 1 до N2.

Задача 20. Построить алгоритм умножения двух много разрядных целых чисел из M и N разрядов (M, N>20).

Задача 21. Построить алгоритм перевода чисел из одной системы счисления с основанием N в другую с основанием M (N, M<=16).

Задача 22. Построить рекурсивный алгоритм поиска минимального элемента в массиве из N чисел.

Задача 23. В заданном интервале от А до С найти все парные простые числа. Парными простыми числами называют два простых числа, разность между которыми равна 2. Например, 3 и 5, 11 и 13, 17 и 19 и т. д.

Задача 24. Найти все трехзначные числа, сумма цифр которых равна заданному числу N.

Задача 25. Число Армстронга – такое число из k цифр, для которого сумма k-х степеней его цифр равна самому числу. Например, 153=13+53+33. Построить алгоритм получения всех чисел Армстронга для двух, трех и четырех цифр.

Контрольные вопросы к главе «генетические алгоритмы»

1.  Какие алгоритмы относят к классу генетических?

2.  В чем заключается принцип эволюции в генетических алгоритмах?

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

4.  В чем отличие генетических алгоритмов от эволюционных программ?

5.  Как происходит формирование решения в генетическом алгоритме?

6.  Для каких задач применение генетических алгоритмов оказывается эффективным?

7.  Какова вычислительная сложность генетических алгоритмов?

8.  Какими вычислительными параметрами характеризуются генетические алгоритмы?

9.  В чем заключаются операторы мутации и скрещивания в генетических алгоритмах?

10.  Каковы особенности эволюционных стратегий?

11.  Как влияет параметр «время жизни индивидов» на размер популяции?

12.  Как формируется функция оценки пригодности индивидов в генетических алгоритмах?

13.  Как влияет параметр «число генераций» на точность решения?

14.  В чём заключается принцип элитизма в генетических алгоритмах?

15.  Приведите примеры задач в которых можно применить генетические алгоритмы и эволюционные программы?

Контрольные вопросы к главе «Параллельные алгоритмы»

1.  Что такое параллельные алгоритмы?

2.  Какова вычислительная сложность параллельных алгоритмов?

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

4.  Какие требования предъявляют параллельные алгоритмы к вычислительным ресурсам?

5.  Дайте сравнительный анализ последовательных и параллельных алгоритмов.

6.  Какие различают виды средств распараллеливания алгоритмов и в чём заключаются их отличительные особенности?

7.  Дайте характеристику модели параллельных вычислений «fork-join».

8.  Приведите основные характеристики спецификаций MPI и OpenMP для распараллеливания алгоритмов.

9.  В чём заключается представление алгоритма решения задачи в виде информационного графа по отношению к модели параллельных вычислений?

10.  Назовите основные проблемы, возникающие при распараллеливании последовательных алгоритмов.

11.  В чём заключается зависимость по управлению между операторами в последовательном алгоритме?

12.  В чём заключается зависимость по данным между операторами в последовательном алгоритме?

13.  Приведите примеры параллельных алгоритмов в виде K – схем.

14.  В чём заключаются методы распараллеливания циклов?

15.  Какие фрагменты последовательной программы подвергаются распараллеливанию?