Незачет – менее 4 заданий Незачет – менее 4 заданий




НазваниеНезачет – менее 4 заданий Незачет – менее 4 заданий
Дата конвертации05.03.2013
Размер445 b.
ТипЗадача



Незачет – менее 4 заданий

  • Незачет – менее 4 заданий

  • Максимум «3» на экзамене – 4 задания

  • Максимум «4» на экзамене – 5 задания

  • Максимум «5» на экзамене – 6 заданий

  • «5» за экзамен автоматом – 7 заданий + дополнительное (первые 3 человека в каждой подгруппе)

  • Освобожден от практики на экзамене – 7 заданий + дополнительное (все, кто не успел стать «первыми 3 в каждой подгруппе»)





Эффективность алгоритма:

  • Эффективность алгоритма:

  • Временная (индикатор скорости работы алгоритма)

  • Пространственная (показывает, сколько для алгоритма требуется оперативной памяти)

  • В основном анализируется временная эффективность.



Временная эффективность (далее просто эффективность) напрямую зависит от размера входных данных.

  • Временная эффективность (далее просто эффективность) напрямую зависит от размера входных данных.

  • Эффективность можно задать функцией от некоторого параметра, связанного с размером входных данных.

  • Пример:

  • Эффективность алгоритма решения задачи сортировки списка зависит от размера списка



Для некоторых задач можно брать разные параметры входных данных.

  • Для некоторых задач можно брать разные параметры входных данных.

  • Пример:

  • Задача перемножение 2-ух матриц размером n на n. 1-ый вариант параметра - это порядок матрицы n, 2-ой вариант - число N =n*n элементов в матрице.



В случае, если на вход алгоритму подается целое число n, принято оценивать размер входных данных по количеству битов b в двоичном представлении числа n.

  • В случае, если на вход алгоритму подается целое число n, принято оценивать размер входных данных по количеству битов b в двоичном представлении числа n.

  • b = + 1

  • Например, для алгоритма возведения целого числа n в квадрат значение эффективности одинаково для чисел 9 и 14 (т.к. число битов двоичного представления этих чисел одно и то же).



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

  • В качестве единицы измерения времени выполнения алгоритма принято использовать не секунды, минуты и пр., а количество операций, выполняемых алгоритмом.

  • При этом считаются не все операции, а лишь основные (которые вносят наибольший вклад в общее время выполнения алгоритма).

  • При анализе эффективности алгоритма необходимо определить, какие операции в нем основные.



Примеры:

  • Примеры:

  • В большинстве алгоритмов сортировки основной операцией является сравнение.

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



Для каждого из приведенных ниже алгоритмов определите 1) естественные единицы измерения входных данных 2) основную операцию алгоритма 3) будет ли изменяться количество основных операций , выполняемых алгоритмом, в зависимости от используемого набора входных данных одинакового размера

  • Для каждого из приведенных ниже алгоритмов определите 1) естественные единицы измерения входных данных 2) основную операцию алгоритма 3) будет ли изменяться количество основных операций , выполняемых алгоритмом, в зависимости от используемого набора входных данных одинакового размера

  • а) вычисление суммы n чисел

  • б) вычисление n!

  • в) поиск наибольшего элемента в списке из n чисел

  • г) алгоритм Евклида

  • д) алгоритм умножения в столбик двух n-разрядных десятичных целых чисел



Основан на 2 утверждениях

  • Основан на 2 утверждениях

  • НОД(m,n) = НОД(n,m mod n)

  • НОД(m,0) = m

  • Пример Найти НОД(12, 8)

  • 12 = 8*1 + 4

  • 8 = 4*2 + 0

  • НОД(12,8) = НОД(8,4) = НОД(4,0)=4



Для алгоритма сложения двух матриц размером n на n

  • Для алгоритма сложения двух матриц размером n на n

  • а) Назовите основную операцию

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

  • Выполните аналогичное упражнение для алгоритма умножения двух матриц размером n на n.



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

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

  • Время выполнения программы T(n) определяется по формуле

  • Данная формула позволяет определить, на сколько изменится время выполнения алгоритма при изменении размера входных данных.



Пусть .

  • Пусть .

  • Если удвоить размер входных данных, то время выполнения алгоритма увеличится в 4 раза, т.к.

  • Заметим, что ответ не зависит от c, поэтому при анализе эффективности алгоритмов сосредотачиваются на оценке порядка роста количества основных операций с точностью до постоянного сомножителя.



Для решения системы из n уравнений (n – произвольное целое число), используется классический алгоритм последовательного исключения Гаусса, в котором выполняется умножений, являющихся основной операцией алгоритма.

  • Для решения системы из n уравнений (n – произвольное целое число), используется классический алгоритм последовательного исключения Гаусса, в котором выполняется умножений, являющихся основной операцией алгоритма.

  • а) Определите, во сколько раз дольше будет работать алгоритм Гаусса для решения системы из 1000 уравнений по сравнений со временем решения из 500 уравнений

  • б) Предположим, вы собираетесь приобрести компьютер, быстродействие которого в 1000 раз превосходит быстродействие того компьютера, на котором вы сейчас работаете. Определите, на сколько порядков большую систему уравнений сможет решить за одно и то же время новый компьютер по сравнению со старым.





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

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

  • Пример.

  • Задача последовательного поиска (поиск заданного элемента k в списке длиной n). В наихудшем случае (когда заданного элемента в списке нет) будет выполнено n операций сравнения. В наилучшем – будет выполнено 1 сравнение.



Сложность алгоритма в наихудшем (наилучшем) случае – сложность для таких входных данных, на которых время работы алгоритма будет наибольшим (наименьшим).

  • Сложность алгоритма в наихудшем (наилучшем) случае – сложность для таких входных данных, на которых время работы алгоритма будет наибольшим (наименьшим).



В ящике хранится 22 перчатки: 5 пар красных, 4 пары желтых и 2 пары зеленых. Предположим, что вы выбираете их в темноте наугад и можете проверить, что именно вы выбрали, только после того, как выбор сделан. Чему равно минимальное количество перчаток, которое надо взять из ящика, чтобы получить как минимум одну пару перчаток (т.е. левая + правая) одинакового цвета?

  • В ящике хранится 22 перчатки: 5 пар красных, 4 пары желтых и 2 пары зеленых. Предположим, что вы выбираете их в темноте наугад и можете проверить, что именно вы выбрали, только после того, как выбор сделан. Чему равно минимальное количество перчаток, которое надо взять из ящика, чтобы получить как минимум одну пару перчаток (т.е. левая + правая) одинакового цвета?

  • а) Дайте ответ на этот вопрос для наилучшего и наихудшего случая.

  • б) Дайте ответ для наилучшего и наихудшего случая для варианта, в котором нужно получить как минимум две перчатки одинакового цвета (не обязательно пару)



  • Факт где С - константа

  • обозначается так: , это значит что функции f(x) и g(x ) имеют один и тот же порядок роста





  • На практике при поиске класса сложности можно отбрасывать слагаемые, которые представляют функции меньшего порядка роста.

  • Примеры:

  • а) 5n + 3 = O(n), т.к.

  • б) , т.к.



  • Для каждой из приведенных ниже функций укажите порядок роста и класс сложности.

  • а)

  • б)

  • в)



Общий план анализа сложности нерекурсивных алгоритмов:

  • Общий план анализа сложности нерекурсивных алгоритмов:

  • 1. Выберите параметр (или параметры), по которому будет оцениваться размер входных данных алгоритма.

  • 2. Определите основную операцию

  • 3. Определите сложность алгоритма в наихудшем случае

  • 3.1. Запишите сумму, выражающую количество выполняемых основных операций алгоритма

  • 3.2. Упростите формулу (используя правила суммирования), и определите, к какому классу сложности относится полученная функция

  • 4. Определите сложность в наилучшем случае (если она не совпадает с наихудшей)



Важные правила и формулы суммирования:

  • Важные правила и формулы суммирования:



Пример 1. Задача поиска наибольшего элемента в массиве из n чисел.

  • Пример 1. Задача поиска наибольшего элемента в массиве из n чисел.

  • maxval := a[0];

  • for i := 1 to n-1 do

  • if ( a[i] > maxval ) then

  • maxval := a[i];

  • Размер входных данных = n, основная операция = сравнение, сложность в наихудшем и наилучшем случае одинаковая.

  • Ответ: сложность алгоритма линейная



