02-resource1 (1238872)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

ВРЕМЯ И ПАМЯТЬАсимптотическая сложность алгоритмовВремя и память как ресурсыК. Владимиров, Intel, 2019mail-to: konstantin.vladimirov@gmail.comСнова алгоритм F•Как оценить время работы этой функции?unsigned long long fib (unsigned n) {unsigned long long first = 0ull;unsigned long long second = 1ull;int idx;if (n == 0) return 0ull;for (idx = 2; idx <= n; ++idx) {unsigned long long tmp = second;second = second + first;first = tmp;}return second;}Снова алгоритм F•Самый очевидный способ − подсчитатьunsigned long long fib (unsigned n) {unsigned long long first = 0ull;unsigned long long second = 1ull;int idx;if (n == 0) return 0ull;for (idx = 2; idx <= n; ++idx) {unsigned long long tmp = second;second = second + first;first = tmp;}return second;}//////////////////////ta + teta + tetatbta + n * (tc + tp) + tbn * (ta + te)n * (tp + te)n * ten * tbtbИтого: k1 + n*k2Обсуждение•Итак, время исполнения алгоритма F составляет 1 + 2 •Здесь это номер вычисленного числа Фибоначчи•От чего зависят значения 1 и 2 ?Обсуждение•Итак, время исполнения алгоритма F составляет 1 + 2 •Здесь это номер вычисленного числа Фибоначчи•От чего зависят значения 1 и 2 ?•••Быстродействие компьютера (laptop vs supercomputer)Архитектура микропроцессора, в частности насколько дорогой branch и какие тамвнутри детали реализации подсистем памяти и арифметики/логикиКачество компилятора и линкера (насколько оптимизирован код)Обсуждение•Итак, время исполнения алгоритма F составляет 1 + 2 •Здесь это номер вычисленного числа Фибоначчи•От чего зависят значения 1 и 2 ?•••Быстродействие компьютера (laptop vs supercomputer)Архитектура микропроцессора, в частности насколько дорогой branch и какие тамвнутри детали реализации подсистем памяти и арифметики/логикиКачество компилятора и линкера (насколько оптимизирован код)•На практике мы часто не знаем и знать не можем большую часть этихпараметров•Но мы всегда знаем наш главный параметр Снова наивный подход•Для примера оценим выполнение при наивном подходеunsigned long long fib (unsigned n) {if (n == 0) return 0ull;if (n <= 2) return 1ull;return fib(n - 1) + fib(n - 2);}15// // // + вызовов функции и общее время 3 •Имеем ровно•Первая мысль при сравнении 1 + 2 против 3 это: а есть ли вообщеразница какие значения имеют 1 , 2 , 3 ?•При достаточно большом , всегда 1 + 2 < 3 O-нотация•Базовая интуиция, что при достаточно большом n, выполняется6 < 4 + 5 log() < 1 + 2 < 3 1.61•Получает своё развитие в O-нотации = ↔ ∃, | ∀ > , ∙ ≥ ()O-нотация•Базовая интуиция, что при достаточно большом n, выполняется6 < 4 + 5 log() < 1 + 2 < 3 1.61•Получает своё развитие в O-нотации = ↔ ∃, | ∀ > , ∙ ≥ ()•Например 2 3 + 14 2 + 87 + 3 = 3•О-нотация не слишком строгая.

Например то же выражение это также 4•Говорят, что O-нотация отражает асимптотику зависимости ресурса(например времени работы алгоритма) от главного параметра в задаче(например номера числа Фибоначчи)O-нотация11111113д1061115м101010c2м3г10142ч28ч()10150Упражнения с асимптотикой•Оцените асимптотику следующих выражений + log + sin()5log2 + 2 100 + 1.1•Расположите выражения по возрастанию порядка роста3 log 2 log 4 2log5 222Problem LM – наименьшее кратное•Число 2520 является наименьшим числом, которое делится без остатка начисла от 2 до 10•Задача состоит в том, чтобы найти наименьшее число, которое делится безостатка на числа от 2 до N•Вам предлагают наивный алгоритм: идти от числа N вверх и каждоевстретившееся число проверять для каждого из N чисел.

