ОСНОВИ НА ИНФОРМАТИКАТА АЛГОРИТМИ. 1. Науката информатика Предмет на науката информатика е информацията и основните информационни дейности Компютърна. - презентация

1 ОСНОВИ НА ИНФОРМАТИКАТА АЛГОРИТМИ

2 1. Науката информатика Предмет на науката информатика е информацията и основните информационни дейности Компютърна информатика – която използва компютри за обработка на информацията Области на приложение: Алгоритмите и структурите от данни Архитектура на компютрите и мрежите Бази данни Компютърна графика Операционни системи Езици за програмиране......

3 Произхода на думата дълго време остава неясен. Езиковедите се опитвали да обяснят това, комбинирайки различни думи. Накрая, историците на математиката открили истинския произход на думата algorism: тя произлиза от името на автора на известния арабски учебник по математика Abu Jafar Mohammed ibn Musa al-gorezmi (около 825 г.) 2. Исторически сведения за алгоритмите

4 Постепенно формата и значението на думата "algorism се променя от algorism на algorithm, така че истинския произход на думата е отдавна забравен.

5 Определение : Система от команди, които задават реда на изпълнение на елементарни действия с цел да се получи определен резултат. елементарно действие - което изпълнителят може да извърши самостоятелно, без допълнителни пояснения. стъпка - извършването на едно елементарно действие от изпълнителя. 3. АЛГОРИТМИ

6 Отношение към даден алгоритъм имат : Съставител Изпълнител Потребител Всеки алгоритъм започва от определено начално състояние (входна информация) и достига до резултат (изходна информация – друго крайно състояние)

7 Как да обясним, сложно действие на изпълнител, който умее да върши само прости неща? Представяме сложното действие, чрез последователност от прости, които изпълнителят може да извършва и които ще доведат до желания резултат.

8 Пример Велосипедист намиращ се в т. А и движещ се на изток пита как да стигне до кръстовището В.

9 Продължете направо, завийте наляво по първата пряка и след една пряка сте в т. В Мога да завивам само на дясно Направо, при втората пряка завийте надясно, след това два пъти последователно при срещане на пряка завийте надясно и после направо до втората пряка.

10 Описание на алгоритмите със знаци Подробните обяснения са необходими, когато изпълнителят е устройство - напр. робот или компютър Движи се направо до първата пряка Завий надясно(приемаме, че при завой изпълнителят остава на същото кръстовище В този случай указанията за велосипедиста ще бъдат :

11 Подалгоритъм Подалгоритъм е алгоритъм за изпълнение на типична последователност от действия, която се използва в определен(и) алгоритъм.

12 Подалгоритъм Велосипедиста може да завие наляво, като обиколи с десен завой един квадрат. Това можем да запишем със следната последователност : : Лявата стрелка и двуеточието означава, че завой наляво се определя чрез редицата от действия, записани след двуеточието. Тази последователност от елементарни действия ще наричаме подалгоритъм и ще считаме, че името на подалгоритъма е. Чрез този подалгоритъм можем да запишем придвижването от А до В по - просто :

13 Присвояване := Променливата := получава стойност При съставянето на алгоритъм е необходимо : Да представите сложното действие чрез последователност от по – прости действия, достъпни за изпълнителя. Да използвате само елементарни (за изпълнителя) действия. Да опишете ясно и точно последователността, в която трябва да се изпълняват елементарните действия.

14 Алгоритъм за отваряне на врата 1. Изваждане на ключа от джоба. 2. Поставяне на ключа в ключалката. 3. Завъртане на ключа два пъти по часовата стрелка. 4. Изваждане на ключа.

15

16 Свойства на алгоритмте Дискретност Яснота Формалност Определеност Масовост Изпълнимост Крайност Ефективност

17 Дискретност Описанието се състои от краен брой указания Описанието се състои от краен брой указания Изпълнява се в последователни, различни една от друга стъпки Изпълнява се в последователни, различни една от друга стъпки

18 Яснота (разбираемост) Изпълнителят може да извърши всяка стъпка и да определи еднозначно следващата Изпълнителят може да извърши всяка стъпка и да определи еднозначно следващата

19 Формалност Изпълнителят не е длъжен да знае каква цел се преследва, работи формално, изпълнявайки указанията Изпълнителят не е длъжен да знае каква цел се преследва, работи формално, изпълнявайки указанията Това свойство позволява изпълнителят да бъде автомат Това свойство позволява изпълнителят да бъде автомат

20 Определеност При изпълнение на алгоритъма с едни и същи данни се получава един и същ резултат При изпълнение на алгоритъма с едни и същи данни се получава един и същ резултат

21 Масовост Алгоритъма може да се прилага за решаване на коя да е задача от даден клас еднотипни задачи Алгоритъма може да се прилага за решаване на коя да е задача от даден клас еднотипни задачи

22 Изпълнимост Да се състои от изпълними стъпки

23 Крайност Изпълнението трябва да завърши след краен брой стъпки Изпълнението трябва да завърши след краен брой стъпки

24 Ефективност Да се изпълняват за приемлив брой стъпки Да не ползват прекалено много памет Измерване на ефективността Брой елементарни действия Брой на входните и междинни резултати

25 Какво научихме днес Алгоритъм Елементарно действие Стъпка Подалгоритъм Присвояване Свойства на алгоритмите