Пример 2. Задача проверки уникальности элементов в массиве из n чисел.

  • Пример 2. Задача проверки уникальности элементов в массиве из n чисел.

  • for i := 0 to n-2 do

  • for j := i + 1 to n-1 do

  • if ( a[i] = a[j] ) then

  • return false;

  • return true;

  • Основная операция = сравнение.

  • Размер входных данных = n

  • Сложность в наихудшем и наилучшем случае различная



  • Ответ: сложность алгоритма в наихудшем случае квадратичная, в наилучшем - константная



Пример 3. Задача умножения двух квадратных матриц размером n на n.

  • Пример 3. Задача умножения двух квадратных матриц размером n на n.

  • for i := 0 to n-1 do

  • for j := 0 to n-1 do

  • begin

  • С[i,j] := 0.0;

  • for k := 0 to n-1 do

  • С[i,j] := С[i,j] + A[i,k] * B[k,j];

  • end;

  • Основная операция = умножение.

  • Размер входных данных = n



Определите сложность в наихудшем и наилучшем случае

  • Определите сложность в наихудшем и наилучшем случае



В массиве A(n) подсчитать количество отрицательных и сумму положительных элементов.

  • В массиве A(n) подсчитать количество отрицательных и сумму положительных элементов.

  • От каждого из m чисел x1 … xm отнять их среднее арифметическое.

  • Дан массив A(n). Все нулевые элементы этого массива поместить в начало массива B(n). Подсчитать количество нулевых элементов.



Похожие:

Незачет – менее 4 заданий Незачет – менее 4 заданий iconЕгэ по математике Демоверсия 2012 года
Несколько изменен порядок заданий части в (в соответствии со сложностью заданий)
Незачет – менее 4 заданий Незачет – менее 4 заданий iconПодходы к проверке заданий части С
Проблемы, в основном, сводятся к тому, что ответы экзаменуемых подчас не укладываются в спроектированные разработчиками заданий критерии...
Незачет – менее 4 заданий Незачет – менее 4 заданий iconПроработавшие в занимаемой должности менее 1 года; проработавшие в занимаемой должности менее 1 года
Число независимых экспертов должно составлять не менее одной четверти от общего числа членов аттестационной комиссии
Незачет – менее 4 заданий Незачет – менее 4 заданий iconГлавные элементы новизны экзаменационной модели 2012 г.: Главные элементы новизны экзаменационной модели 2012 г
Ким и сокращено число заданий репродуктивного характера сокращено с 27 до 21 число заданий с выбором ответа, с 15 до 12 число заданий...
Незачет – менее 4 заданий Незачет – менее 4 заданий iconСостав заданий егэ по теме «основы логики»
Вывод: успешная подготовка учащихся к выполнению заданий егэ возможна только в следующих случаях
Незачет – менее 4 заданий Незачет – менее 4 заданий iconИзменено количество заданий с выбором ответа с 3 до 7 и количество заданий с кратким ответом с 14 до 9

Незачет – менее 4 заданий Незачет – менее 4 заданий iconДля испытаний следует использовать площадку с минимальными размерами 100x100 м с примыкающей к ней разгонной полосой длиной не менее 1000 м и шириной не менее 7 м

Незачет – менее 4 заданий Незачет – менее 4 заданий iconГрафик проведения испытания на сайте ккидппо
Интернет; выполнение заданий частиАиВ на компьютере; получение протокола о результатах тестирования на компьютере; выполнение заданий...
Незачет – менее 4 заданий Незачет – менее 4 заданий iconВиды заданий: Виды заданий
В целях усиления, отдельные слова могут выделяться длительностью звучания ударного звука, усилением голоса, повторением одного и...
Незачет – менее 4 заданий Незачет – менее 4 заданий iconУрок 1 Отбор и группировка статистических данных
Администрация школы решила проверить математическую подготовку восьмиклассников. С этой целью был составлен тест, содержащий 9 заданий....
Разместите кнопку на своём сайте:
hnu.docdat.com


База данных защищена авторским правом ©hnu.docdat.com 2012
обратиться к администрации
hnu.docdat.com
Главная страница