Търсачка

Банер

Дипломни Информатика, ИТ Компютърни алгоритми - Приложение и оптимизиране


Дипломна работа, 44 страници по-големи от стандартните, съдържа таблици, формули, графични елементи, има апарат
Цена: 4.80лв.
Безплатно
Спестявате: 100.00%
Задайте въпрос за този материал

Normal 0 21 false false false MicrosoftInternetExplorer4 /* Style Definitions */ table.MsoNormalTable {mso-style-name:"Table Normal"; mso-tstyle-rowband-size:0; mso-tstyle-colband-size:0; mso-style-noshow:yes; mso-style-parent:""; mso-padding-alt:0cm 5.4pt 0cm 5.4pt; mso-para-margin:0cm; mso-para-margin-bottom:.0001pt; mso-pagination:widow-orphan; font-size:10.0pt; font-family:"Times New Roman"; mso-ansi-language:#0400; mso-fareast-language:#0400; mso-bidi-language:#0400;}

Съдържание

Увод. 3

Цели и задачи на дипломната работа. 4

Въведение. 5

1. Алгоритъм.. 5

1.1. Формализации. 5

1.2. Представяне. 5

1.3. Класификация на алгоритмите. 6

2. Основни математически понятия и алгоритми. 8

2.1. Множества. 8

2.2. Числа 9

2.3. Целочислено деление и остатък. 10

2.4. Степен, логаритъм, n-ти корен. 10

2.5. Факториел. Рекурентни функции. 11

2.6. Матрици 11

2.7. Намиране броя на цифрите на произведение. 12

2.8. Прости числа. 12

2.9. Мерсенови числа. 16

2.10. Съвършени числа. 17

2.11. Бройни системи и преобразуване. 17

2.12. Римски цифри. 20

3. Рекурсия и итерация. 21

3.1. Факториел. 21

3.2. Редица на Фибоначи. 21

3.3. Най-голям общ делител. Алгоритъм на Евклид. 22

4.1. Сортиране чрез сравнение. 24

4.2. Сортиране чрез вмъкване. 25

4.3. Сортиране чрез трансформация. 28

5. Търсене. 29

5.1. Търсене със стъпка. Квадратично търсене. 32

5.2. Двоично търсене. 33

5.3. Интерполационно търсене. 34

6. Търсене с връщане. NP-пълни задачи. 35

6.1. Класификация на задачите. 35

6.2. Приложение на алгоритмите. 37

Използвана литература: 44


Увод

Алгоритъм е термин от математиката, информатиката, лингвистиката и други области, с който се означава крайна поредица от инструкции или изрично описание на постъпкова процедура за решаване на даден проблем, често свързан с изчисление или обработка на данни. По-строго казано, алгоритъмът е ефективен метод, който при даден списък от коректно дефинирани команди за изпълнение на задача и зададено едно начално състояние преминава през коректно дефинирана поредица от последователни състояния и завършва в едно крайно състояние. Преходът между състоянията не е задължително да е детерминиран: някои алгоритми известни като вероятностни алгоритми съдържат в себе си случайност.

Частичната формализация на понятието започва с опитите да се реши 10-тия проблем на Хилберт „Задача за разрешимост на диофантово уравнение“, поставен от Давид Хилберт през 1900 година на Втория световен конгрес по математика в Париж. Последващите формализации представляват опити да се дефинира „ефективна изчислимост“ (Клини 1943:274) или „ефективен метод“ (Росър 1939:225); включват рекурсивните функции на Ербран-Гьодел-Клини от 1930, 1934 и 1935 година, ламбда смятането на Алонсо Чърч от 1936, „Формулировка 1“ на Емил Пост от 1936, и машината на Тюринг от 1936-7 и 1939 година.

При все, че няма общоприета формална дефиниция на алгоритъм, неформално понятието може да се определи като „процес, който извършва някаква поредица от операции“.


Цели и задачи на дипломната работа

Основни цели и задачи

Основната цел на настоящата дипломна работа е да се представят едни от най-известните и използвани компютърни алгоритми, както в теоретично така и в практично отношение. Също така има за цел да се покажат примери за приложението им за намиране на решения на основни типове задачи свързани с всекидневния живот.

В дипломната работа се засягат въпроси, подпомагащи изучаването на предмети свързани с компютърната информатика.

Водещи идеи и закономерности

Основната идея в съдържанието на дипломната работа е формирането на понятия, представи и знания за основните математически понятия, алгоритми и задачи, използвани в съвременните методи за програмиране.

Кратко съдържание на дипломната работа

В дипломната работа са разледани математическите понятия, намиращи пряко приложение в програмирането, като: множества, числа, бройни системи, матрици, както и различни агоритми за бързо изчислени, търсене, сортиране с примери за оптимизиране

Всички основни операции се реализират чрез процедури, за да могат по-нататък да се използват наготово в по-сложни задачи.

Всички основни операции са реализирани чрез процедури, за да могат по-нататък да се използват наготово в по-сложни задачи. Тук например се решават задачи като изчисление на факториел, сортиране на списък, търсене и намиране на оптимално решение на задачи от ежедневието.

Примерите са представени посредством езика Си, като най-популярен и универсален в работата с алгоритми.

 

------------------------------------------------------

 

 

Normal 0 21 false false false MicrosoftInternetExplorer4 st1:*{behavior:url(#ieooui) } /* Style Definitions */ table.MsoNormalTable {mso-style-name:"Table Normal"; mso-tstyle-rowband-size:0; mso-tstyle-colband-size:0; mso-style-noshow:yes; mso-style-parent:""; mso-padding-alt:0cm 5.4pt 0cm 5.4pt; mso-para-margin:0cm; mso-para-margin-bottom:.0001pt; mso-pagination:widow-orphan; font-size:10.0pt; font-family:"Times New Roman"; mso-ansi-language:#0400; mso-fareast-language:#0400; mso-bidi-language:#0400;}

Задача за раницата (Оптимална селекция)

Дадена е раница с вместимост (издръжливост) М килограма. Дадени са N предмета, всеки с тегло mi (1 i N). Да се провери дали съществува подмножество от предмети, които да запълват точно раницата, т.е. сборът от теглата им да бъде точно М.

Обобщен оптимизационен вариант на тази задача е следната:

Дадена е раница, която може да побере М килограма. Дадени са N предмета, всеки с тегло mi и стойност (цена) ci. Да се намери подмножество от предмети с максимална обща цена, които да се побират в раницата, т.е. сборът от теглата им да бъде по-малък или равен на М

В някои частни случаи, например когато теглата са цели числа, и при наличие иа достатъчно памет (Θ(M.N)), могат да се приложат ефективни алгоритми за решаване на горните задачи, основани на принципа на динамичното оптимиране. В обшия случай обаче, когато цените и теглата са реални числа, тези две NP-пълни задачи се решават с пълно изчерпване. Ще разгледаме втората от тях и ше я решим с метода на разклоненията и границите.

Ще генерираме всички възможни решения чрез търсене с връшане, като в процеса на генериране ще запазим оптималното. Във втората задача е дадено множество от предмети. Измежду всички 2N негови подмножества трябва да изберем това, което отговаря на условията на задачата: сумата от теглата на предметите в него да не надхвърля М и сумата от стойностите им да бъде максимална.

Нека разполагаме с частично решение (подмножество от предмети), при което са взети предметите A = {а1, а2, ..., аk} С S(а1, а2, ..., аk) означаваме сумата от теглата им. Към подмножеството А опитваме да добавим нов предмет измежду тези, които не са взети до момента:

- Ако S(а1, а2, ..., аk) + m[ak+1] ≤ M то следва, че добавянето на предмета е възможно и продължаваме рекурсивно да разширяваме подмножеството А по всички възможни начини.

- Ако не съществува предмет такъв, че S(а1, а2, ..., аk) + m[ak+1] ≤ M то следва, че множеството а1, а2, ..., аk е гранично (т. е. не може да се разширява повече).

Тогава се изчислява стойността му с[А] = с1] + c2] + ... + c[аk] и, ако е по-голяма от максималната намерена до момента, се запазва:

На практика дефинирахме кога едно частично решение може да се разшири. Така осигурихме да не се разглеждат всички 2N-та възможни подмножества, а само тези, за които сборът от теглата на предметите е по-малък или равен на М. С това обаче въпросът с отсичането на рекурсивното дърво иа кандидатите за решение не се изчерпва.

Нека а процеса на построяване на подмножество от предмети (както в схематичната процедура по-горе) сме взели

предметите A = {а1, а2, ..., аk} а сме пропуснали предметите B = {b1, b2, ..., bk}. С VT ще означим сбора от стойностите на всички предмети, а с Vmах максималната стойност, получена от проверените до момента решения. Тогава, ако

VT - c[b1] - c[b2] - ... - c[b1] ≤ Vmах

то следва, че няма смисъл да разширяваме повече текущото решение. Това е така, тъй като дори да бъде възможно включването на всички останали предмети, максималната стойност, която ще получим, е стойността на взетите до момента предмети плюс стойността на оставащите при което, ако последният израз се окаже по-малък от Vmах. следва, че текущото решение е без перспективно и по-нататъшно разглеждане няма да доведе до по-добри резултати.

За да получим работеща програма, трябва да уточним още как ще извършваме включването и изключването на i-тия предмет. За целта ше въведем масив taken[] и променлива tN, която показва броя на елементите му. Най-доброто решение, намерено до момента, ще запазваме в масива saveTaken[], с sn елемента. Входните данни N, M, c[N] и m[N] се задават като константи в началото на програмата.

#define MAXN 100

const unsigned n = 10;

const float M = 10.5;

const float c[MAXN] = { 10.3, 9.0, 12.0, 8.0, 4.0, 8.4,

9.1, 17.0, 6.0, 9.7 };

const float m[MAXN] = { 4.0, 2.6, 3.0, 5.3, 6.4, 2.0, 4.0,

5.1, 3.0, 4.0 };

unsigned taken[MAXN], saveTaken[MAXN], tn, sn;

float VmaX, Vtemp, Ttemp, totalV;

void generate(unsigned i)

{

unsigned k;

if (Ttemp > M) return;

if (Vtemp + totalV < VmaX) return;

if (i == n) {

if (Vtemp > VmaX) {

VmaX = Vtemp; sn = tn;

for (k=0; k

saveTaken[k] = taken[k];

}

return;

}

taken[tn++] = i;

Vtemp += c[i];

totalV -= c[i];

Ttemp += m[i];

generate(i + 1);

tn--;

Vtemp -= c[i];

Ttemp -= m[i];

generate(i + 1);

totalV += c[i];

}

6.3. Изграждане на независима база данни


Използвана литература

1. http://en.wikipedia.org/wiki/Algorithm

2. Аладжем М., „Приложно програмиране”, „Техника”, София, 1992

3. Корн Г., Т. Корн, „Справочник по математика”, „Наука”, Москва, 1977

4. Наков П., „Основи на компютърните алгоритми”, Top Team Co”, София, 1998

5. Швертер Й., „Структури от данни и алгоритми”, университетско издателство „Св. Климент Охридски”, София 1995

6. Уирт Н. „Алгоритми”, „Техника”, София, 1980

7. Knuth D. The art computer programing, „Мир”, Москва, 1978


Коментари на клиенти:

Все още няма коментари за този материал.
Моля, влезте в системата с потебителско име и парола, за да оставите коментар.


повече категории
Компютърни системи

За сайта

Кой е онлайн

В момента има 597 посетителя и 5 потребителя в сайта

Намерете ни в Facebook


© 2010 znanieto.net Всички права запазени.
znanieto.net избра за свой хостинг партньор Viscomp.bg

Изграден с помощта на Joomla!.