Вложенные отображения

Всем тем, кто осилил: Cвойство замыкания, на примере list и Иерархические структуры посвящается....
Мы разобрались как создавать абстрагированные последовательности, узнали приемы работы с ними. пришло время отчеркнуть линию и применить знания на примере!
Задача(для тех кто осилил еще и Простые числа вместе с Тест простоты =):
Пусть дано положительное целое число n; найти все такие упорядоченные пары различных целых чисел i и j, где 1 ≤ j < i ≤ n, что i+j является простым.
*-Нравится статья? Кликни по рекламе! :)

Иерархические структуры

Эта заметка является логическим продолжением статьи: Cвойство замыкания, на примере list. Представление последовательностей в виде списков естественно распространить на последовательности, элементы которых сами могут быть последовательностями. Например, мы можем рассматривать объект ((1,2) 3, 4), получаемый с помощью ((1,2),(3, 4)). Как список с тремя членами, первый из которых сам является списком. В сущности, это подсказывается формой, в которой результат печатается интерпретатором. Еще один способ думать о последовательностях последовательностей — деревья (trees). Элементы последовательности являются ветвями дерева, а элементы, которые сами по себе последовательности — поддеревьями. Рисунок снизу показывает структуру в виде дерева.
*-Нравится статья? Кликни по рекламе! :)

Cвойство замыкания, на примере list

Все знают такую структуру в разных языках как список(однонаправленный). Многие даже знают, как происходит работа с ним в недрах компутера. Здесь я хотел бы показать это на пальцах. Воссоздав этот список искуственно.

Пример взят из Lisp и искусственно спроецирован на Python.
Для реализации конкретного уровня абстракции данных в Lisp имеется составная структура, называемая парой (pair), и она создается с помощью элементарной процедуры cons(мы вместо cons будем использовать кортеж из 2-х элементов). Эта процедура принимает два аргумента и возвращает объект данных, который содержит эти два аргумента в качестве частей. Имея пару, мы можем получить ее части с помощью элементарных процедур car и cdr.
*-Нравится статья? Кликни по рекламе! :)

Нахождение неподвижных точек функций

Число x называется неподвижной точкой (fixed point) функции f, если оно удовлетворяет уравнению f(x) = x. Для некоторых функций f можно найти неподвижную точку, начав с какого-то значения и применяя f многократно:

f(x), f(f(x)), f(f(f(x))), . . .

— пока значение не перестанет сильно изменяться.

*-Нравится статья? Кликни по рекламе! :)

Нахождение корней уравнений методом половинного деления

Метод половинного деления (half-interval method) — это простой, но мощный способ нахождения корней уравнения f(x) = 0, где f — непрерывная функция. Идея состоит в том, что если нам даны такие точки a и b, что f(a) < 0 < f(b), то функция f должна иметь по крайней мере один ноль на отрезке между a и b. Чтобы найти его, возьмем x, равное среднему между a и b, и вычислим f(x). Если f(x) > 0, то f должна иметь ноль на отрезке между a и x. Если f(x) < 0, то f должна иметь ноль на отрезке между x и b. Продолжая таким образом, мы сможем находить все более узкие интервалы, на которых f должна иметь ноль. Этот прием мы уже использовали в статье: Двочный (бинарный) поиск элемента в массиве.
*-Нравится статья? Кликни по рекламе! :)

Возведение в степень

Рассмотрим задачу возведения числа в степень. Нам нужна процедура, которая, приняв в качестве аргумента основание b и положительное целое значение степени n, возвращает bⁿ. Один из способов получить желаемое — через рекурсивное определение

которое прямо переводится в процедуру:
*-Нравится статья? Кликни по рекламе! :)

Порядок роста

Те, кто часто решает алгоритмические задачи, знают, что решить их можно по-разному и, что процессы могут значительно различаться по количеству вычислительных ресурсов, которые они потребляют. Удобным способом описания этих различий является понятие порядка(скорости) роста, которое дает общую оценку ресурсов, необходимых процессу при увеличении его входных данных.
*-Нравится статья? Кликни по рекламе! :)

Динамическое программирование: размен денег

Это запись -  пример выгодного использование рекурсии. Тем, кто еще не ознакомился, советую прочитать - Линейные рекурсия и итерация. Чего не хватает Python. Я считаю, что именно в тематике динамического программирования рекурсия побеждает всех, как говорится "в шлемах и без" :) Тут я хочу рассмотреть всем известную(а может и не всем, раз вы читаете) задачу размена денег. У неё есть несколько интерпретаций, таких как:

1. Как дать сдачу определенной суммы, определенным набором монет
2. Сколькими способами конь может дойти до определенного места на шахмотной доске.
3. И др.....

*-Нравится статья? Кликни по рекламе! :)

Линейные рекурсия и итерация. Чего не хватает Python

Рассмотрим эти 2 процесса на примере(рассмотренного мной ранее) вычисления факториала. Мы можем вычислить n!, вычислив сначала (n − 1)!, а затем умножив его на n. После того, как мы добавляем условие, что 1! равен 1, это наблюдение можно непосредственно перевести в процедуру. В рекурсивной реализации это выглядит следующим образом.

*-Нравится статья? Кликни по рекламе! :)

Вычисление квадратного корня методом Ньютона

Процедуры очень похожи на обыкновенные математические функции. Они устанавливают значение, которое определяется одним или более параметром. Но есть важное различие между математическими функциями и компьютерными процедурами. Процедуры должны быть эффективными.
В качестве примера рассмотрим задачу вычисления квадратного корня. Мы можем определить функцию «квадратный корень» так:

*-Нравится статья? Кликни по рекламе! :)

Формулирование абстракций с помощью процедур высших порядков

Тут описана идея, важнейшая для любого программиста. Это то, как должен работать мозг у человека создающего такие вещи, как информационные структуры. Идеология приведена из книги "Структура и интерпретация компьютерных программ", Харольда Абельсона и Джеральда Джей Сассмана.

*-Нравится статья? Кликни по рекламе! :)

Тест простоты

Тест простоты — алгоритм, который по заданному натуральному числу определяет, простое ли это число. Различают детерминированные и вероятностные тесты.
Определение простоты заданного числа в общем случае не такая уж тривиальная задача. Только в 2002 году было доказано, что она полиномиально разрешима. Тем не менее, тестирование простоты значительно легче факторизации заданного числа.

*-Нравится статья? Кликни по рекламе! :)

Простые числа

Просто́е число́ — это натуральное число, которое имеет ровно два различных натуральных делителя: единицу и самого себя. Все остальные числа, кроме единицы, называются составными.

Простые способы нахождения начального списка простых чисел вплоть до некоторого значения дают Решето Эратосфена, решето Сундарама и решето Аткина.

*-Нравится статья? Кликни по рекламе! :)

Перевод целых чисел из десятичной системы счисления в двоичную

Тут, конечно писать особо и нечего, просто раз уж показали метод в университете, решил поделиться. Будет продемонстрированно 2 метода: общеизвестный и основанный на логических операциях.

Двоичная система счисления — это позиционная система счисления с основанием 2. В этой системе счисления числа записываются с помощью двух символов (1 и 0).
Сначала, немного применения:

Двоичная система используется в цифровых устройствах, поскольку является наиболее простой и соответствует требованиям:
*-Нравится статья? Кликни по рекламе! :)

Двоичный (бинарный) поиск элемента в массиве

Двоичный (бинарный) поиск (также известен как метод деления пополам и дихотомия) — классический алгоритм поиска элемента в отсортированном массиве (векторе). Используется в информатике, вычислительной математике и математическом программировании.
Частным случаем двоичного поиска является метод бисекции, который применяется для поиска корней заданной непрерывной функции на заданном отрезке.
*-Нравится статья? Кликни по рекламе! :)

Если у нас есть массив, содержащий упорядоченную последовательность данных, то очень эффективен двоичный поиск.
Бинарный поиск позволяет найти данный элемент в отсортированном массиве или определить, что он не встречается в данном массиве за O(log n) действий, где n - количество элементов в массиве.

Описание алгоритма:

