Алгоритми. Структурно програмиране.


Категория на документа: Други


1.Определение и развитие на понятието алгоритъм
Едно oт най-важните понятия в съвременната математика и информатика е понятието алгоритъм. За него не може да се даде строго определение, а само някакъв вид описание. Алгоритъма е точно предписание което задава изчислителния процес и започва от входни данни принадлежащи на някаква съвкупност. Алгоритъма е еднозначна процедура за решение на задача. Процедурата от своя страна представлява крайна последователност от точно определени стъпки и операции, за изпълнението на които се изисква краен обем оперативна памет и крайно време. При изчисляване на алгоритъм не е задължително да бъде получен резултат - при конкретните входни данни изчисленията по дадения алгоритъм могат да се прекъсват без резултат или въобще да не завършат. В такъв случай се казва, че алгоритъмът не е приложим за тези конкретни входни данни. Алгоритмите притежават редица свойства:
1. Детерминираност - това свойство означава, че всяко действие в алгоритъма трябва да е еднозначно определено за всички възможни данни, които той е предназначен да обраоотва. Действията в алгоритъма трябва така да се формулирани, че да не допускат двусмислие. При изпълнение на ЦЕИМ езиците за програмиране са тези, които осигуряват недвусмислие.
2. Резултативност - целта на всеки алгоритъм е да даде резултат, който еднозначно да съответствува на входните данни, които той е обработил. Резултат обаче не се получава при всякакви входни данни, а само тогава, когато те са взети от областта на определение на алгоритъма, която моделира множеството на входните данни, за които алгоритъма е резултативен. На всяка точка от областта на определение на алгоритъма съответствува точка от областта на стойностите на алгоритъма. Ако входните данни не представляват точка от дефиниционната област на алгоритъма, то процедурата на алгоритъма или продължава до безкрайност или не се получава верен резултат.
3. Крайност - резултатът на алгоритмите трябва да се получава след краен брой действия предписани от алгоритъма.
4. Дискретност - алгоритъмът трябва да се изпълнява на отделни стъпки, съдържащи едно или няколко действия. Към следващата стъпка се преминава само след като е изпълнена предишната стъпка.
5. Масовост - под масовост се разбира свойството на алгоритъма да дава решение на цял клас задачи.
Алгоритмите могат да бъдат подразделени на различни видове изхождайки от различни признаци
а) Разклонени и неразклоневи - неразклонените алгоритми представляват неизменима последователност от действия. При разклонените алгоритми последователността от действия и операции се изменя изхождайки от няквкво условие, зависещо пряко или косвено от входните данни, така че в зависимост от тях алгоритъмът ще се изпълни по един или друг клон.
б) Последователни и паралелни алгоритми - при последователните алгоритми действията се изпълняват едно след друго по време. При паралелните алгоритми действията, ако те са независими едно от друго, могат да се изпълняват и паралелно, в едно и също време.
в) Циклични алгоритми - при тях едно действие или поредица от действия записани еднократно се изпълняват многократно при изменящи се данни.
г) Детерминирани и вероятностни алгоритми - в зависимост от това дали съдържат случайни величини, много често обаче случайните величини във вероятностните алгоритми се моделират чрез разпределения получени чрез детерминиран алгоритъм, в резултат на което вероятностният алгоритъм по същество се превръща в детерминиран алгоритъм, който моделира случайни явления.
д) Самоизменящи алгоритми - тези които не само преработват входните данни, но и самите те се преобразуват. Резултатът от работата на този вид алгоритми зависи не само от конкретните входни данни, но и от състоянието не алгоритъма, което от своя страна се определя от предишната му работа.
е) Евристични алгоритми - дават решение, което не е най-доброто, но за сметка на това решението е бързо
ж) Числени и логически алгоритми - числените алгоритми са тези, които се свеждат до някакви аритметични действия. Те могат да съдържат и по-сложни математични действия, които чрез съответните числени методи в крайна сметка се свеждат до аритметични действия.
Машина на Тюринг
Английският математик Тюринг е предложил абстрактна схема на автомат, пригоден за реализацията на всеки алгоритъм. Наречен е "машина на Тюринг". Автоматът на Тюринг има крайна вътрешна и безкрайна външна памет, представена чрез лента, на която се записва информация във всяка клетка - нули и единици.

