Лингвофорум

Цитата: Bhudh от мая 17, 2015, 23:41

Цитата: _Swetlana от мая 17, 2015, 23:18Объявляем переменную определённого типа, выделяем память. Потом присваиваем ей значение 1.

Если на каждую константу по longlongint выделять...

Россия - щедрая душа 

Но в Америке серверов всё равно больше.

Цитата: _Swetlana от мая 17, 2015, 18:47
Откуда log(b)/b ?

Как я понял, из схемотехники.
Одна из реализаций памяти — через триггеры на логических элементах 2-И-НЕ.
На крждый разряд нужно по триггеру, при этом триггер для k-ичной цифры будет иметь k элементов 2-И-НЕ.

Двоичный триггер	Троичный триггер

То есть, мы считаем, сколько элементов нужно для представления числа.

Кстати, на ЛФ уже как минимум местах в двух обсуждалось. Хорошо бы слить, чтобы тут не офтопить.

А я-то думала, из математики.
Сливайте, куда хотите 

Ещё пофлужу, не зря ж меня Мынаше КО называет.
Не знаю, что обсуждалось на ЛФ, но формулы выводятся всё ж из математических моделей. Математической моделью устройства для хранения числа является абстрактный конечный автомат (о чём я могла и пораньше догадаться, и вопросы бы не возникли).
Общее количество информации делится на суммарное количество состояний автомата, а количество состояний автомата (в данном случае) не зависит от реализации через триггеры-шмыггеры  потому что на каждый разряд нужно b независимых состояний.

Чё-то я не понял вашего замечания. Можно ещё раз, только поподробнее?

В параллельной вселенной система счисления построена на числах Фибоначчи.

Цитата: Тайльнемер от мая 18, 2015, 12:26
Чё-то я не понял вашего замечания. Можно ещё раз, только поподробнее?

А что именно не поняли?

Цитата: _Swetlana от мая 18, 2015, 11:57
...формулы выводятся всё ж из математических моделей. Математической моделью устройства для хранения числа является абстрактный конечный автомат... а количество состояний автомата (в данном случае) не зависит от реализации через триггеры-шмыггеры

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

Цитата: _Swetlana от мая 17, 2015, 18:47
Объясните, где я ошибаюсь, будьте так любезны.

ЦитироватьОпределение плотности записи информации через энтропию

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

Пусть система счисления имеет основание b, записанное число r разрядов. Возможных состояний системы b^r, все они равновероятны, p=1/b^r.
Если по известной формуле Шеннона посчитать энтропию такой системы, то получим log(b^r) = r*log(b). Это энтропия r-разрядного числа в системе счисления с основанием b, оно же количество информации. Теперь делим количество информации r-разрядного числа на число разрядов, получаем log(b).
Откуда log(b)/b ? 

В знак не *n=r, a n=b*r, т.е.

А плотность записи не  , а  нат или  бит

Спасибо, Sirko,  я уже разобралась 

Цитата: Тайльнемер от мая 18, 2015, 13:56

Цитата: _Swetlana от мая 18, 2015, 11:57
...формулы выводятся всё ж из математических моделей. Математической моделью устройства для хранения числа является абстрактный конечный автомат... а количество состояний автомата (в данном случае) не зависит от реализации через триггеры-шмыггеры

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

Нет, модель не зависит от физического устройства. Физические устройства соответствуют этой модели.

Что такое автомат? Абстрактное устройство, которое находится в определённом состоянии, получает на вход сигнал, переходит в другое состояние (или остаётся в том же ) и на выход отправляет выходной сигнал. Всё конечно: мн-во состояний, мн-во входов и выходов; функционирование автомата описывается двумя функциями с конечным набором команд.
Поскольку мы храним число, никаких выходов у нас нет, нас интересует только функция переходов из состояния в состояние.
Что такое мн-во состояний автомата? - это его внутреняя память.
У нас r одинаковых автоматов (по числу разрядов), рассмотрим работу одного.
Как автомат может запомнить одно число из 0..b-1? У него должно быть b различных состояний q₀, ..q_b-1. Вначале он находится в состоянии q₀. Если на вход поступило число i, то он переходит в состояние  q_i.  Количество различных чисел по всем разрядам b*r, это необходимое число состояний.

Сделаю небольшое лирическое отступление. Как сказал гениальный математик Ломоносов (не тот  тот был великим, но не гениальным, а этот - наш не великий гениальный современник): "Идей в математике меньше чем теорем". Идея состояния системы - это великая идея.
Чему равно количество информации в r-разрядном слове, записанном в b-буквенном алфавите: log(b^r), где b^r - количество состояний системы (с точностью до константы, зависящей от выбора основания логарифма).
Чему равна минимальная необходимая сложность автомата для хранения этого слова: - количеству его состояний br. (В скобках замечу, что в нашем случае количество команд линейно зависит от числа состояний, т.е сложность с точностью до константы O(br).)
Таким образом, эта формула не только проста и красива, но есть фундаментальная идея пространства состояний в действии     

