Деревья кодирования по Хаффману

Эта статья дает возможность попрактиковаться в использовании списковых структур и абстракции данных для работы с множествами и деревьями.
Советую ознакомиться с предыдущей записью: Представление множеств и КодХаффмана
Они применяются к методам представления данных как последовательностей из единиц и нулей (битов). Например, стандартный код ASCII, который используется для представления текста в компьютерах, кодирует каждый символ как последовательность из семи бит. Семь бит позволяют нам обозначить 2⁷, то есть 128 различных символов. В общем случае, если нам требуется различать n символов, нам потребуется log₂N бит для каждого символа.
*-Нравится статья? Кликни по рекламе! :)

Представление множеств

И хотя в нашем любимом Python'е уже есть такой тип данных, как множества(set), я все таки считаю, Что изобрести велосипед заново, в данном случае будет полезно. Хотя бы чтобы просто получше понять, а как оно там вообще работает?!
Для понимания идеологии советую прочитать "Свойство замыкания на примере list"
*-Нравится статья? Кликни по рекламе! :)

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

Всем тем, кто осилил: 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, это наблюдение можно непосредственно перевести в процедуру. В рекурсивной реализации это выглядит следующим образом.

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

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

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

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

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

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

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