(см. lmnaive.c)•Оцените асимптотику наивного алгоритма•Подумайте, можно ли использовать алгоритм E для лучшего решения этойзадачи?•Математический инсайт: , =gcd ,и , , = ( , , )Warmup: простые числа•Определение ⇔ ∃, = 1 ⇔ ∄, ≠ ∩ ≠ ∩ \p•Мнемоническое правило "делитсятолько на единицу и на само себя"•Но строго говоря в целых числах unitsэто 1 и -1•Значит реально ещё на -1 и на минуссамо себяАлгоритм P, первое приближение•Простейший способ определить, является ли число простымint is_prime(unsigned n) {if (n < 2) return 0;int last = (int) sqrt(n) + 1;for (int j = 2; j <= last; ++j)if ((n % j) == 0)return 0;return 1;}•Оцените асимптотику этого алгоритма по времениАлгоритм P, первое приближение•Простейший способ определить, является ли число простымint is_prime(unsigned n) {if (n < 2) return 0;int last = (int) sqrt(n) + 1;for (int j = 2; j <= last; ++j)if ((n % j) == 0)return 0;return 1;}•Асимптотическая сложность .

Кажется, этот алгоритм можно улучшитьАлгоритм P, второе приближение•Используем тот факт, что чётные всегда не простые кроме 2int is_prime(unsigned n) {if (n == 2) return 1;if ((n < 2) || ((n % 2) == 0)) return 0;int last = (int) sqrt(n) + 1;for (int j = 3; j <= last; j += 2)if ((n % j) == 0)return 0;return 1;}•Скорость превосходит первое приближение вдвое. Асимптотика?Алгоритм P•Используем тот факт, что простые всегда имеют вид 6 ± 1int is_prime(unsigned n) {if ((n == 2) || (n == 3)) return 1;if ((n < 2) || ((n % 2) == 0) || ((n % 3) == 0)) return 0;int last = (int) sqrt(n) + 1;for (int j = 5; j <= last; j += 6)if (((n % j) == 0) || ((n % (j + 2)) == 0))return 0;return 1;}•Скорость превосходит первое приближение втрое. Асимптотика?Обсуждение•Асимптотическая сложность не измеряет время выполнения задачи.•Она измеряет то, как изменяется время выполнения при изменении входныхданныхProblem PN – N-ное простое число•Первым простым числом является 2, шестым является 13•Используйте алгоритм P чтобы вычислить N-е простое число•Вычислите для начала N = 1000, потом увеличивайте.•До какого числа вы сможете досчитать в пределах 60 секунд (используйтеulimit)?•Сможете ли вы использовать для оптимизации идеи, использованные дляоптимизации алгоритма P?•Оцените асимптотику вашего решенияОбсуждение•Пока что речь шла только об одном ресурсе − времени•Но бывают и другие ресурсы.

