Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
Об’єм програми -розмир
Важливою характеристикою програми є її розмір. При перекладі алгоритму з однієї мови на інший розмір програми буде змінюватися. Вивчення цих змін кількісними методами вимагає, щоб розмір був вимірною величиною.
Крім того, метрична характеристика розміру повинна бути застосовна до широкого кола мов без втрати спільності та об'єктивності отже, не повинна залежати від набору символів, необхідних для подання алгоритму, тобто символів, що використовуються для запису операторів або імен операндів.
Вирішення цієї проблеми пов'язано з тим, що можна визначити абсолютний мінімум довжини подання найдовшого оператора або імені операнда. Мінімальна довжина залежить тільки від числа елементів у словнику h. У загальному випадку 
є мінімальна довжина (в бітах) всієї програми. Під бітом тут розуміється логічна одиниця інформації - символ, оператор, операнд - те, чим оперує програміст при створенні програми.
Відповідна метрична характеристика розміру будь-якої реалізації якогось алгоритму, що називається об'ємом V, може бути визначена як
(1.2)
де 
- довжина реалізації, а 
її словник.
Очевидно, що якщо даний алгоритм перекладається з однієї мови на іншу, то його обсяг змінюється. Наприклад, при перекладі алгоритму з Паскаля в машинний код будь-якої конкретної машини його об’єм збільшиться. З іншого боку, вираження алгоритму на більш розвиненій мові, ніж та, на якій він написаний початково, призведе до зменшення його об’єму. Остання можливість надзвичайно важлива і заслуговує спеціального розгляду.
Потенційний об’єм V*
Вираз алгоритму в найбільш стислій формі передбачає існування мови, в якій необхідна операція вже визначена або реалізована, можливо, у вигляді процедури або підпрограми. Для реалізації алгоритму в такій мові потрібні лише імена операндів для його аргументів і результатів.
Позначивши відповідні програмні параметри можливо найкоротшою або в найбільш стислій формі алгоритму зірочками, з рівняння (1.1) отримаємо, що мінімальний (або потенційний) об’єм дорівнює
V* = (N1* + N2*) log2(h1* + h2*)(1.3)
Але у мінімальній формі ні оператори, ні операнди не вимагають повторень, тому
N1* = h1*; N2* = h2*
що дає нам
V* = (h1* + h2*) log2(h1* + h2*)
Крім того, відоме мінімально можливе число операторів 
для будь-якого алгоритму. Кожен алгоритм повинен включати один оператор для імені функції або процедури і один в якості символу привласнення або угруповання, тобто мінімальне значення 
.
Рівняння тепер набуде вигляду:
V* = (2+ h2*) log2(2+ h2*), (1.4)
де 
повинне являти собою число різних вхідних і вихідних параметрів.
З рівняння (1.4) випливає, що потенційний об’єм V * будь-якого алгоритму не повинен залежати від мови, якою він може бути виражений. Якщо розцінюється як число єдиних за змістом (ненадлишкових) операндів, то V * виявляється найбільш корисною мірою вмісту алгоритму.
Повернімося до прикладу програми для алгоритму Евкліда і визначимо його обсяг для програм на Паскалі і С.
Паскаль: V =N * log2 h = 61* log2 18 = 254.4 бітів.
С: V =N * log2 h = 55* log2 18 = 224.8 бітів.
Щоб знайти потенційний об’єм, нам потрібно підрахувати число необхідних вхідних і вихідних параметрів. В даному випадку це А, В і GCD, так що 
. Отже, потенційний об’єм:
V* = (2 +h2*) log2(2 + h2*) = (2+3) log2(2+3) = 11,6 бітів
Як вже згадувалося вище, при перекладі алгоритму з однієї мови на іншу його потенційний об’єм V * не змінюється, але дійсний об’єм V збільшується або зменшується в залежності від розвиненості розглянутих мов. Проте легко помітити, що не може бути гладкого переходу від виразу на потенційній мові, для якого V = V *, до будь-якої менш розвиненої мови, для якої V>V *. Такий різкий перехід обумовлений тим, що для потенційної мови 
, в той час як для всіх інших мов застосовується рівняння довжини і 
> 
.
Date: 2015-07-11; view: 306; Нарушение авторских прав; Помощь в написании работы --> СЮДА... |