2. Оптимизация на алгоритмите по време и памет.
Бързодействие (време зa изпълнение)
Независимо от непрестанния прогрес в бързодействието на компютрите сега и в бъдеще ще има задачи, за които времето за изпълнение ще бъде проблем. Проблем по отношевие на времето зa изпълнение може да възникне и при решаване на задачи с голяма размерност. Под размерност на задачата може да се разбира броят на неизвестните и уравненията, които ги свързват.При наличието на много вложени един в друг цикли бързодействието се определя в най-голяма степен от операторите в тялото на най-вътрешния цикъл. При недостиг на бързодействие, мерките, които могат да се предприемат са следните:
1. Операторите в тялото на най-вътрешния цикъл или най-често повтарящите се оператори да се напишат по оптимален за бързодействието начин.

2. Използува не на числен метод осигуряващ най-голямо бързодействие. В зависимост от конкретната задача следва де се избере най-бързия метод.
3. Бързодействието на програмата може да се повиши, ако нейната транслация се извърши чрез оптимизиращ компилатор.
4. Избор на процесор с по-голяма тактова честота, както и използване на много ядрени процесори с разпаралелване на алгоритмите
Необходима памет
Паметта на компютъра при изпълнение на една програма се заема от:
1. Обработваните структури от данни - масиви, записи и др.
2. От командите на програмата представени в машинен код.
3. От стандартните подпрограми и функции, които се извикват за изпълнение.
Готовата за изпълнение програма се получава след свързването на транслираната програма със стандартните програми и функции, в резултат на което се получава изпълнима програма в абсолютен двоичен код, наречена образ в паметта. Обемът на заеманата памет от този двоичен код е показател за сложността на програмата, но не винаги е определящ показател. Той може да се превърне в определящ показател за трудноста на разработваната програма, ако паметта на използвания компютър не достига.Мерките, които могат да се вземат са следните:
а) Промяна в математическия модел с оглед намаляване на необходимата памет
б) Опростяване на алгоритъма с оглед намаление на броя на операторите в програмата, размерността на използваните масиви и др..
в) Използуване на сегментация на програмите ( OVERLAY ), при която в даден момент в оперативната памет се намира главната програма и само един сегмент, а останалите сегменти са във външно запомнящо устройство.
г) Използуване на динамични променливи, за които памет се резервира по време на изпълнение само временно, докато това е необходимо за изпълнението на програмата, а след това тя се освобождава.
д) Заявяване на по-голям дял от паметта при системите с много потребители или прехвърляне на програмата на компютър с повече памет.
Трябва да се подчертае, че когато са изчерпани другите възможности бързодействието на програмата може да се повиши за сметка на необходимата памет и обратно.
3. Етапи на разработка и документиране на алгоритми и програми.
За да се реши дадена задача чрез ЦЕИМ трябва да бъде създадена строга последователност от елементарни операции, наречена програма, чрез която се осъществява необходимият изчислителен процес. Програмата се представя чрез алгоритъм. Точно описание на алгоритъм може да бъде дадено чрез блок-схема или чрез алгоритмичен език. Въз основа на алгоритъма се създава програма за ЦЕИМ, чиято работа се проверява, а разработеният програмен продукт се документира. Компютърната програма извършва автоматизация на изчислителния процес и за създаването и трябва да се отговори на следните въпроси:
- Коректна ли е терминологията използуване в предварителната формулировка на задачата?
- Какво е дадено?
- Какво трябва де се намери?
- Кои данни липсват?
- Всички данни ли са нужни или някои от тях са безполезни?
- Какви допускания са направени?
- Взети ли са под внимание всички фактори?
- Как да се намери решението?
Разработка не математически модел
Математическото моделиране на изследвания обект може условно де се раздели на два етапа:
а) Разработване на аналитичен математически модел.



Сподели линка с приятел:





Яндекс.Метрика
Алгоритми. Структурно програмиране. 9 out of 10 based on 2 ratings. 2 user reviews.