1.  Находится средний элемент последовательности. Для этого первый и последний элементы связываются с переменными, а средний вычисляется.
2.  Средний элемент сравнивается с искомым значение. В зависимости от того, больше оно или меньше среднего элемента, дальнейший поиск будет происходить лишь в левой или правой половинах массива. Если значение среднего элемента окажется равным искомому, то поиск завершен.
3.  Одна из границ исследуемой последовательности становится равной предыдущему или последующему среднему элементу из п.2.
4.  Снова находится средний элемент, теперь уже в «выбранной» половине. Описанный выше алгоритм повторяется уже для данной последовательности.

Переменные i и j содержат, соответственно, левую и правую границы отрезка массива, где находится нужный нам элемент.

def BinSearch(li, x):
    i = 0
    j = len(li)-1
    m = int(j/2)
    while li[m] != x and i < j:
        if x > li[m]:
            i = m+1
        else:
            j = m-1
        m = int((i+j)/2)
    if i > j:
        return 'Нет такого'
    else:
        return m

Замечательный труд Никлауса Вирта - Алгоритмы и структуры данных, написанный в век, когда любая операция сравнения и перестановки имела огромное значение, описывает модифицированную реализацию метода.

В ней мы избавимся от проверки li[m] != x, которая выполняется каждый цикл. Для этого он предлагает отказаться от "наивного" желания закончить поиск сразу после нахождения искомого значения, а дождаться схождения левой и правой границ и сравнить найденный элемент с искомым, поняв нашли или нет. Т.к. всего шагов logN , то он считает это решение целесообразным.

def BinSearchVirt(li, x):
    i = 0
    j = len(li)-1
    while i < j:
        m = int((i+j)/2)
        if x > li[m]:
            i = m+1
        else:
            j = m
    #тут не важно j или i
    if li[j] == x:
        return j
    else:
        return None

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


Двоичный поиск - очень мощный метод. Если, например, длина массива равна 1023, после первого сравнения область сужается до 511 элементов, а после второй - до 255. Легко посчитать, что для поиска в массиве из 1023 элементов достаточно 10 сравнений.

Практические приложения метода:

• Широкое распространение в информатике применительно к поиску в структурах данных. Например, поиск в массивах данных осуществляется по ключу, присвоенному каждому из элементов массива (в простейшем случае сам элемент является ключом).
• Также его применяют в качестве численного метода для нахождения приближённого решения уравнений.

Немножко о производительности
Для сравнения, одухотворения и просто ради полезности, вынес этот вопрос в свою другую статью!)

Использованная литература: 
1.) Вики Двоиный поиск
2.) http://younglinux.info/algorithm/dichotomy
3.) http://algolist.manual.ru/search/bin_search.php

Числа Фибоначчи

Чи́сла Фибона́ччи — элементы числовой последовательности

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946,… 

в которой каждое последующее число равно сумме двух предыдущих чисел. Название по имени средневекового математика Леонардо Пизанского (известного как Фибоначчи).
Более формально, последовательность чисел Фибоначчи задается линейным рекуррентным соотношением:

*-Нравится статья? Кликни по рекламе! :)

Вычисление факториала

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

Факториа́л числа n (обозначается n!, произносится эн факториа́л) — произведение всех натуральных чисел до n включительно:

.

По определению полагают 0! = 1. Факториал определён только для целых неотрицательных чисел.

*-Нравится статья? Кликни по рекламе! :)

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

Алгоритм Евклида – это алгоритм нахождения наибольшего общего делителя (НОД) пары целых чисел.
Наибольший общий делитель (НОД) – это число, которое делит без остатка два числа и делится само без остатка на любой другой делитель данных двух чисел.
*-Нравится статья? Кликни по рекламе! :)

Пилотный(нулевой) пост

Итак, это мой нулевой пост в этот блог.
Я надеюсь, что из самого названия понятно, о чем я буду здесь писать.
Скажу сразу, что это вряд ли будут авторские статьи, скорее это будет некая консолидация материалов, которые мне понравились и возможно пригодятся.
Я буду писать где я нашел те или иные статьи, но если вдруг забуду, просьба не бить сильно, а просто указать на это!
Ну вот и все, надеюсь я найду достаточно время, чтобы уделять этому блогу пару часиков в неделю, для пополнения и редактирования.
На сем заканчиваю, надеюсь, самый пустой и бессмысленный пост и приступлю к более серьезному.