...А ещё троичная система получается естественным образом, если каждый разряд (например, единственный) передаётся при помощи выделенной пары проводов. Можно эту пару проводов вообще отключить от источника тока и закоротить, можно подключить к источнику одной полярностью, а можно противоположной. Именно такая схема применялась, например, в системе автоблокировки с рельсовмыми цепями постоянного тока. Питание в РЦ в них подавалось с той стороны, с которой вступает поезд и где находится светофор, защищающий блок-участок, а путевое реле располагалось, соответственно, на выходном конце блок-участка, на удалении от светофора данного БУ и рядом со светофором следующего БУ. И вот оттуда назад к своему светофору информация о состоянии передавалась по одной паре проводов именно как троичный разряд - с добавлением информации и о следующем блок-участке: если путевое реле (повторитель) без тока, т.е. блок-участок занят, то провода отключены, и сзади светофор показывает красный. Если же реле под током, т.е. БУ свободен, то ток подаётся, но полярность зависит от состояния следующего блок-участка: если следующий БУ занят (а светофор при ящике, соотв., красный), полярность одна, и светофор сзади показывает жёлтый, если же он свободен (светофор при ящике открыт - жёлтый или зелёный), полярность другая, и светофор сзади показывает зелёный. Понятно, что если данный БУ занят, то необходимости знать состояние следующего уже нет.

Потом получила распространение система автоблокировки числового кода, и необходимость передачи такой информации по паре проводов отпала, т.к. рельсовые цепи чисто кодовые, питаемые с выходного конца, и информация о состоянии следующего блок-участка приходит на сигнальную точку естественным образом вместе с кодом (банально серии из 1, 2 или 3 импульсов). Однако принцип передачи троичного разряда по паре проводов с использованием полярности сохранился - например, для предвходных светофоров там, где входной светофор может разрешать движение либо с максимальной скоростью, либо со скоростью до 40 км/ч, либо до 80 км/ч. Или для управления предупредительным светофором перед входным на перегонах без автоблокировки, где он имеет три показания: жёлтый (входной закрыт), жёлтый мигающий (входной разрешает до 40 км/ч) и зелёный (входной разрешает установленную скорость).
Аналогичный принцип используется, например, и в схемах управления и контроля положения стрелок в электрической централизации, где стрелка может иметь три положения - два крайних и промежуточное/неопределённое/взрезанное/неисправное.

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

Цитата: Toman от мая 18, 2015, 17:54
...А ещё троичная система получается естественным образом, если каждый разряд (например, единственный) передаётся при помощи выделенной пары проводов. Можно эту пару проводов вообще отключить от источника тока и закоротить, можно подключить к источнику одной полярностью, а можно противоположной.

А можно отключить и не закоротить. А можно (поскольку логические элементы имеют питание) один провод закоротить на плюс питания, а другой оставить в воздухе (два варианта). Или на минус (ещё два варианта). Или оба на плюс. Или оба на минус. Естественным образом получается десятичная система

Цитата: Alone Coder от мая 18, 2015, 20:15
А можно отключить и не закоротить. А можно (поскольку логические элементы имеют питание) один провод закоротить на плюс питания, а другой оставить в воздухе (два варианта). Или на минус (ещё два варианта). Или оба на плюс. Или оба на минус. Естественным образом получается десятичная система

Ой, какая ересь! По условию задачи разрешается использовать только эту пару проводов, а обращение к сторонним проводникам, которое вы тут подразумеваете, чревато всякими нехорошими последствиями - например, поймать блуждающий ток. Уже только поэтому варианты "оба на плюс" и "оба на минус" ничем не отличаются от простого "отключено и закорочено", кроме количества отказов, необходимого для передачи опасного ложного показания.

С точки зрения использования строго только одной пары проводов, отличаться могло бы только отключение без закорачивания. Но, даже если отвлечься от неудобств, связанных с местным питанием в линию от принимающей стороны, эти два положения легко и непринуждённо превращаются друг в друга в обе стороны единственным (и притом банальным) отказом - соотв. обрывом провода или КЗ между проводами на линии. И уже только по этой причине различение таких положений не годится для построения схем, безопасных при отказах. На самом деле, закорачивать ли отключённый от питания конец линии или оставлять разомкнутым по обоим полюсам - отдельный вопрос, ответ на который может зависеть от того, какого рода неприятностей мы больше боимся. Если боимся появления левого питания в разрыве провода, то лучше оставить разомкнутым. А если боимся левого питания просто между разными проводами без разрыва, то лучше закоротить. Но во всяком случае это уже более сложные и маловероятные отказы. А вот само различие между закороченной и разомкнутой линией без поданного на неё питания нельзя использовать безопасным при отказе образом из-за гораздо более простых и гораздо более вероятных отказов.

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

Цитата: _Swetlana от мая 18, 2015, 15:09
Нет, модель не зависит от физического устройства.

Модель выбирается в соответствии с физическим устройством.

Вы же сами приводили пример с листом бумаги, на котором печатаются буквы алфавита фиксированного размера.
Если бы память представляла собой такой лист бумаги, нас бы интересовало число символов, и формула была бы ln b. А в случае с памятью на триггерах нас интересует число триггеров, которое совпадает с числом состояний автоматов, и получается ln b / b.