Ваши предположения?Обсуждение•Пока что речь шла только об одном ресурсе − времени•Но бывают и другие ресурсы:•••••ПамятьОбъём пересылаемых по сети данныхСложность разработки в человеко-часахСтоимость лицензий для подключаемых сторонних библиотекЭнергопотребление компьютера•Память выделена потому что это второй по важности ресурс после времени•Разумеется память это ресурс только в языках с явным управлением памятью.К счастью язык C из этихПростые числа: решето Эратосфена2345678910111213141516234567891011121314151623456789101112131415162345678910111213141516•Вычеркиваются все числа кратные каждому простому. Следующее простоеэто ближайшее невычеркнутое.Проектирование решета: структуры•Решето это объединение его размера с указателем на память. Объединениятипов называются структурами.struct sieve_t {unsigned size;unsigned char *sieve;};•Использованиеstruct sieve_t s = init_sieve(100); // для чисел от 0 до 100assert (s.sieve != NULL && s.size > 0);int is63 = is_prime(s, 63); // проверяем простое ли число 63Минимум о структурах•Структура задаётся ключевым словом struct и содержит поля разных типовstruct S { int x; int y; char z; };•Объект структуры можно инициализировать при первом определенииstruct S t = {1, 2, 'a'};•Доступ к полям структуры делается через точкуt.x = t.y + 1;assert (t.x == 3);•Возможен указатель на структуру, тогда обращаемся через стрелку.struct S *pt = &t; assert (pt->x == 3);Алгоритм S: построение решетаstruct sieve_t init_sieve (unsigned n) {unsigned char *sieve = calloc(n, sizeof(unsigned char));struct sieve_t res = { n, sieve };assert ((n > 1) && (sieve != NULL));unsigned r = (unsigned) sqrt (n) + 1;res.sieve[0] = res.sieve[1] = 1;// напишите здесь код, который для каждого i устанавливает// res.sieve[i] = 1, если число составноеreturn res;}Оцените асимптотическую сложностьполучившегося алгоритмаОсвобождение памяти•После использования решета следует освободить выделенную через callocпамятьvoid free_sieve(struct sieve_t *s) {free(s->sieve);s->sieve = 0;s->size = 0;}•Все ли понимают почему сюда решето пришло по указателю?Проверка с помощью решета•Поскольку решето содержит 1 для составных и 0 для простых, на проверке,надо инвертировать логикуunsigned is_prime (struct sieve_t s, unsigned n) {assert (n < s.size);return (s.sieve[n] == 1) ? 0 : 1;}•Использован тернарный оператор a ? b : c•Означает "если a, то b, иначе c".

Более короткая форма, когда не хочетсяписать if.Сводим всё вместе•Выделить решето на 100 элементовstruct sieve_t s = init_sieve(100);•Проверить число 97 с помощью решетаassert (is_prime(s, 97) == 1);•Освободить решетоfree_sieve(&s);Problem PS – снова N-е простое•Чтобы вычислить N-е простое число для N > 20, с помощью решета, нужнопостроить решето до числа log + log log unsigned long long sieve_bound(unsigned num) {assert(num > 20);double dnum = num;double dres = dnum * (log(dnum) + log(log(dnum)));return (unsigned long long) round(dres);}•Сравните результаты с результатами задачи PN•Замерьте до какого числа вы сможете дойти за 60 секундProblem GF – генерирующие формулы•Эйлер открыл потрясающую формулу 2 + + 41.•Она генерирует для 0 ≤ ≤ 39, 40 последовательных простых чисел.•Ещё более потрясающая формула 362 − 810 + 2753 генерирует 45последовательных простых (http://oeis.org/A050268)•Используйте компьютер, чтобы рассмотреть все формулы, вида2 + + , < 1000, < 1000•Какую самую длинную последовательность простых чисел вы сможетесгенерировать?•Оптимизируйте алгоритм, отсекая заведомо плохие b (для n=0, число сразудолжно быть простым).Работа с битами•Минимальной адресуемой единицей в языке C является байт•Но что если есть необходимость работать с отдельными битами внутрибайта?••••Установить бит под номером n в числе x в значение 0 или 1Считать значение бита под номером n в числе xИнвертировать бит под номером n в числе xМожно ли использовать для этого обычную арифметику? В принципе да, ноэто выглядит крайне странноx = (y / pow(2, n)) % 2; // x = nth bit value in yОсновы битовой арифметики•Установить бит под номером n в числе x в значение 1x = x | (1u << n);•Установить бит под номером n в числе x в значение 0x = x & ~(1u << n);•Считать значение бита под номером n в числе xval = (x >> n) & 1u;•Инвертировать бит под номером n в числе xx = x ^ (1u << n);Тренируемся в битовой арифметике•Подсчитайте0xAC & 0x28 = ?0xE2 | (~0xEF) = ?075 & 063 = ?62 ^ 43 = ?0b10100 ^ 0 = ?0x23 >> 2 = ?0x23 << 4 = ?Длинные и короткие операции•Важно не путать длинные (логические) с короткими (побитовыми)операциямиunsigned char c = 0x78;if (c && 1) { printf("long"); } // логическое "и"if (c & 1) { printf("short"); } // побитовое "и"•Какая логическая операция соответствует побитовому исключающему или?Обмен битов•Дано число x и необходимо поменять в нём местами i-й и j-й (напримертретий и седьмой) биты.

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций