Извршување на алгоритам за одредена одлука на извршител. Компјутерски науки и информатичка технологија. Начини за опишување на алгоритми

Клучни зборови:

• алгоритам
• својства на алгоритмот
  • дискретност
  • јасност
  • сигурност
  • ефективноста
  • масовен карактер
• извршител

• карактеристики на изведувачот
  • опсег на задачи што треба да се решат
  • среда
  • режим на работа
  • команден систем
• формално извршување на алгоритмот

3.1.1. Концепт на алгоритам

Секој човек во Секојдневниот живот, на студирање или на работа, решава огромен број проблеми со различна сложеност. Комплексните проблеми бараат многу размислување за да се најде решение; Човек решава едноставни и познати задачи без размислување, автоматски. Во повеќето случаи, решението за секој проблем може да се подели на едноставни фази (чекори). За многу такви задачи (инсталација софтвер, склопување кабинет, креирање веб-локација, управување со технички уред, купување авионски билет преку Интернет и сл.) се веќе развиени и понудени чекор по чекор инструкции, што, кога се извршува постојано, може да доведе до посакуваниот резултат.

Пример 1. Задачата „Најди ја аритметичката средина на два броја“ се решава во три чекори:

• размислете за два броја;
• додадете два броја на ум;
• добиениот износ поделете го со 2.

Пример 2. Задачата „Депонирајте пари на вашата телефонска сметка“ е поделена на следниве чекори:

• одете до терминалот за плаќање;
• изберете телекомуникациски оператор;
• внесете телефонски број;
• проверете дали внесениот број е точен;
• вметнете банкнота во примачот на сметки;
• почекајте порака за кредитирање на пари на вашата сметка;
• прими чек.

Пример 3. Фазите на решавање на проблемот „Нацртајте смешен еж“ се претставени графички:

Пронаоѓањето на аритметичката средина, депонирањето пари на телефонска сметка и цртањето еж се, на прв поглед, сосема различни процеси. Но, тие имаат заедничка карактеристика: секој од овие процеси е опишан со низа кратки инструкции, строгото придржување до кое ви овозможува да го добиете потребниот резултат. Секвенците од инструкции дадени во примерите 1-3 се алгоритми за решавање на соодветните проблеми. Извршителот на овие алгоритми е личност.

Алгоритмот може да биде опис на одредена низа на пресметки (пример 1) или чекори од нематематичка природа (примери 2-3). Но, во секој случај, пред неговиот развој, на почетни услови(влезни податоци) и што треба да се добие (резултат). Можеме да кажеме дека алгоритмот е опис на секвенцата на чекори за решавање на проблем, што води од почетните податоци до потребниот резултат.

Општо земено, дијаграмот за работа на алгоритмот може да се претстави на следниов начин (сл. 3.1):

Ориз. 3.1.
Општа шема на алгоритмот

Алгоритмите се правила за додавање, одземање, множење и поделба на броеви, граматички правила, правила на геометриски конструкции, итн., Студирани во училиште.

Анимациите „кои работат со алгоритам“, „Најголем заеднички делител“, „најмалку вообичаен повеќекратен“ (http://school-collection.edu.ru/) ќе ви помогне да запомните некои алгоритми што се изучуваат на руски јазик и лекции по математика.

Пример 4. Некој алгоритам води до фактот дека од еден синџир на знаци се добива нов синџир на следниов начин:

1. Се пресметува должината (во знаци) на изворната низа на знаци.
2. Ако должината на оригиналниот синџир е непарна, тогаш бројот 1 се додава на оригиналниот синџир од десната страна, во спротивно ланецот не се менува.
3. Симболите се заменуваат во парови (првиот со вториот, третиот со четвртиот, петтиот со шестиот итн.).
4. Бројот 2 се додава десно од добиениот синџир.

Добиениот синџир е резултат на алгоритмот.

Значи, ако почетниот ланец беше #Б, тогаш резултатот од алгоритмот ќе биде ланецот #A1B2, и ако почетниот ланец беше ABC@, тогаш резултатот од алгоритмот ќе биде ланецот BA@B2.

3.1.2. Извршувач на алгоритам

Секој алгоритам е дизајниран за одреден изведувач.

Има формални и неформални изведувачи. Официјален изведувач секогаш ја извршува истата команда на ист начин. Неформалниот извршител може да изврши команда на различни начини.

Да го разгледаме подетално збирот на формални изведувачи. Официјалните изведувачи се екстремно разновидни, но за секоја од нив може да се наведат следниве карактеристики: опсегот на задачи што треба да се решат (цел), околината, командниот систем и начинот на работа.

Опсег на задачи што треба да се решат. Секој изведувач е создаден за да реши одреден спектар на проблеми - конструирање на ланци на симболи, вршење пресметки, конструирање цртежи во авион, итн.

Уметничка средина. Областа, поставката, условите во кои работи изведувачот обично се нарекуваат средина на дадениот изведувач. Изворните податоци и резултатите од кој било алгоритам секогаш припаѓаат на околината на изведувачот за кого е наменет алгоритмот.

Команден систем на извршител. Упатството до изведувачот да изврши посебно завршено дејство се нарекува команда. Множеството од сите команди што може да ги изврши некој извршител го формира системот на команди за овој извршител (SKI). Алгоритмот се составува земајќи ги предвид можностите на одреден изведувач, со други зборови, во системот на команди на изведувачот кој ќе го изврши.

Режими за работа на изведувачи. За повеќето изведувачи, режими за директна контрола и контрола на програмата. Во првиот случај, изведувачот чека команди од некоја личност и веднаш ја извршува секоја примена команда. Во вториот случај, на изведувачот прво му се дава целосна низа наредби (програма), а потоа тој ги извршува сите овие команди во автоматски режим. Голем број изведувачи работат само во еден од наведените режими.

Ајде да разгледаме примери на изведувачи.

Пример 5. Изведувач Желката се движи на екранот на компјутерот, оставајќи трага во форма на линија. Командниот систем на желката се состои од две команди:

Напред n (каде n е цел број) - предизвикува желката да помести n чекори во насока на движење - во насока во која главата и телото се свртени;

Десно m (каде што m е цел број) - предизвикува правецот на движење на желката да се промени за m степени во насока на стрелките на часовникот.

Запис Повторете k [<Команда1> <Команда2> ... <Командаn>] значи дека низата наредби во загради ќе се повторува k пати.

Размислете која фигура ќе се појави на екранот откако желката ќе го заврши следниот алгоритам.

Повторете 12 [десно 4 5 напред 20 десно 45]

Пример 6. Системот на команди на извршители Компјутерот се состои од две команди, на кои им се доделуваат броеви:

1 - одземе 1
2 - помножете се со 3

Првиот од нив го намалува бројот за 1, вториот го зголемува бројот за 3 пати. Кога пишувате алгоритми, за краткост, се означени само броеви на команди. На пример, алгоритмот 21212 ја означува следната низа на команди:

помножете се со 3
одземе 1
помножете се со 3
одземе 1
помножете се со 3

Користејќи го овој алгоритам, бројот 1 ќе се претвори во 15: ((1-3-1)-3-1)-3 = 15.

Пример 7. Роботот изведувач работи на карирано поле, меѓу соседните ќелии може да има ѕидови. Роботот се движи по ќелиите на полето и може да ги изврши следните команди, на кои им се доделуваат броеви:

1 - горе
2 - долу
3 - Точно
4 - Лево

При извршување на секоја таква команда, роботот се движи во соседната ќелија во наведената насока. Ако има ѕид во оваа насока помеѓу ќелиите, тогаш Роботот е уништен. Што ќе се случи со роботот ако ја изврши секвенцата на командите 32323 (тука броевите ги означуваат командните броеви), почнувајќи да се движат од ќелијата А? Која секвенца на команди треба да ја изврши роботот за да се пресели од ќелијата А во ќелијата Б без да се сруши кога ќе удри во ѕидовите?

Кога развивате алгоритам:

1. се идентификуваат објектите што се појавуваат во проблемот, својствата на објектите, односите меѓу објектите и можни дејствасо предмети;
2. се одредуваат првичните податоци и потребниот резултат;
3. се одредува редоследот на дејства на изведувачот, обезбедувајќи премин од првичните податоци до резултатот;
4. редоследот на дејствата се снима со помош на команди вклучени во командниот систем на извршителот.

Можеме да кажеме дека алгоритам е модел на активноста на извршителот на алгоритмот.

3.1.3. Карактеристики на алгоритмот

Не секоја инструкција, низа инструкции или акционен план може да се смета за алгоритам. Секој алгоритам нужно ги има следните својства: дискретност, разбирливост, сигурност, ефективност и масовен карактер.

Својството на дискретност значи дека патот до решавање на проблемот е поделен на посебни чекори (дејства). Секоја акција има соодветна инструкција (наредба). Само по извршувањето на една команда, извршителот може да започне со извршување на следната команда.

Имотот на разбирливоста значи дека алгоритмот се состои само од команди вклучени во системот на команди на изведувачот, т.е. на такви команди што изведувачот може да ги согледа и според кои може да ги изврши потребните активности.

Својството на сигурност значи дека алгоритмот не содржи команди чиешто значење може двосмислено да се толкува од изведувачот; Ситуациите се неприфатливи кога, по извршувањето на следната команда, на изведувачот не му е јасно која команда да ја изврши на следниот чекор.

Својството на ефикасност значи дека алгоритмот мора да може да добие резултат по конечен, можеби многу голем број чекори. Во овој случај, резултатот се смета не само за одговорот утврден со изјавата на проблемот, туку и за заклучокот за невозможноста да се продолжи да се реши овој проблем од која било причина.

Својството на масовно производство значи дека алгоритмот мора да обезбеди можност за негова примена за решавање на кој било проблем од одредена класа на проблеми. На пример, алгоритмот за наоѓање корени на квадратна равенка треба да биде применлив за која било квадратна равенка, алгоритмот за преминување улица треба да биде применлив насекаде на улицата, алгоритмот за подготовка на лек треба да биде применлив за подготовка на која било количина од него, итн.

Пример 8. Да разгледаме еден од методите за наоѓање на сите прости броеви што не надминуваат n. Овој метод се нарекува „сито на Ератостен“, именуван по старогрчкиот научник Ератостен кој го предложил.

За да ги најдете сите прости броеви не поголеми од даден број n, следејќи го методот на Ератостен, треба да ги извршите следните чекори:

1. запишете ги сите цели броеви од 2 до n по ред (2, 3, 4, ..., n);
2. рамка 2 - првиот прост број;
3. пречкртајте ги од списокот сите броеви деливи со последниот пронајден прост број;
4. пронајдете го првиот необележан број (означените броеви се прецртани броеви или броеви затворени во рамка) и затворете го во рамка - ова ќе биде уште еден прост број;
5. повторете ги чекорите 3 и 4 додека не останат необележани броеви.

Можете да добиете повизуелна идеја за методот за наоѓање прости броеви користејќи ја анимацијата „Ситото на Ератостен“ (http://school-collection.edu.ru/).

Разгледуваната низа на дејства е алгоритам, бидејќи ги задоволува следниве својства:

• дискретност - процесот на пронаоѓање на прости броеви е поделен на чекори;
• разбирливост - секоја команда е разбирлива за ученик од 9-то одделение кој го изведува овој алгоритам;
• сигурност - секоја команда ја толкува и извршува изведувачот недвосмислено; има инструкции за редоследот на извршување на командите;
• ефективност - по одреден број чекори се постигнува резултатот;
• масовен карактер - низата на дејства е применлива за секое природно n.

Разгледаните својства на алгоритмот ни овозможуваат да дадеме попрецизна дефиниција на алгоритмот.

3.1.4. Можност за автоматизација на човековите активности

Развивањето на алгоритам обично е трудоинтензивна задача која бара од човекот да има длабоко знаење, генијалност и многу време.

Решавањето на проблемот со помош на готов алгоритам бара само изведувачот строго да ги следи дадените инструкции.

Пример 9. Од куп што содржи кој било број на предмети поголем од три, двајца играчи наизменично земаат по еден или два предмети. Победникот е оној кој може да ги подигне сите преостанати ставки при неговиот следен потег.

Ајде да разгледаме алгоритам, по кој првиот играч сигурно ќе обезбеди победа.

1. Ако бројот на предмети во купот е повеќекратен од 3, тогаш отстапете му го на противникот, инаку започнете ја играта.
2. Со вашиот следен потег, секој пат додавајте го бројот на предмети земени од вашиот противник на 3 (бројот на преостанатите објекти мора да биде повеќекратен од 3).

Изведувачот може да не навлегува во смислата на она што го прави и да не резонира зошто постапува вака, а не поинаку, односно може формално да дејствува. Способноста на изведувачот да дејствува формално обезбедува можност за автоматизирање на човековата активност. За ова:

1. процесот на решавање на проблем е претставен како низа од едноставни операции;
2. се создава машина ( автоматски уред), способни да ги извршуваат овие операции во секвенцата наведена во алгоритмот;
3. едно лице е ослободено од рутински активности, извршувањето на алгоритмот е доверено на автоматски уред.

Најважниот

Изведувач - некој предмет (лице, животно, технички уред), способен за извршување на одреден сет на команди. Официјален изведувач секогаш ја извршува истата команда на ист начин. За секој формален изведувач, можете да наведете: опсегот на задачи што треба да се решат, околината, командниот систем и режимот на работа.

Алгоритам е опис на низа дејства наменети за специфичен изведувач што води од почетните податоци до бараниот резултат, кој има својства на дискретност, разбирливост, сигурност, ефективност и масовен карактер.

Способноста на изведувачот да дејствува формално обезбедува можност за автоматизирање на човековата активност.

Прашања и задачи

1. Како се нарекува алгоритам?
2. Најдете синоними за зборот „рецепт“.
3. Наведете примери на алгоритми што сте ги учеле на училиште.
4. Кој може да биде извршител на алгоритмот?
5. Наведете пример за формален изведувач. Наведете пример кога некое лице се однесува како формален изведувач.
6. Кои команди треба да ги извршува роботот како: а) касиер во продавница; б) чувар; в) чувар?
7. Што го одредува опсегот на задачи што ги извршува изведувачот на „компјутерот“?
8. Размислете како изведувач обработка на текст, достапно на вашиот компјутер. Опишете го опсегот на задачи што ги решава овој изведувач и неговата околина.
9. Што е тим, систем на команди на изведувачи?
10. Наведете ги главните својства на алгоритмот.
11. До што може да доведе отсуството на кое било својство во алгоритам? Наведи примери.
12. Зошто е важно да може формално да се изврши алгоритам?
13. Низата од броеви е конструирана според следниот алгоритам: првите два броја од низата се земаат еднакви на 1; Секој следен број во низата се зема дека е еднаков на збирот на двата претходни броја. Запишете ги првите 10 термини на оваа секвенца.
14. Некои алгоритами добиваат нов синџир од една низа знаци како што следува. Прво, се пишува оригиналниот синџир на знаци, по него се пишува оригиналниот синџир на знаци во обратен редослед, потоа се пишува буквата што следи во руската азбука по буквата што била на последното место во оригиналниот синџир. Ако последното место во оригиналниот синџир е буквата Z, тогаш буквата A се пишува како следната буква. Добиениот синџир е резултат на алгоритмот. На пример, ако оригиналниот синџир на знаци беше DOM, тогаш резултатот од алгоритмот ќе биде синџирот DOMMODN. Даден е низа на ликови. Колку букви О ќе има во синџирот на симболи што ќе се добијат ако го примените алгоритмот на овој синџир, а потоа повторно го примените алгоритмот на резултатот од неговата работа?
15. Најдете анимација на чекорите на алгоритмот на Ератостен на Интернет. Користете го алгоритмот на Ератостен за да ги пронајдете сите прости броеви што не надминуваат 50.
16. Каков ќе биде резултатот од извршувањето на желка (види Пример 5) на алгоритмот?
    Повторете 8 [десно 45 напред 45]
17. Запишете алгоритам за извршителот на Калкулаторот (пример 6), кој содржи не повеќе од 5 команди:
    а) примање од бројот 3 бројот 16;
    б) Примање од бројот 1 Бројот 25.
18. Системот на команди на извршители Конструкторот се состои од две команди, на кои им се доделуваат броеви:
    1 - додели 2
    2 - подели со 2

    Според првиот од нив, на бројот од десната страна се додава 2, според вториот, бројот се дели со 2. Како ќе се конвертира бројот 8 ако изведувачот го изврши алгоритамот 22212? Направете алгоритам во командниот систем на овој извршител, според кој бројот 1 ќе се претвори во бројот 16 (алгоритмот треба да содржи не повеќе од 5 команди).

19. Во која ќелија треба да се наоѓа роботскиот изведувач (пример 7) за да се врати во него по извршувањето на алгоритмот 3241?

| § 2.1. Алгоритми и извршители

Лекција 14
§ 2.1. Алгоритми и извршители

Клучни зборови:

Алгоритам
својства на алгоритмот (дискретност; разбирливост; сигурност; ефективност; масовен карактер)
извршител
карактеристики на изведувачот (опсег на задачи што треба да се решат; околина; режим на работа; команден систем)
формално извршување на алгоритмот

2.1.1. Концепт на алгоритам

Секој човек во секојдневниот живот, на студирање или на работа решава огромен број проблеми со различна сложеност. Комплексните проблеми бараат многу размислување за да се најде решение; Човек решава едноставни и познати задачи без размислување, автоматски. Во повеќето случаи, решението за секој проблем може да се подели на едноставни фази (чекори). За многу од овие задачи (инсталирање софтвер, составување кабинет, креирање веб-локација, управување со технички уред, купување авионски билет преку Интернет итн.), чекор-по-чекор инструкции веќе се развиени и се нудат, секвенцијалниот чија имплементација може да доведе до посакуваниот резултат.

Пример 1.Задачата „Најди ја аритметичката средина на два броја“ се решава во три чекори:

1) размислете за два броја;
2) додадете два планирани броја;
3) добиениот износ поделете го со 2.

Пример 2.Задачата „Депонирајте пари на вашата телефонска сметка“ е поделена на следниве чекори:

1) одете до терминалот за плаќање;
2) изберете телекомуникациски оператор;
3) внесете телефонски број;
4) проверете дали внесениот број е точен;
5) вметнува банкнота во сметководителот;
6) почекајте порака за кредитирање на пари на вашата сметка;
7) прими чек.

Пример 3.Фазите на решавање на проблемот „Нацртајте смешен еж“ се претставени графички:

Пронаоѓањето на аритметичката средина, депонирањето пари на телефонска сметка и цртањето еж се, на прв поглед, сосема различни процеси. Но, тие имаат заедничка карактеристика: секој од овие процеси е опишан со низа кратки инструкции, строгото придржување до кое ви овозможува да го добиете потребниот резултат. Секвенците од инструкции дадени во примерите 1-3 се алгоритми за решавање на соодветните проблеми. Извршителот на овие алгоритми е личност.

Алгоритмот може да биде опис на одредена низа на пресметки (пример 1) или чекори од нематематичка природа (примери 2-3). Но, во секој случај, пред неговиот развој, мора јасно да се дефинираат првичните услови (почетни податоци) и она што треба да се добие (резултат). Можеме да кажеме дека алгоритам е опис на низата чекори во решавањето на проблемот, што води од почетните податоци до бараниот резултат.

Општо земено, дијаграмот за работа на алгоритмот може да се претстави на следниов начин (сл. 2.1).

Ориз. 2.1. Општа шема на алгоритмот

Алгоритмите се правила на собирање, одземање, множење и делење на броеви кои се изучуваат во училиште, многу граматички правила, правила на геометриски конструкции итн.

Анимациите „Работа со алгоритам“ (193576), „Најголем заеднички делител“ (170363), „Најмал заеднички множител“ (170390) ќе ви помогнат да запомните некои алгоритми изучени на часови по руски јазик и математика (http://sc.edu. ru /).

Пример 4.Некој алгоритам води до фактот дека од еден синџир на знаци се добива нов синџир на следниов начин:

1. Се пресметува должината (во знаци) на оригиналната низа знаци.
2. Ако должината на оригиналниот синџир е непарна, тогаш бројот 1 се додава на оригиналниот синџир од десната страна, во спротивно ланецот не се менува.
3. Симболите се заменуваат во парови (првиот со вториот, третиот со четвртиот, петтиот со шестиот итн.).
4. Бројот 2 се додава десно од добиениот синџир.

Добиениот синџир е резултат на алгоритмот.

Значи, ако почетниот синџир беше A#B, тогаш резултатот од алгоритмот ќе биде синџирот #A1B2, а ако почетниот синџир беше ABC@, тогаш резултатот од алгоритмот ќе биде синџирот BA@B2.

2.1.2. Извршувач на алгоритам

Секој алгоритам е дизајниран за одреден изведувач.

Извршител е предмет (лице, животно, технички уред) способен да изврши одреден сет на команди.

Разликувајте формални и неформални изведувачи. Официјален изведувач секогаш ја извршува истата команда на ист начин. Неформалниот извршител може да изврши команда на различни начини.

Да го разгледаме подетално збирот на формални изведувачи. Официјалните изведувачи се екстремно разновидни, но за секоја од нив може да се наведат следниве карактеристики: опсегот на задачи што треба да се решат (цел), околината, командниот систем и начинот на работа.

Опсег на задачи што треба да се решат. Секој изведувач е создаден да реши одреден опсег на проблеми - конструирање синџири од симболи, вршење пресметки, конструирање цртежи на рамнина итн.

Уметничка средина. Областа, поставката, условите во кои работи изведувачот обично се нарекуваат средина на дадениот изведувач. Изворните податоци и резултатите од кој било алгоритам секогаш припаѓаат на околината на изведувачот за кого е наменет алгоритмот.

Команден систем на извршител. Упатството до изведувачот да изврши посебно завршено дејство се нарекува команда. Множеството од сите команди што може да ги изврши некој извршител го формира системот на команди за овој извршител (SKI). Алгоритмот се составува земајќи ги предвид можностите на одреден изведувач, со други зборови, во системот на команди на изведувачот кој ќе го изврши.

Режими за работа на изведувачи. За повеќето изведувачи, обезбедени се режими за директна контрола и контрола на програмата. Во првиот случај, изведувачот чека команди од некоја личност и веднаш ја извршува секоја примена команда. Во вториот случај, на изведувачот прво му се дава целосна низа на команди (програма), а потоа тој ги извршува сите овие команди автоматски. Голем број изведувачи работат само во еден од наведените режими.

Ајде да разгледаме примери на изведувачи.

Пример 5.Изведувач Желката се движи на екранот на компјутерот, оставајќи трага во форма на линија.

Командниот систем Turtle се состои од следниве команди:

1. Напред n (каде n е цел број) - предизвикува желката да помести n чекори во насока на движење - во насоката во која главата и телото се свртени;
2. Десно m (каде m е цел број) - предизвикува промена во насоката на движење на Желката за t степени во насока на стрелките на часовникот.
Снимајте Повторете k [<Команда1> <Команда2> ... <Командаn>] значи дека низата наредби во загради ќе се повторува k пати.

Размислете која фигура ќе се појави на екранот откако желката ќе го заврши следниот алгоритам.
Повторете 12 [десно 45 напред 20 десно 45]

Пример 6.Системот на команди на извршители Компјутерот се состои од две команди, на кои им се доделуваат броеви:

1 - одземе 1
2 - помножете се со 3

Првиот од нив го намалува бројот за 1, вториот го зголемува бројот за 3 пати. Кога пишувате алгоритми, за краткост, се означени само броеви на команди. На пример, алгоритмот 21212 ја означува следната низа на команди:

Помножете се со 3
одземе 1
помножете се со 3
одземе 1
помножете се со 3

Користејќи го овој алгоритам, бројот 1 ќе се претвори во 15:

((1 3 - 1) 3 - 1) 3 = 15.

Пример 7.Роботот изведувач работи на карирано поле, меѓу соседните ќелии може да има ѕидови. Роботот се движи по ќелиите на полето и може да ги изврши следните команди, на кои им се доделуваат броеви:

1 - нагоре
2 - надолу
3 - нели
4 - лево

При извршување на секоја таква команда, роботот се движи во соседната ќелија во наведената насока. Ако има ѕид во оваа насока помеѓу ќелиите, тогаш Роботот е уништен.

Што ќе се случи со роботот ако ја изврши низата наредби 32323 (тука бројките означуваат броеви на команди), почнувајќи да се движи од ќелијата А? Која секвенца на команди треба да ја изврши роботот за да се пресели од ќелијата А во ќелијата Б без да се сруши кога ќе удри во ѕидовите?

Кога развивате алгоритам:

1) се идентификуваат објектите што се појавуваат во проблемот, се воспоставуваат својствата на предметите, односите меѓу предметите и можните дејства со предметите;
2) се утврдуваат првичните податоци и бараниот резултат;
3) се одредува редоследот на дејства на изведувачот, обезбедувајќи премин од првичните податоци до резултатот;
4) редоследот на дејства се снима со помош на команди вклучени во командниот систем на изведувачот.

Можеме да кажеме дека алгоритам е модел на активноста на извршителот на алгоритмот.

2.1.3. Карактеристики на алгоритмот

Не секоја инструкција, низа инструкции или акционен план може да се смета за алгоритам. Секој алгоритам нужно ги има следните својства: дискретност, разбирливост, сигурност, ефективност и масовен карактер.

Дискретна сопственостзначи дека патот до решавање на проблемот е поделен на посебни чекори (дејства). Секоја акција има соодветна инструкција (наредба). Само по извршувањето на една команда, извршителот може да започне со извршување на следната команда.

Својство за разбирливостзначи дека алгоритмот се состои само од команди вклучени во системот на команди на изведувачот, т.е. од такви команди што изведувачот може да ги согледа и според кои може да ги изврши бараните дејства.

Сопственост на сигурностзначи дека алгоритмот не содржи наредби чие значење изведувачот може двосмислено да го толкува; Ситуациите се неприфатливи кога, по извршувањето на следната команда, на изведувачот не му е јасно која команда да ја изврши следната. Благодарение на ова, резултатот од алгоритмот е уникатно одреден од множеството почетни податоци: ако алгоритмот се примени неколку пати на истиот сет на почетни податоци, тогаш излезот секогаш го произведува истиот резултат.

Изведба сопственостзначи дека алгоритмот мора да обезбеди резултат по конечен, можеби многу голем број чекори. Во овој случај, резултатот се смета не само за одговорот утврден со изјавата за проблемот, туку и за заклучокот за неможноста да се продолжи да се решава овој проблем од која било причина.

Имот од масовен карактерзначи дека алгоритмот мора да обезбеди можност за негова примена за решавање на кој било проблем од одредена класа на проблеми. На пример, алгоритмот за наоѓање корени на квадратна равенка треба да биде применлив за која било квадратна равенка, алгоритмот за преминување улица треба да биде применлив насекаде на улицата, алгоритмот за подготовка на лек треба да биде применлив за подготовка на која било количина од него, итн.

Пример 8.Да разгледаме еден од методите за наоѓање на сите прости броеви кои не надминуваат некој природен број n. Овој метод се нарекува „сито на Ератостен“ по старогрчкиот научник Ератостен (3 век п.н.е.) кој го предложил.

За да ги најдете сите прости броеви не поголеми од даден број n, следејќи го методот на Ератостен, треба да ги извршите следните чекори:

1) запишете ги по ред сите природни броеви од 2 до n (2, 3, 4, ..., n);
2) рамка 2 - првиот прост број;
3) пречкртајте ги од списокот сите броеви деливи со последниот пронајден прост број;
4) најдете го првиот необележан број (обележаните броеви се пречкртани броеви или броеви затворени во рамка) и затворете го во рамка - ова ќе биде уште еден прост број;
5) повторете ги чекорите 3 и 4 додека не останат неозначени броеви.

Можете да добиете повизуелна идеја за методот на пронаоѓање на прости броеви користејќи ја анимацијата „Ситото на Ератостен“ (180279) објавена во Единствената колекција на дигитални образовни ресурси.

Разгледуваната низа на дејства е алгоритам, бидејќи ги задоволува следниве својства:

дискретност- процесот на пронаоѓање на прости броеви е поделен на чекори;
разбирливост- секоја команда е разбирлива за ученик од 8-мо одделение кој го изведува овој алгоритам;
сигурност- секоја команда ја толкува и извршува изведувачот недвосмислено; има инструкции за редоследот на извршување на командите;
ефективноста- по одреден број чекори се постигнува резултатот;
масовен карактер- низата на дејства е применлива за секој природен број n.

Разгледаните својства на алгоритмот ни овозможуваат да дадеме попрецизна дефиниција на алгоритмот.

Алгоритам е опис на низа дејства наменети за специфичен изведувач што води од почетните податоци до бараниот резултат, кој има својства на дискретност, разбирливост, сигурност, ефективност и масовен карактер.

2.1.4. Можност за автоматизација на човековите активности

Развивањето на алгоритам обично е трудоинтензивна задача која бара од човекот да има длабоко знаење, генијалност и многу време.

Решавањето на проблемот со помош на готов алгоритам бара само изведувачот строго да ги следи дадените инструкции.

Пример 9.Од куп што содржи кој било број на предмети поголем од три, двајца играчи наизменично земаат по еден или два предмети. Победникот е оној кој може да ги подигне сите преостанати ставки при неговиот следен потег.

Ајде да разгледаме алгоритам, по кој првиот играч сигурно ќе обезбеди победа.

1. Ако бројот на предмети во купот е повеќекратен од 3, тогаш отстапете го на противникот, инаку започнете ја играта со земање 1 или 2 предмети, така што бројот на предмети што преостануваат да биде повеќекратен од 3.
2. Со вашиот следен потег, секој пат додавајте го бројот на предмети земени од вашиот противник на 3 (бројот на преостанатите објекти мора да биде повеќекратен од 3).

Изведувачот може да не навлегува во смислата на она што го прави и да не резонира зошто постапува вака, а не поинаку, односно може формално да дејствува. Способноста на изведувачот да дејствува формално обезбедува можност за автоматизирање на човековата активност. За ова:

1) процесот на решавање на проблем е претставен како низа од едноставни операции;
2) се создава машина (автоматски уред) која е способна да ги извршува овие операции во низата наведена во алгоритмот;
3) едно лице е ослободено од рутински активности, извршувањето на алгоритмот е доверено на автоматски уред.

НАЈВАЖНИОТ

Извршител- некој предмет (лице, животно, технички уред) способен да изврши одреден сет на команди.

Официјален изведувач секогаш ја извршува истата команда на ист начин. За секој формален извршител можете да наведете: опсег на задачи што треба да се решат, околина, команден систем и режим на работа.

Алгоритам- опис на редоследот на дејства наменети за конкретен изведувач што води од првичните податоци до бараниот резултат, кој има својства на дискретност, разбирливост, сигурност, ефективност и масовен карактер.

Способност на изведувачот да дејствува формалнообезбедува способност за автоматизирање на човековите активности.

Прашања и задачи

1. Прочитајте ги материјалите за презентација за параграфот содржан во електронска апликацијадо учебникот. Дали презентацијата ги надополнува информациите содржани во текстот на параграфот? Кои слајдови би можеле да ги додадете во вашата презентација?

2. Што се нарекува алгоритам?

3. Изберете синоними за зборот „рецепт“.

4. Наведете примери за алгоритми што сте ги учеле на училиште.

5. Кој може да биде извршител на алгоритмот?

6. Наведете пример за формален изведувач. Наведете пример кога некое лице се однесува како формален изведувач.

7. Што го одредува опсегот на задачи што ги извршува „компјутерот“ изведувач?

8. Сметајте го процесорот на текст на вашиот компјутер како извршител. Опишете го опсегот на задачи што ги решава овој изведувач и неговата околина.

9. Што е тим, систем на команди на изведувачи?

10. Кои команди треба да ги извршува роботот следниве функции:

а) касиерка во продавница;
б) чувар;
в) чувар?

11. Наведете ги главните својства на алгоритмот.

12. До што може да доведе отсуството на кое било својство во алгоритам? Наведи примери.

13. Која е важноста да се биде во можност формално да се изврши алгоритам?

14. Низата од броеви е конструирана според следниот алгоритам: првите два броја од низата се земаат еднакви на 1; Секој следен број во низата се зема дека е еднаков на збирот на двата претходни броја. Запишете ги првите 10 термини на оваа секвенца. Откријте како се нарекува оваа секвенца.

15. Одреден алгоритам добива нов синџир од една низа знаци како што следува. Прво, се пишува оригиналниот синџир на знаци, по него се пишува оригиналниот синџир на знаци во обратен редослед, потоа се пишува буквата што следи во руската азбука по буквата што била на последното место во оригиналниот синџир. Ако буквата „I“ е на последното место во оригиналниот синџир, тогаш буквата „А“ е напишана како следната буква. Добиениот синџир е резултат на алгоритмот. На пример, ако оригиналниот синџир на знаци беше „HOUSE“, тогаш резултатот од алгоритмот ќе биде синџирот „DOMMODN“. Дадена е стринг на ликот „COM“. Колку букви „О“ ќе има во синџирот на знаци што ќе се добијат ако го примените алгоритмот на овој синџир, а потоа повторно го примените алгоритмот на резултатот од неговата работа?

16. Најдете анимација на чекорите на алгоритмот на Ератостен на Интернет. Користете го алгоритмот на Ератостен за да ги пронајдете сите прости броеви што не надминуваат 50.

17. Каков ќе биде резултатот од извршувањето на желка (види пример 5) на алгоритмот?

18. Запишете алгоритам за извршителот Калкулатор (види пример 6), кој не содржи повеќе од 5 команди:

а) примање од бројот 3 бројот 16;
б) примање од бројот 1 бројот 25.

19. Систем на команди на изведувачи Конструкторот се состои од две команди, на кои им се доделуваат броеви:

1 - додели 2
2 - подели со 2

Според првиот од нив, на бројот од десната страна се додава 2, според вториот, бројот се дели со 2. Како ќе се конвертира бројот 8 ако изведувачот го изврши алгоритамот 22212? Направете алгоритам во командниот систем на овој извршител, според кој бројот 1 ќе се претвори во бројот 16 (алгоритмот треба да содржи не повеќе од 5 команди).

20. Во која ќелија треба да се наоѓа Robot performer (пример 7) за да се врати во него по извршувањето на алгоритмот 3241?

Слободен софтвер:

КуМир систем - Збир на образовни светови (преземете ја архивата на програмата од веб-страницата) или посетете ја страницата КуМир ((http://www.niisi.ru/kumir/)

Ве молиме суспендирајте го AdBlock на оваа страница.

Во оваа лекција ќе разгледаме некои теоретски концепти кои го формализираат концептот на програмирање. Во исто време, ние попрецизно ќе ја формулираме главната задача на вашата обука.

За почеток ви предлагам да си поиграте малку со следната детска играчка. Завршете ги првите пет задачи, вратете се назад и продолжете со читање на лекцијата.

Сл.1 Слика од екранот на полето за играње на Code.org

Се надевам дека сè ти успеа. Сега, користејќи го овој пример, ќе опишеме неколку основни концепти:

• извршител;
• систем на команди на изведувачи;
• алгоритам.

Во играчката контролираме црвена птица. Целта на секоја фаза е да се привлече птицата до свиња. Птицата може да изврши одредени команди, на пример: да се движи напред, да се сврти лево, да се сврти десно, итн.

Едно лице, машина или уред што може да изврши некои команди се нарекува извршител. Во оваа играчка, очигледно, изведувачот е птица. Сетот на команди што изведувачот ги разбира и може да ги изврши се нарекува систем на команди на извршители.

Редоследот на командите што изведувачот мора да ги изврши за да реши проблем се нарекува алгоритам.

Неопходно е да се фокусираме на неколку точки.

Извршителот може да изврши само оние команди што се вклучени во неговиот команден систем.

Ова значи, на пример, дека не можете да му напишете на изведувачот на птици: „Оди на свиња!“ Поточно можете да го запишете, но ништо нема да се случи, затоа што ... вршителот на таквите наредби не знае.

Можете да ги запишете достапните команди по кој било редослед што го сметате за точен. Ваша задача како програмер е да поделите голема сложена задача на мали поединечни чекори, од кои секој ќе биде разбирлив за изведувачот. Принципот на „раздели и владеј“ повторно функционира.

Изведувачот го прави токму она што алгоритмот му кажува да го направи.

Изведувачот на птици е многу доверлив. Таа не го доведува во прашање она што го пишувате во програмата. Ако, на пример, заборавите да ја свртите птицата, таа ќе се урне во ѕидот. Затоа, мора да следите сè сами.

Вашите идни програми честопати нема да работат како што сте замислиле. Секому му се случуваат грешки. Овде е важно да разберете дека не е компјутерот глупав, туку сте направиле грешка во алгоритмот. Немојте да бидете како лоши програмери, на кои програмата секогаш им е виновна за се.

Сега да продолжиме од илустративниот пример кон компјутерската реалност. Ние пишуваме програми за компјутерот, што значи дека компјутерот во нашиот случај е изведувачот. Командниот систем е стандардни функции и конструкции на јазикот C.

Која е главната цел на вашето предавање на основите на програмирањето? Совладете ја вештината на алгоритамско размислување. Тоа е, научете да го запишете решението за различни проблеми во форма на алгоритам за одреден изведувач (во нашиот случај, компјутер).

Значи, да резимираме:

Компјутерска програма– алгоритам за решавање на проблем, напишан на програмски јазик.

Алгоритам е прецизен опис на редоследот на дејства што изведувачот мора да ги изврши за да реши проблем.

Извршител е лице или некој уред кој може да разбере и изврши одреден сет на команди.

Зборот „алгоритам“ потекнува од името на арапскиот математичар Ал-Хваризми од 9 век, кој ги формулирал правилата за извршување аритметички операции.

Алгоритам– точна и разбирлива инструкција до изведувачот да ја изврши конечната секвенца на команди што води од почетните податоци до почетниот резултат.

Примери: дневна рутина, редослед на готвење, инструкции итн.)

Извршувач на алгоритам– тоа е оној кој го извршува алгоритмот (лице, животно, машина, компјутер).

Команден систем на извршител- ова е целиот сет на команди што изведувачот знае да ги изврши (разбира). Алгоритмот може да се изгради само од команди вклучени во системот на команди на извршители.

На пример, изведувач Роботот може да врши команди напред, назад, лево, десно, бојадисување. Се движи низ клеточно поле ограничено со ѕид и содржи ѕидови. Роботот не може да помине низ ѕидот.

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

1.Перформанси (екстремитет)– способност да се добие резултат од почетните податоци во конечен број чекори. (На пример, при извршување на алгоритмот за собирање 2 броја, треба да се добие збирот).

2.Масовен карактер– можност за примена на алгоритмот на голем број различни изворни податоци. (На пример, можете да додадете какви било 2 броја, знаејќи го алгоритмот за додавање.)

3.Детерминизам(сигурност, точност) – секоја команда мора уникатно да го одреди дејството на изведувачот.

4.Разбирливост- Командата мора да биде напишана на јазик разбирлив за компјутерот.

5.Дискретност- Поделување на алгоритмот во одделни команди.

Начини за пишување на алгоритмот:

1) На природен јазик - снимање во форма на одделни команди на јазик разбирлив за луѓето.

2) Графички - На јазикот на графиконите, користејќи геометриски форми (овален, правоаголник, паралелограм, ромб).

3) На алгоритмички јазик - јазик за пишување алгоритми за настава за програмирање. Наредбите се напишани на руски.

4) Во програмски јазик - програма. Програмски јазици: Основни, Паскал, Ц, Visual Basic.

Б7.Базични алгоритмички структури: следниве, разгранување, јамка; Слика на блок дијаграми. Разложување на задачите на подзадачи. Помошни алгоритми.

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

Основни алгоритамски конструкциисе линеарна низа од чекори (или следните), разгранување и циклус.

Се повикува алгоритам во кој командите се извршуваат последователно една по друга линеарен алгоритам.

Вака изгледа линеарен алгоритам на јазикот на блок дијаграмите:

Пример: алгоритам за вклучување на компјутерот:

1. Вклучете го напојувањето на компјутерот (притиснете го копчето за вклучување заштитник од пренапони).
2. Вклучете го мониторот и печатачот.
3. Кликнете Копче за напојувањена системска единица.
4. Почекајте да се вчита операционен системи изгледот на работната површина.
5. Фати се на работа.

Во овој алгоритам, сите дејства мора да се вршат последователно едно по друго: не можете да започнете да работите ако напојувањето или мониторот не се вклучени.

Во алгоритамската структура " разгранување» вклучени состојба, во зависност од вистинитоста на состојбата, се извршува една или друга низа наредби (серија).

Услов е изјава која може да биде вистинита или неточна. Во условот, два броја, две низи, две променливи или стрингови изрази се споредуваат едни со други со помош на оператори за споредба (>,<, =, >=, <=).

Снимање на алгоритамски јазик: IfCondition then Series 1 (Ако Состојбавистина, тогаш вистина Епизода 1, Ако Состојбалажно, тогаш ништо не се извршува). Пример: Ако денес е недела, тогаш нема потреба да одите на училиште. Целосна форма на разгранување

Во алгоритамските структури циклус вклучува низа наредби кои се извршуваат постојано. Оваа низа на команди се нарекува тело на јамката.

Постојат два вида циклични алгоритамски структури:

• спротивставени јамки, во која телото на јамката се извршува одреден број пати;
• условни јамки, во која телото на јамката се извршува се додека условот е задоволен.

Јамка со бројач– се користи кога однапред се знае колку повторувања на телото на јамката треба да се изведат.

Алгоритам и неговите својства.

Алгоритам- јасна и прецизна инструкција до изведувачот да ја изврши конечната секвенца на команди што води од почетните податоци до посакуваниот резултат.

Извршувач на алгоритам- ова е објектот или предметот за кој е дизајниран да контролира алгоритмот.

Командниот систем на изведувачот (SCS) е целокупниот сет на команди што изведувачот може да ги изврши.

Својства на алгоритмот: разбирливост, точност, конечност.

Јасност:алгоритмот е составен само од команди вклучени во SKI на извршителот.

Точност:Секоја команда на контролниот алгоритам го одредува недвосмисленото дејство на изведувачот.

Завршување (или изведба):извршувањето на алгоритмот мора да доведе до резултат во конечен број чекори.

Опкружување на изведувачот: средина во која работи изведувачот.

Одреден редослед на дејства на изведувачот секогаш важи за некои изворни податоци. На пример, за да подготвите јадење според кулинарски рецепт, потребни ви се соодветни производи (податоци). За да се реши математичка задача (решавање квадратна равенка), потребни се почетни нумерички податоци (коефициенти на равенки).

Целосен сет на податоци:неопходен и доволен сет на податоци за решавање на задачата (добивање на посакуваниот резултат).

Методи за пишување алгоритми.

Најчестите методи се: графички, вербалнаи во форма компјутерски програми.

Графички методвклучува употреба на одредени графички симболи - блокови.

Име на блокирање	Означување на блок	содржина
Процес		Обработка на податоци
Донесување одлуки		Логичен блок за проверка на вистинитоста или неточноста на одредена состојба
Пренос на податоци		Внесување или излез на информации
Почни, застани		Почеток или крај на програмата
Модификација		Организација на цикличен процес - заглавие на циклусот

Колекцијата на блокови формира т.н дијаграм на тек на алгоритам.

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

При пишување алгоритми во форма програмикомпјутерите користат програмски јазици - системи за кодирање инструкции и правила за нивна употреба. Пишувањето алгоритми во форма на програми се карактеризира со висок степен на формализирање.

Алгоритми за работа со количини. Основни алгоритамски структури.

Количеството е единствен информативен објект кој има име, вредност и тип.

Изведувач на алгоритми за работа со количини може да биде лице или посебен технички уред, како што е компјутер. Таков изведувач мора да има меморијаза складирање на количини.

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

Константна вредност (константна)не ја менува својата вредност за време на извршувањето на алгоритмот. Константа може да се означи со сопствената вредност (броеви 10, 3.5) или со симболично име (број).

Променлива вредностможе да ја промени вредноста за време на извршувањето на алгоритмот. Променлива е секогаш назначена со симболично име (x, a, r5, итн.).

Вид на количинаГо дефинира збирот на вредности што може да ги преземе вредноста и збир на активности што можат да се извршат со таа вредност. Основни видови на количини: Интерес, вистински, симболичен, логичен.

Изразување- запис кој го дефинира редоследот на дејствата на количините. Изразот може да содржи константи, променливи, оперативни знаци и функции. Пример:

А + Б; 2*X-Y; K + L - sin (X)

Команда за доделување е команда на извршител што резултира со променлива да добие нова вредност. Формат на команди:

име на променлива>:=израз>

Командата за доделување се извршува по следниот редослед: прво се пресметува, а потоа добиената вредност се доделува на променлива.

Пример.Нека променливата А има вредност 6. Која вредност ќе ја добие променливата А по извршувањето на наредбата: A:= 2 * A - 1?
Решение.Пресметувајќи го изразот 2*A - 1 со A=6 ќе се добие бројот 11. Тоа значи дека новата вредност на променливата A ќе биде еднаква на 11.

Во продолжение ќе се претпостави дека изведувач на алгоритми за работа со количини е компјутер. Секој алгоритам може да се изгради од команди задачи, внесување, излез, разгранувањеИ циклус.

Команда за внесување- команда со која променливите вредности се поставуваат преку влезните уреди (на пример, тастатура).

Пример: внесувањеА - внесување на вредноста на променливата А од тастатурата на компјутерот.

Излезна команда: Команда што ја прикажува вредноста на количината на излезен уред на компјутер (како монитор).

Пример: заклучок X - на екранот се прикажува вредноста на променливата X.

Команда на гранка- го дели алгоритмот на две патеки во зависност од некоја состојба; тогаш извршувањето на алгоритмот оди на општо продолжение. Разгранувањето може да биде целосно или нецелосно. Опис на разгранување во блок дијаграми и во алгоритамски јазик:

Овде, серија значи една или повеќе секвенцијални команди; kv - крај на разгранување.

Команда за јамкаобезбедува повторено извршување на низа наредби (тело на јамката) врз основа на некој услов.

Јамка со предуслов- јамка чие извршување се повторува додека условот на јамката не биде точен:

Јамка со параметар- повторено извршување на телото на јамката додека параметарот цел број поминува низ множеството на сите вредности од почетната (In) до последната (Ik):

Пример.Дадени се две едноставни фракции. Направете алгоритам за добивање на дропка што е резултат на нивното делење.
Решение.Во алгебарска форма, решението на проблемот изгледа вака:
a/b: c/d = a*d/b*c = m/n
Почетните податоци се четири целобројни величини: a, b, c, d. Резултатот е два цели броеви m и n.

алгделење дропки
недопрена a, b, c, d, m, n
почеток на внесувањеа бе це де
m:=a*d
n:=b*c
излез „Бројувач=", m
излез „Имениител=", n
кои

Забележете дека за да излезе текст (секоја низа знаци), тој мора да биде напишан во наводници во командата заклучок.

1. Ефимова О., Морозов В., Угринович Н. Курс по компјутерска технологија со основите на компјутерската наука. Упатствоза средно училиште. - М.: ДОО „Издавачка куќа АСТ“; ABF, 2000 година
2. Проблемска книга-работилница по информатика. Во 2 тома / Ед. И. Семакина, Е. Хенер. - М.: Лабораторија на основни знаења, 2001 г.
3. Ugrinovich N. Компјутерски науки и информациска технологија. 10-11 одделение - М.: Лабораторија за основни знаења, АД „Московски учебници“, 2001 г.

Задачи и тестови на тема „Алгоритми и извршители“

• Уметнички менаџмент Драфтист - Алгоритми 6-то одделение

  Часови: 4 Задачи: 9 Тестови: 1

• 2 Задачи: 9 Тестови: 1

Почитуван студент!

Познавањето на Темата „Алгоритми и извршители“ е неопходно пред се за понатамошно изучување на програмирањето. Програмскиот јазик QBasic е избран како основа за изучување на програмирање. Ја напуштивме идејата да вклучиме Visual Basic или кој било друг објектно-ориентиран програмски јазик во нашиот курс, бидејќи овој пристап сè уште не е широко користен во повеќето средни училишта во Руската Федерација. Покрај тоа, објектно-ориентираното програмирање се заснова на принципите на класичното програмирање Dos.

Нашиот курс е дизајниран за општообразовна програма. Кога се подготвувате за приемни испити по информатичка технологија на универзитетите, треба да се запознаете со спецификите на студирање програмирање на даден универзитет. Во некои случаи, неопходно е длабинско проучување на голем број теми, на пример, „Низи“. Треба да обрнете внимание на ова кога студирате литература за програмирање; можеби треба да користите методолошки препоракиза подготовка за испити, кои моментално се објавуваат во повеќето високообразовни институции.

Како заклучок, забележуваме дека постигнувањето „аеробатика“ во програмирањето е можно само со постојана пракса и решавање на конкретни применети проблеми.