Цитата: Тайльнемер от мая 19, 2015, 06:17

Цитата: _Swetlana от мая 18, 2015, 15:09
Нет, модель не зависит от физического устройства.

Модель выбирается в соответствии с физическим устройством.

Вы же сами приводили пример с листом бумаги, на котором печатаются буквы алфавита фиксированного размера.
Если бы память представляла собой такой лист бумаги, нас бы интересовало число символов, и формула была бы ln b. А в случае с памятью на триггерах нас интересует число триггеров, которое совпадает с числом состояний автоматов, и получается ln b / b.

Я не приводила такого примера. И я не говорила, что у азбуки Морзе бинарный алфавит. Сорри, щас нет времени.

Цитата: _Swetlana от мая 19, 2015, 07:40
Я не приводила такого примера.

Цитата: _Swetlana от мая 17, 2015, 12:17
Мы записываем на доске числа от 0 до N c помощью двух разных алфавитов. Делим использованную площадь на N, получаем функцию удельной плотности f(m, N), где m - количество символов алфавита, N - число.
Чем больше основание позиционной системы счисления, тем короче запись числа. И площадь меньше.

Цитата: Тайльнемер от мая 19, 2015, 06:17
Модель выбирается в соответствии с физическим устройством.

Нет.
Теоретические основания "информатики" со всеми её устройствами и языками программирования (теория алгоритмов, которую я по старинке называю "конструктивной математикой"):   
Программа Гильберта - 20-е годы.
Теоремы Гёделя  - 1931г. (Гёделю было 25 лет).
Вычислимые функции и тезис Чёрча - 1935-1936гг.
Машины и тезис Тьюринга - 1936-1937гг.
Машина Поста - 1936г.
Нормальные алгорифмы Маркова - конец 40-х годов (А.А Марков мне на 1-м курсе математическую логику читал. Я, конечно, была самым недостойным всех слушателей )

Когда появились реальные физические устройства на триггерах-шмыггерах, чтобы стать образцами для математических моделей?

Что такое машина Тьюринга - это абстрактная модель вычислителя. Причём этих вычислителей у Тьюринга два. Первый тип вычислителя- конкретная машина Тьюринга, которая выполняет свою ДМТ-программу. С точки зрения физических устройств - напаяли схемку, она выполняет один и тот же алгоритм всегда, пока не сломается.
Второй тип вычислителя: универсальный интерпретатор, который может выполнить любую ДМТ-программу (принцип хранимой, выполняемой и модифицируемой программы ошибочно называют "архитектурой фон Неймана", не буду касаться этой долгой и малоприятной истории).

ЗЫ. Сейчас гуглила даты, неожиданно нагуглила статью, где о нашем кураторе А.Г. Драгалине (ученике Маркова) вспоминают:

ЦитироватьА. Г. Драгалин еще раз подтвердил глубину воззрений Гильберта, поддержанных, кстати, его якобы непримиримым ( если судить по писаниям вульгаризаторов истории науки) оппонентом Брауэром: хотя порою в принципе идеальные понятия могут быть устранены, редукционизм и ползучий эмпиризм приводят к полной умственной прострации, просто невероятно увеличивая объем выкладок. Ни до чего нетривиального мы не можем добраться без использования идеальных понятий, и чем более сильного практического результата мы желаем добиться, тем более высокую теорию надо задействовать.

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

Цитата: Тайльнемер от мая 19, 2015, 11:04

Цитата: _Swetlana от мая 19, 2015, 07:40
Я не приводила такого примера.

Цитата: _Swetlana от мая 17, 2015, 12:17
Мы записываем на доске числа от 0 до N c помощью двух разных алфавитов. Делим использованную площадь на N, получаем функцию удельной плотности f(m, N), где m - количество символов алфавита, N - число.
Чем больше основание позиционной системы счисления, тем короче запись числа. И площадь меньше.

Это я чужой пример пыталась понять, о чём речь. Ну, туповата, сразу не поняла. Я и не отрицаю 

Цитата: _Swetlana от мая 19, 2015, 11:28
Когда появились реальные физические устройства на триггерах-шмыггерах, чтобы стать образцами для математических моделей?

Железнодорожная сигнализация/блокировка и телеграф - кажется, оба постепенно развиваются с 19-го века. А уж механические замки (ближайший родственник ж.д. систем блокировки) с каких времён делают... Ведь передача и хранение информации - они не всегда сопряжены с какими-то собственно компьютерами.

Да, ещё абак, счёты, логарифмирическая линейка и арифмометр в качестве модели вычислителя 

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

Причём тут оптимизация? Я ничего не оптимизировала, сугубо для личных целей выводила формулу log(b^r)/(br).
Когда вывела, обратила внимание собравшихся, что нельзя числитель подсчитывать чрез количество энтропии, а знаменатель через количество триггеров конкретного устройства. Разный уровень абстракции.
Тем более, нетрудно видеть, что для хранения числа в формате (b,r) (формат числа задан по условию) любое устройство должно иметь br независимых состояний.