Що є алгоритм. Алгоритм. Основні засади складання алгоритмів. приклади. Що таке властивості алгоритмів

Перш ніж почати писати супер програми, давайте розберемося, що ж таке програма? Програма – це певний алгоритм, який має виконати ваш комп'ютер.

Ну, а тепер головне питання: Що таке алгоритм?

Властивості алгоритмів

Я не винаходитиму велосипед, а просто перерахую властивості алгоритму, які відомі вже багато років.

1. Кінцевість (результативність)алгоритму означає, що за кінцеве число кроків має бути отриманий результат;
2. Дискретністьалгоритму означає, що алгоритм має бути розбитий на послідовність виконуваних кроків;
3. Зрозумілістьалгоритм означає, що алгоритм повинен містити тільки ті команди, які входять до набору команд, який може виконати конкретний виконавець;
4. Точністьалгоритм означає, що кожна команда повинна розумітися однозначно;
5. Масовістьалгоритм означає, що одного разу складений алгоритм повинен підходити для вирішення подібних завдань з різними вихідними даними.
6. Детермінованість (визначеність). Алгоритм має властивість детермінованості, якщо й тих самих наборів вихідних даних він видавати той самий результат, тобто. результат однозначно визначається вихідними даними.

Таким чином, Алгоритм— це зрозумілий і точний розпорядження виконавцю, виконати кінцеву послідовність кроків, що призводить від вихідних даних до результату.

Уявіть, що я маю з ножем порізати апельсин. Щоб виконати цю дію, мені знадобиться алгоритм.

Я хочу порізати апельсин. Як це зробити?

Види алгоритмів

• Лінійний (Команди послідовні без повторів та переходів);

Приклад алгоритму:

початок
дістань ніж
поріж апельсин (Саме апельсин, а не будь-який інший фрукт. За це відповідає ТОЧНІСТЬ)
з'їж апельсин
кінець

• Циклічний (Є група дій, що повторюються за деякою умовою);

Приклад алгоритму:

початок
дістань ніж
ПОКИ апельсини не закінчилися
ріж апельсин
з'їж усі апельсини
кінець

• Розгалужується(Виконання команди залежить від умови).

Приклад алгоритму:

початок
дістань ніж
ЯКЩО ніж тупий потоки
ріж апельсин
з'їж апельсин
кінець

От і все. На наступному уроці ми з вами розглянемо структуру програми Паскаль.

Підсумкове тестування з інформатики

1. Як називався обчислювальний пристрій, який використовувався у Стародавній Греції?

1. калькулятор
2. машина Паскаля
3. арифмометр
4. логарифмічна лінійка

2. Проект першої програмно-керованої машини було розроблено:

1. Чарльзом Беббіджем
2. Блезом Паскалем
3. Джоном фон Нейманом
4. С.А. Лебедєвим
5. Джоном Непером

3. Для введення програм та даних в ЕОМ першого покоління використовувалися

1. магнітні барабани
2. оптичні диски
3. магнітні диски
4. перфокарти
5. магнітні стрічки

4. Елементною базою першого покоління були

1. транзистори
2. мікропроцесори
3. інтегральні схеми
4. електронні лампи
5. електромеханічне реле

5. Перша ЕОМ називалася …

6. Хто був конструктором перших вітчизняних ЕОМ?

7. Як називався перший серійний персональний комп'ютер?

8. Елементною базою ЕОМ третього покоління були

1. мікропроцесори
2. транзистори
3. інтегральні схеми
4. електронні лампи
5. електромеханічне реле

9. Що таке інформатизація?

1. програмне забезпечення комп'ютера
2. технологія підготовки документів
3. сукупність способів та прийомів зберігання, передачі та обробки інформації
4. процес створення, розвитку та масового застосування інформаційних засобів та технологій
5. система управління базами даних

10. Інформаційним суспільствомназивають:

1. систему національних, громадських установ
2. користувачів мережі Інтернет
3. мережу, яка зв'язує між собою безліч локальних мереж, а також окремі комп'ютери
4. стадію розвитку суспільства, де основним предметом праці людей стає інформація
5. суспільство, що характеризується високим ступенемвідкритості, доступності інформації про діяльність установ, організацій, посадових осібі т.п. для громадського ознайомлення, обговорення

11. Що з перерахованого НЕ відноситься до цілей інформатизації?

1. інформаційне забезпечення активного відпочинку та дозвілля людей
2. формування та розвиток інформаційних потреб людей
3. формування умов, які забезпечують здійснення інформатизації
4. інформаційне забезпечення всіх видів діяльності
5. переведення всіх інформаційних ресурсів у цифровий формат

12. До національних інформаційних ресурсів належать

1. медичні заклади
2. фонди бібліотек та архівів
3. університети, інститути, академії
4. газ, нафта
5. громадські організації

13. До заходів забезпечення інформаційної безпеки НЕ належить

1. технічні заходи щодо захисту від комп'ютерних злочинів
2. юридичні заходи щодо захисту від комп'ютерних злочинів
3. розробка технологій створення захищених автоматизованих систем обробки інформації
4. дотримання правил техніки безпеки під час роботи з комп'ютером
5. адміністративні заходи щодо захисту від комп'ютерних злочинів

14. По лінії прямого зв'язку передаються

1. команди управління та інформація про об'єкт управління
2. інформація про стан об'єкта управління
3. інформація про стан керуючої системи
4. команди управління
5. команди управління та інформація про керуючу систему

15. Який із об'єктів може бути виконавцем алгоритмів?

16. Алгоритми, які вирішують деяке підзавдання головного завдання і, як правило, виконуються багаторазово, називаються:

1. циклічними
2. допоміжними
3. лінійними
4. основними
5. розгалуженими

Читайте також: Як закрити борги за кредитами

17. Алгоритм називається лінійним:

1. якщо хід його виконання залежить від істинності тих чи інших умов
2. якщо його виконання передбачає багаторазове повторення тих самих операцій
3. якщо операції виконуються в порядку їх природного слідування одна за одною незалежно від будь-яких умов
4. якщо він представимо у табличній формі
5. якщо операції виконуються від поч до кон

18. Зрозумілість алгоритму означає, що він має бути записаний за допомогою:

1. команд, зрозумілих творцю алгоритму
2. команд із системи команд виконавця
3. команд, зрозумілих користувачеві алгоритму
4. команд, зрозумілих для комп'ютера
5. операторів мови програмування

19. Кінцевість алгоритму означає, що:

1. в ньому повинен бути оператор виведення результату
2. він повинен вирішувати завдання обчислювального характеру
3. у ньому має бути присутнім ключове слово, що означає кінець алгоритму
4. він повинен бути застосовним для вирішення всіх завдань заданого типу
5. результат має бути отриманий за кінцеве число кроків

20. Як називається властивість алгоритму, що відповідає визначенню: «Алгоритм має бути записаний із команд, зрозумілих виконавцю, кожна команда повинна визначати однозначну дію виконавця»?

1. масовість
2. точність
3. кінцівка
4. зрозумілість
5. дискретність

21. Алгоритм - це

1. кінцевий набір розпоряджень, що визначає розв'язання задачі за допомогою кінцевої кількості операцій
2. правила виконання певних дій
3. набір команд для комп'ютера
4. протокол обчислювальної мережі
5. припис виконавцю вчинити послідовність дій

22. До клітини електронної таблиці можна занести.

1. тільки формулу
2. тільки число чи текст
3. тільки число
4. число, формулу чи текст
5. діаграму

23. Діапазон клітин електронної таблиці - це

1. безліч клітин, що утворюють область довільної форми
2. безліч заповнених клітин ЕТ
3. безліч порожніх клітин ЕТ
4. безліч клітин, що утворюють область прямокутної форми
5. безліч клітин, що утворюють область квадратної форми

24. Скільки клітин входить у діапазон клітин A5: D8?

25. Клітина ЕТ називається поточною, якщо

1. клітка видно на екрані
2. в ній знаходиться інформація
3. клітина порожня
4. клітина містить формулу
5. в ній знаходиться курсор

26. Адреса клітини електронної таблиці - це

1. ім'я, що складається із послідовності символів
2. ім'я, що складається з імені стовпця та номера рядка
3. адреса байта оперативної пам'яті, відведеного під клітину
4. адреса машинного слова оперативної пам'яті, відведеного під клітинку
5. номер байта оперативної пам'яті, відведеної під клітинку

27. Чому дорівнює сума двійкових чисел 110110 та 101?

28. Неправильне твердження:

1. запис включає кілька полів
2. поле включає кілька записів
3. кожне поле БД має власний розмір
4. БД має жорстку структуру
5. кожне поле має ім'я

29. Структура БД зміниться, якщо

1. додати/видалити поле
2. редагувати запис
3. поміняти місцями записи
4. Додати запис
5. видалити запис

30. У реляційній БД інформація організована у вигляді

1. ієрархічної структури
2. файлу
3. дерева
4. прямокутної таблиці

31. Що унеможливлює підключення комп'ютера до глобальної мережі:

1. Тип комп'ютера
2. Склад периферійних пристроїв
3. Відсутність дисководу
4. Відсутність мережної карти

32. У комп'ютерних мережах зазвичай використовуються канали зв'язку:

1. Провід
2. Кабелі
3. Радіо зв'язок
4. Все вищезазначене

33. Ефективність комп'ютерного зв'язку залежить від:

1. Пропускної спроможності
2. Продуктивності процесора
3. Ємності пам'яті
4. Все вищезазначене

34. Пристрій, що робить перетворення аналогових сигналів в цифрові та назад, називається:

35. Об'єднання комп'ютерів та локальних мереж, розташованих на віддаленій відстані, для загального використання світових інформаційних ресурсів, називається.

1. локальна мережа
2. глобальна мережа
3. корпоративна мережа
4. регіональна мережа

36. У локальних мережахвикористовуються:

1. Провід та кабелі
2. Лінії телефонного зв'язку
3. Електронні лампи
4. Кристал

37. Всесвітня павутина - це система в глобальній мережі, яка зветься:

38. Протоколи – це …

1. спеціалізовані засоби, що дозволяють у реальному часі організувати спілкування користувачів каналами комп'ютерного зв'язку
2. сукупністю правил, що регулюють порядок обміну даними у мережі
3. система передачі електронної інформації, що дозволяє кожному користувачеві мережі отримати доступ до програм та документів, що зберігаються на віддаленому комп'ютері

39. Браузер – це …

1. інформаційна система, основними компонентами якої є гіпертекстові документи
2. програма для перегляду Web-сторінок
3. сервіс Інтернету, що дозволяє обмінюватися між комп'ютерами через мережу електронними повідомленнями

40. Адреса електронної поштизаписується за певним правилам. Заберіть зайве

1. petrov_yandex.ru
2. [email protected]
3. [email protected]

Підсумкове тестування з інформатики на тему «Управління та алгоритми» (9 клас)

Що таке Кібернетика?

розділ інформатики, що має на меті розробку інтелектуальних систем; наука, що займається вивченням способів передачі, зберігання та обробки інформації за допомогою комп'ютера;

наука про управління в живих та неживих системах;

наука про форми, методи та закони інтелектуальної пізнавальної діяльності, що формалізуються за допомогою логічної мови;

наука про життя, одна з природничих наук, предметом якої є живі істоти та їх взаємодія з довкіллям.

Читайте також: Заява приставам про припинення виконавчого провадження

Хто заснував Кібернетику?

угорсько-німецький математик Джон фон Нейман;

грецький філософ Платон;

французький фізик Андре Ампер;

російський вчений Владислав Закревський;

американський математик Норберт Вінер.

З яких елементів з погляду кібернетики складається будь-яка система управління?

канал зворотного зв'язку;

16+ Свідоцтво про реєстрацію ЗМІ:
Ел №ФС77-60625 від 20.01.2015.

Ліцензія на здійснення освітньої діяльності: №5201 від 20.05.2016.

Адреса редакції та видавництва: 214011, РФ,
м. Смоленськ, вул. Верхньо-Сінна, 4.
Контакти: [email protected]

Правовласник товарного знаку ІНФОУРОК: ТОВ «Інфоурок» (Свідоцтво № 581999)

Всі матеріали, розміщені на сайті, створені авторами сайту або розміщені користувачами сайту та представлені на сайті виключно для ознайомлення. Авторські права на матеріали належать їхнім законним авторам. Часткове чи повне копіювання матеріалів сайту без письмового дозволу адміністрації сайту заборонено! Думка редакції може не співпадати з точкою зору авторів.

Відповідальність за вирішення будь-яких спірних моментів, що стосуються самих матеріалів та їх змісту, беруть він користувачі, які розмістили матеріал на сайті. Однак редакція сайту готова надати всіляку підтримку у вирішенні будь-яких питань, пов'язаних із роботою та змістом сайту. Якщо Ви помітили, що на цьому сайті незаконно використовуються матеріали, повідомте про це адміністрацію сайту через форму зворотнього зв'язку.

1. Як називається властивість алгоритму, 1. Як називається властивість алгоритму, що означає, що даний алгоритм застосовується до розв'язання цілого класу задач?
а) зрозумілість
б) певність
в) результативність
г) масовість
2. Як називається властивість алгоритму, що означає, що він завжди призводить до результату через кінцеве, можливо дуже велике числокроків?
а) дискретність
б) зрозумілість
в) результативність
г) масовість
3. Як називається властивість алгоритму, що означає, що він заданий за допомогою таких розпоряджень, які виконавець може сприймати і якими може виконувати необхідні дії?
а) дискретність
б) зрозумілість
в) визначеність
г) масовість
4. Як називається властивість алгоритму, що означає, що нехай розв'язання задачі поділено на окремі кроки?
а) дискретність
б) певність
в) результативність
г) масовість
5. Як називається властивість алгоритму, що означає, що шлях розв'язання задачі визначений цілком однозначно, на будь-якому кроці не допускаються жодні двозначні та недомовки?
а) дискретність
б) зрозумілість
в) визначеність
г) результативність

Перевірені відповіді містять інформацію, яка заслуговує на довіру. На «Знаннях» ви знайдете мільйони рішень, відзначених самими користувачами як найкращі, але лише перевірка відповіді нашими експертами дає гарантію її правильності.

Відповімо на запитання на тему «Властивості алгоритму»:

Перш ніж відповісти на питання тесту, пригадаємо властивості алгоритму:

1. Зрозумілість- Зміст команд, зрозумілих виконавцю;
2. Визначеність— результат однозначно визначається вихідними даними, кожен крок алгоритму чітко визначено.
3. Результативність- Отримання результату через кінцеве число кроків.
4. Масовість— певний алгоритм може застосовуватися на вирішення подібних завдань.
5. Дискретність- Поділ алгоритму на послідовні дії (кроки).
6. Точність- всі команди повинні чітко (однозначно) розумітися.

Питання №1
Як називається властивість алгоритму, що означає, що даний алгоритм застосовується до вирішенню цілого класу завдань ?
а) зрозумілість;
б) певність;
в) результативність;
г) масовість- певний алгоритм може застосовуватися для вирішення цілого класу подібних завдань .
ВІДПОВІДЬ: Г) МАСОВІСТЬ

Питання №2
Як називається властивість алгоритму, що означає, що він завжди призводить до результату через кінцеве. можливо, дуже велике кількість кроків ?
а) дискретність;
б) зрозумілість;
в) результативність - отримання результату через кінцева кількість кроків ;
г) масовість.
ВІДПОВІДЬ: В) РЕЗУЛЬТАТИВНІСТЬ .

Питання №3
Як називається властивість алгоритму, що означає, що він заданий за допомогою таких розпоряджень, які виконавець може сприйматиі за якими може виконувати необхідні дії ?
а) дискретність;
б) зрозумілість- Зміст команд, зрозумілих виконавцю ;
в) певність;
г) масовість.
ВІДПОВІДЬ: Б) Зрозумілість.

Питання №4
Як називається властивість алгоритму, що означає, що п уть розв'язання задачі поділено на окремі кроки ?
а) дискретність - поділуалгоритму на послідовнідії (Кроки);
б) певність;
в) результативність
г) масовість
ВІДПОВІДЬ: А) ДИСКРЕТНІСТЬ

Питання №5
Як називається властивість алгоритму, що означає, що шлях вирішеннязавдання визначеноцілком однозначно. на будь-якому кроці не допускаються жодні двозначні та недомовки?
а) дискретність;
б) зрозумілість;
в) визначеність— результат однозначно визначається вихідними даними, кожен крок алгоритму чітко визначений;
г) результативність.
ВІДПОВІДЬ: В) ВИЗНАЧЕННІСТЬ.

Безкоштовна допомога з домашніми завданнями

Введення у поняття алгоритму

Поняття алгоритму

У сьогоднішньому соціумі слово «алгоритм» настільки поширене, що більшості інтуїтивно зрозуміло. Під ним ми розуміємо якусь послідовність кроків для досягнення тієї чи іншої мети. Однак для теоретичної науки поняття «алгоритму» досить складне.

Практично все у світі підпорядковується якимось законам і правилам. Сучасна наукане стоїть на місці, завдяки чому людству відома маса формул і алгоритмів, за якими можна розрахувати і відтворити безліч дій і будов, створених природою, і втілити в життя ідеї, придумані людиною.

У статті ми розберемо основні поняття алгоритму.

Історія появи алгоритмів

Алгоритм - поняття, що з'явилися у XII столітті. Саме слово "алгоритм" походить від латинської інтерпретації імені відомого математика середнього сходу Мухаммеда аль Хорезмі, який написав книгу "Про індійський рахунок". У цій книзі описано, як правильно записувати натуральні числа, використовуючи арабські цифри, та наведено опис алгоритму дій стовпчиком над такими числами.

У XII столітті книга "Про індійський рахунок" була перекладена латинською мовою, тоді-то і з'явилося дане визначення.

Взаємодія алгоритму з людиною та машиною

Створення алгоритму вимагає творчого підходу, тому новий список послідовних дій може створити лише жива істота. А ось для виконання вже існуючих інструкцій фантазію мати не обов'язково, з цим упорається навіть бездушна техніка.

Відмінним прикладом точного виконання заданої інструкції є порожня мікрохвильова піч, яка продовжує працювати, незважаючи на відсутність їжі в ній.

Суб'єкт чи об'єкт, якому необов'язково вникати у суть алгоритму, називається формальним виконавцем. Людина також може стати формальним виконавцем, проте у разі нерентабельності тієї чи іншої дії мислячий виконавець може все зробити по-своєму. Тому основними виконавцями є комп'ютери, мікрохвильові печі, телефони та інша техніка. Поняття алгоритму в інформатиці має найважливіше значення. Кожен алгоритм складається з розрахунку конкретного суб'єкта, з урахуванням допустимих действий. Ті об'єкти яких суб'єкт може застосувати інструкції, становлять середу виконавця.

Практично все у світі підпорядковується якимось законам і правилам. Сучасна наука не стоїть на місці, завдяки чому людству відома маса формул і алгоритмів, за якими можна розрахувати і відтворити безліч дій і творінь природи і втілити в життя ідеї, придумані людиною. У статті ми розберемо основні поняття алгоритму.

Що таке алгоритм?

Більшість дій, які ми виконуємо протягом свого життя, потребують дотримання низки правил. Від того, наскільки вірне уявлення має людина про те, як і в якій послідовності вона повинна зробити, залежить якість і результат виконання поставлених перед ним завдань. З дитинства батьки намагаються виробити у своєму чаді алгоритм основних дій, наприклад: прокинутися, заправити постіль, вмитися і почистити зуби, зробити зарядку, поснідати і т. д., список, який людина все життя виконує з ранку, теж можна вважати своєрідним алгоритмом.

Який із способів буде використаний, залежить від кількох факторів: від складності задачі, від того, наскільки необхідно деталізувати процес розв'язання задачі тощо.

Графічний варіант побудови алгоритму

Графічний алгоритм - поняття, що мають на увазі під собою розкладання дій, які потрібно виконати для вирішення певного завдання, за певними геометричними фігурами.

Зображуються не абияк. Для того щоб їх могла зрозуміти будь-яка людина, застосовуються найчастіше блок-схеми і структурограми Нассі-Шнейдермана.

Також блок-схеми зображуються відповідно до ГОСТ-19701-90 та ГОСТ-19.003-80.
Графічні фігури, що застосовуються в алгоритмі, поділяються на:

Основні.Основні зображення застосовуються для позначення операцій, необхідні обробки даних під час вирішення завдання.

Допоміжні.Допоміжні зображення потрібні для позначення окремих, не найважливіших елементів вирішення задачі.

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

Всі блоки йдуть у послідовності "згори донизу" і "зліва направо" - це правильний напрямок потоку. При правильній послідовності лінії, що з'єднують між собою блоки, не показують напрямок. В інших випадках напрямок ліній позначається за допомогою стрілок.

У правильної схеми алгоритму не повинно бути більше одного виходу з обробних блоків і менше двох виходів з блоків, що відповідають за перевірку виконання умов.

Як правильно побудувати алгоритм?

Структура алгоритму, як було сказано вище, повинна будуватися за ГОСТом, інакше вона не буде зрозуміла і доступна оточуючим.

Загальна методика запису включає наступні пункти:

Назва, яким буде зрозуміло, яке завдання можна вирішити з допомогою цієї схеми.

У кожного алгоритму мають бути чітко позначені початок та кінець.

У алгоритмів мають бути чітко та ясно описані всі дані, як вхідні, так і вихідні.

При складанні алгоритму слід зазначити дії, які дозволять виконувати необхідні завдання завдання над вибраними даними. Зразковий вид алгоритму:

• Назва схеми.
• Дані.
• Початок.
• Команди.
• Кінець.

Правильне побудова схеми значно полегшить обчислення алгоритмів.

Геометричні фігури, що відповідають за різні дії в алгоритмі

Горизонтально розташований овал – початок та кінець (знак завершення).

Горизонтально розташований прямокутник – обчислення чи інші дії (знак процесу).

Горизонтально розташований паралелограм - введення або виведення (знак даних).

Горизонтально розташований ромб – перевірка умови (знак рішення).

Витягнутий, горизонтально розташований шестикутник – модифікація (знак підготовки).

Моделі алгоритмів представлені нижче малюнку.

Формульно-словесний варіант побудови алгоритму.

Формульно-словенні алгоритми записуються в довільній формі, професійною мовоютієї галузі, до якої належить завдання. Опис дій у такий спосіб здійснюють за допомогою слів та формул.

Поняття алгоритму інформатики

У комп'ютерній сфері все ґрунтується на алгоритмах. Без чітких вказівок, введених у вигляді спеціального коду, не працюватиме жодна техніка чи програма. На уроках інформатики учням намагаються дати основні поняття алгоритмів, навчити користуватися ними та самостійно їх створювати.

Створення та використання алгоритмів в інформатиці - процес творчіший, ніж, наприклад, виконання вказівок до вирішення задачі в математиці.

Існує також спеціальна програма «Алгоритм», яка допомагає людям, необізнаним з програмування, створювати свої власні програми. Такий ресурс зможе стати незамінним помічником для тих, хто робить перші кроки в інформатиці та хоче створювати свої ігри чи будь-які інші програми.

З іншого боку, будь-яка програма – алгоритм. Але якщо алгоритм несе лише дії, які потрібно виконувати, вставляючи свої дані, то програма вже несе в собі готові дані. Ще одна відмінність - це те, що програма може бути запатентована і бути приватною власністю, а алгоритм ні. Алгоритм - поняття більш широке, ніж програма.

Висновок

У цій статті ми розібрали поняття алгоритму та його види, довідалися, як правильно записувати графічні схеми.

Зрозумілість - алгоритм повинен складатися з команд, "зрозумілих" виконавцю (що входять до системи команд виконавця).

Дискретність (перервність, роздільність) - алгоритм повинен представляти процес вирішення задачі як послідовне виконання простих (або раніше визначених) кроків.

Визначеність - тобто. кожне правило алгорита повинна бути чітким, однозначним і не залишати місця для свавілля. Завдяки цій властивості виконання алгоритму носить формальний характер і не вимагає ніяких додаткових вказівок або відомостей про вирішувану задачу.

Результативність (або кінцівка)- алгоритм повинен призводити до вирішення завдання (або відповіді, що рішення немає) за кінцеве число кроків.

Масовість - Алгоритм вирішення завдання розробляється в загальному вигляді, тобто. він повинен бути застосований для деякого класу завдань, що відрізняються лише вихідними даними. При цьому вихідні дані можуть вибиратися з деякої області, яка називається областю прийнятності алгоритму.

Головна особливість будь-якого алгоритму - формальне виконання, що дозволяє виконувати задані дії (команди) як людині, а й технічним пристроям (виконавцям). Таким чином, виконавцями алгоритмів можуть бути, наприклад, людина, комп'ютер, принтер, робот-маніпулятор, верстат з числовим програмним керуванням, жива клітка, дресирована тварина, комп'ютерна програма, комп'ютерний вірус, "черепашка" у Логорайтері чи Логомирах (геометричний виконавець) тощо.

Виконавець алгоритму - пристрій управління, з'єднане з набором інструментів. Пристрій управління розуміє алгоритми та організує їх виконання, командуючи відповідними інструментами. А інструменти роблять дії, виконуючи команди пристрою, що управляє. Перш ніж складати алгоритм розв'язання задачі, треба дізнатися, які дії передбачуваний виконавець може виконати.

Ці дії називаються допустимими діями виконавця. Тільки їх можна використовувати.

Виконавець обчислювальних алгоритмів називається обчислювачем. Обчислювач може мати справу з числами та змінними, що позначають числа. Отже, алгоритм - це організована послідовність дій, допустимих деякого виконавця. Один і той самий виконавець може бути симітований на ЕОМ багатьма способами.

Складність алгоритму

Складність алгоритму дозволяє оцінити, наскільки швидко зростає трудомісткість алгоритму зі збільшенням обсягу вхідних даних. Під трудомісткістю розуміється кількість елементарних операцій, які потрібно виконати на вирішення завдання з допомогою даного алгоритму. Зазвичай оцінка складності алгоритму представляється як O(f(N)), де O – функція складності, а N – число оброблюваних спостережень чи прикладів. Найменш витратними є алгоритми, котрим функція складності має вигляд f(N)=C і f(N)=C*N, де С – константа. У першому випадку обчислювальні витрати залежить від кількості оброблюваних даних, тоді як у другому випадку – лінійно зростають. Найбільш витратними є алгоритми, складність яких має статечну і факторіальну залежність від кількості спостережень, що обробляються.

СОРТУВАННЯ

Сортування є процес упорядкування безлічі подібних інформаційних об'єктів у порядку зростання або зменшення їх значень. Наприклад, список i з n елементів буде відсортовано у порядку зростання значень елементів, якщо i<= i <= ... <= i.

Є два види алгоритмів сортування: сортування масивів, які можуть бути як в операційній пам'яті, так і на диску у вигляді файлу прямого доступу, і сортування послідовних файлів, що знаходяться на дисках або магнітних стрічках.

Основна відмінність між сортуванням масивів та сортуванням послідовних файлів полягає в тому, що кожен елемент масиву є доступним у будь-який час. Це означає, що будь-який час будь-який елемент масиву може порівнюватися з будь-яким іншим елементом масиву і будь-які два елементи масиву можуть обмінюватися місцями. Навпаки, у послідовному файлі кожен момент часу доступний лише одне елемент. Через ці відмінності методи сортування суттєво відрізняються для цих двох видів сортування.

У загальному випадку при сортуванні даних тільки частина інформації використовується як ключ сортування, який використовується в порівняннях. Коли здійснюється обмін, передається вся структура даних.

МЕТОДИ ПОШУКУ

Пошук інформації у невідсортованому масиві потребує проведення послідовного перегляду масиву. Перегляд починається з першого елемента і завершується знайденим елементом, або досягненням кінця масиву. Цей метод слід використовувати для невідсортованих даних, але він також може використовуватися для відсортованих даних. Якщо дані відсортовані, може використовуватися двійковий пошук, який виконується значно швидше.

алгор і ф м) – одне з основних понять логіки та математики. Під А. розуміють точне припис, що задає обчислити. процес, що веде від початкових даних, які можуть варіювати, до шуканого результату. Слова "обчислення", що зустрічаються вище, "обчислювальний" не слід розуміти у вузькому сенсі цифрових обчислень. Так, вже у шкільному курсі алгебри говорять про літерні обчислення, і хоча тут літери відіграють ще роль заступників чисел, вже в арифметич. обчислення з'являються символи, що не позначають жодних величин: дужки, знак рівності, знаки арифметич. дій. Можна піти далі і розглядати обчислення з довільними символами та їх комбінаціями; саме в такому широкому значенні і розуміють термін "обчислення" в описі поняття "А.". Так, можна говорити про А. перекладу з однієї мови на іншу, про А. роботи поїзного диспетчера (переробного інформацію про рух поїздів до наказів) та ін прикладах алгоритміч. опис процесів управління, що вивчаються кібернетикою. З н а ч е н ня А. Саме слово "А." перегукується з 9 в. (Воно походить від Algoritmi, що є, у свою чергу, лат. транслітерацією, виробленої, мабуть, в 12 ст., Арабського імені хорезмійського математика аль-Хорезмі). У наші дні найпростіші А. з'являються вже в початковій школі - А. Арифметич. дій (у СР-вік. Європі А. якраз і називалася совр. шкільна арифметика, тобто десяткова позиційна система числення і мистецтво рахунку в ній, оскільки трактат аль-Хорезмі був одним з перших, якщо не найпершим, завдяки до-рому Європа познайомилася з позиційною системою). Підкреслимо, що у початковій школі навчають саме А. рахунки. Говорячи про вміння людини складати числа, мають на увазі не те, що він для будь-яких двох чисел рано чи пізно зуміє знайти їхню суму, а те, що він володіє деяким одноманітним прийомом додавання, застосовним до будь-яких двох конкретних записів чисел, т.е. е., іншими словами, А. додавання (прикладом такого А. є відомий А. додавання чисел "стовпчиком"). А. зустрічаються в науці на кожному кроці, вміння вирішувати завдання "в загальному вигляді" завжди означає, по суті, володіння деяким А. Поняття задачі "в загальному вигляді" уточнюється за допомогою поняття масової проблеми. Під терміном "проблема" можна розуміти завдання знаходження об'єкта, що має ті чи інші властивості; цей об'єкт зв. вирішенням проблеми (зокрема, для проблеми знаходження відповіді на якесь питання рішенням є відповідь "так" чи "ні" на поставлене питання). Проблема нерозв'язна, якщо вона має рішення, тобто. немає об'єкта, що має необхідні властивості. Зрозуміло тому, що нерозв'язність проблеми не дає підстав для агностич. висновків; навпаки, встановлення нерозв'язності конкретної проблеми є важливим пізнавати. акт. Масова проблема задається серією окремих, "поодиноких" проблем і полягає у вимогі знайти загальний метод (тобто А.) їх вирішення. Нерозв'язність масової проблеми означає неможливість знайти відповідності. А. Масові проблеми надзвичайно характерні та важливі для логіки та математики. Навіть вирішення поодиноких проблем часто цінне саме завдяки тому, що одночасно дає загальний метод для вирішення цілого класу проблем; в той же час постановка масової проблеми означає перетворення деякого класу проблем на одиничну проблему - проблему знаходження А. для вирішення всіх проблем цього класу; тут проявляється зв'язок таких категорій діалектики, як одиничне, особливе та загальне. Ролью масових проблем і визначається значення А. Встановлення нерозв'язності тієї чи іншої масової проблеми (тобто. відсутності єдиного алгоритму, що дозволяє знайти рішення всіх одиничних проблем даної серії) є найважливішим пізнавальним актом, що показує, що на вирішення конкретних одиничних проблем принципово необхідні специфічні кожної такої проблеми методи. Існування нерозв'язних масових проблем служить, тобто конкретним втіленням невичерпності процесу пізнання. Містять. явища, які лягли в основу освіти поняття "А.", здавна займали важливе місце в науці. Багато завдань, що виникали в математиці та логіці, полягали у пошуках тих чи інших конструктивних методів. Пошуки таких методів, що особливо посилилися у зв'язку зі створенням зручної математич. та логіч. символіки, і навіть осмислення важливої ​​відсутності цих методів часом – усе це було сильним чинником розвитку наук. знання. Усвідомлення неможливості вирішити будь-яке завдання прямим обчисленням призвело до створення 19 в. теоретико-множин. концепції. Лише після періоду бурхливого розвитку цієї концепції (в рамках якої питання про конструктивні методи в совр. їх розумінні взагалі не виникає) виявилося можливим в останні десятиліття знову повернутися до питань конструктивності, але вже на новому рівні, збагаченому поняттям "А., що викристалізувався". (ще одна ілюстрація до становища Леніна про спіралеподібний характер розвитку пізнання). І хоча поняття "А." не є настільки далекосяжною абстракцією, як, скажімо, поняття "множина", не можна вважати випадковим, що історично перше з цих понять виникло пізніше за друге. П р і м е р ы А. Подібно до понять "множина", "відповідність", "натуральне число", "ставлення" і т.п., поняття "А." є первинним логіко-математич. поняттям (однієї з категорій логіки та математики). Воно не допускає формального визначення через простіші поняття, а (як і ін. математич. категорії) абстрагується безпосередньо з досвіду. Поняття "А." може бути засвоєно лише з прикладах. П р і м е р 1. Можливими початковими даними кінцеві непусті комбінації, складені з паличок (I), тобто. об'єкти I, II, III тощо. А. складається із слід. правил (виконувати які належить починаючи з правила 1 °): 1 °. Підкресли знизу крайню ліву паличку і перейди до виконання правила 2°. 2 °. Надкресли зверху крайню праворуч паличку та перейди до виконання правила 3°. 3 °. Розглянь підкреслену паличку і, якщо вона не накреслена, перейди до виконання правила 4°. 4 °. Розглянь паличку безпосередньо наступну за підкресленою; якщо вона не накреслена, перейди до виконання правила 5°; якщо вона підкреслена, перейди до виконання правила 7°. 5 °. Перенеси нижню рису з підкресленої палички на безпосередньо за нею наступну і перейди до виконання правила 6°. 6 °. Перенеси верхню рису з надкресленої палички на безпосередньо їй попередню і перейди до виконання правила 7°. 7 °. Зітріть надкреслену паличку і всі наступні за нею палички і перейди до виконання правила 8°. 8 °. Зітріть нижню рисочку у підкресленої палички; те, що вийшло, є результат. Застосовуючи цей А. до комбінації ||||, взятої як початковий даний, отримаємо послідовно: за правилом 1° – |||, за правилом 2° – ? || , за правилами 3 °, 4 °, 5 ° - | ? | , за правилами 6 °, 3 °, 4 ° - | ? | за правилом 7 ° - | ?, за правилом 8 ° - | | (Результат). Якщо спробувати застосувати А. до комбінації |||, то отримаємо: за правилом 1° – ? ||, за правилом 2 ° -? | , за правилами 3 °, 4 °, 5 ° - | ? , за правилом 6 ° - | I |, далі необхідно перейти до виконання правила 3°, але правило 3° можна здійснити лише за умови, що підкреслена паличка не надкреслена. Т.ч., для ситуації А. не містить вказівок, як чинити далі; сталася т.зв. безрезультатна зупинка (зупинка, що не супроводжується одержанням результату). Легко зауважити, що взагалі сформулювали. А. дає результат при застосуванні його до будь-якої комбінації з парного числа паличок, і результатом у цьому випадку є комбінація, що складається з половини паличок; А. не дає результату до будь-якої комбінації, що складається з непарного числа паличок. Приклад 2. У логіці та математиці всякий кінцевий набір знаків зв. "алфавітом", знаки, що входять до нього, - "літерами" алфавіту, а кінцева (в т.ч. порожня) послідовність написаних один за одним букв к.-л. алфавіту зв. "словом" у цьому алфавіті. Арабські цифри утворюють алфавіт, а кожен десятковий запис цілого числа є словом у цьому алфавіті. Розглянемо алфавіт (а, в) із двох літер: а та в. Прикладами слів у цьому алфавіті є: в, ав, вва ааававв тощо. Умовимося називати "допустимим" перехід від слова в цьому алфавіті до ін. Слова в цьому ж алфавіті згідно з одним із слід. двох правил: 1) якщо слово має вигляд аР, де P – довільне слово, перейти до слова Рв; 2) якщо слово має вигляд ва?, де? - Довільне слово, перейти до слова Рава. Далі формулюється слід, припис: "виходячи з к.-л. слова (взятого як початкові дані), роби допустимі переходи до тих пір, поки не вийде слово виду аа?; коли слово такого виду вийде, відкинь перші дві літери, а те, що залишиться, і є результатом”. Оскільки щоразу можна здійснити не більше одного правила переходу, то сформулюють. припис утворює А., можливими початковими даними якого служать слова в алфавіті (а, в). Візьмемо як початкові дані слово ваваа. Відповідно до правила 2 отримаємо вааава. Знову застосовуючи правило 2, отримаємо ааваава. В силу нашого розпорядження треба зупинитися; результатом (застосування А. до слова ваваа) є ваава. Візьмемо як початкові дані слово ваава. За правилом 2 отримаємо аваава. За правилом 1 отримаємо ваавав. Далі отримаємо послідовно ававава, вававав, вававава тощо. Можна довести, що процес ніколи не закінчиться (тобто ніколи не виникає слово, що починається з двох букв а, і для кожного з слів можна буде здійснити допустимий перехід). Т.ч., А. не дає результату при застосуванні до слова ваава. Візьмемо як початкові дані слово ваав. Послідовно отримаємо ваавв, аввава, ввававши. Далі жодне з правил 1 і 2 не можна здійснити, і в той же час результат не вийшов. Тому у застосуванні до слова аваав А. також не дає результатів. Основні риси А. За твердженням А. А. Маркова, для А. характерні такі осн. риси: а) про розподілення алгоритмич. приписи, що полягає в його не залишає місця свавілля точності і загальнозрозумілості (через цю визначеність приписи алгоритміч. процес є детермінарним: кожна стадія процесу однозначно визначає наступну стадію); б) маса с о в с т ь, що полягає в можливості для кожного А. виходити з початкових даних, що варіюються у відомих межах; в) результативність, яка полягає у спрямованості його на отримання шуканого результату. Детермінованість А. забезпечує можливість повідомлення його однією особою іншій особі з тим, що ця інша особа зможе виконувати А. без участі першої; це ж властивість детермінованості уможливлює передачу виконання А. машині. Масовість А. припускає, що існує деяка сукупність (для кожного А. своя) можливих початкових даних. Як задається ця сукупність, – це вже інше питання. Можна вважати, що відповідна якомусь А. сукупність можливих початкових даних не визначається окремо від А., а вказується природ. чином самим змістом цього А. (так, для А. додавання стовпчиком відповідна сукупність складається з усіх пар записів чисел у десятковій системі). Коли якийсь конкретний об'єкт вибирається як початкові дані А., то говорять про приклад і А. до цього об'єкта. Якщо А. дає результат при застосуванні його до деякого об'єкта, то кажуть, що він приклад до цього об'єкта. Результативність А. зовсім не означає, що А. має бути застосовним до будь-якого об'єкта з відповідної сукупності можливих початкових даних (див. Приклади1 і 2). Тут доречно відзначити, що можна побудувати такий А., для якого не існує ніякого А., який розпізнавав би за довільними початковими даними першого А., застосуємо до них перший А. чи ні. Основні абстракції теорії А. У нав. практиці склалася низка специфічних. для математики та логіки абстракцій. Такі насамперед абстракція актуальної нескінченності, абстракція ототожнення, абстракція потенційної здійсненності. Рад. Вчений А. А. Марков показав, що дві останні необхідні під час розгляду А. Алгоритміч. процес розчленовується на отд. кроки, кожен з яких брало передбачається настільки елементарним, що можливість його фактич. здійснення не викликає сумнівів. Разом з тим кількість цих елементарних кроків, потрібна для отримання результату, може бути настільки великою, що досягнення результату може вважатися практично неможливим. Однак уявлення про практич. здійсненності чи нездійсненності тієї чи іншої кількості кроків є відносним. Воно змінюється із розвитком обчислить. коштів (у принципі може змінюватися й уявлення про елементарність отд. кроку). Теоретично А. тому відволікаються від " практич. здійсненності " і вважають здійсненним будь-яке кінцеве число кроків. Тим самим щодо А. допускають абстракцію потенційної здійсненності, яка полягає у відверненні реальних меж наших можливостей. Розвиток швидкодіючих електронних обчислить. машин швидко відсуває ці межі дедалі далі. Те, що було лише потенційно здійсненним учора, стає практично здійсненним сьогодні. Це зближує теорію А. з практикою роботи на обчислити. машин і дозволяє цим двом дисциплінам взаємно збагачувати один одного. Передача машині розв'язання задач к.-л. серії неможлива без попередньо. складання А. рішення. Упорядкування такого А. має, як правило, принципове значення (так, у проблемі машинного перекладу основним є саме складання А. перекладу). Абстракція потенційної здійсненності необхідна під час розгляду як алгоритмич. процесів, а й самих об'єктів, що у цих процесах (зокрема " початкових даних " і " результатів " ). Так, щоб говорити про будь-яке натуральне число (точніше, про запис цього числа, скажімо, в десятковій системі), треба дозволити собі розглядати записи настільки великих чисел, що ці записи не вмістилися б на земній кулі; т.ч., і тут, відволікаючись від фізич. здійсненності такого запису, використовують абстракцію потенційної здійсненності. Взагалі до абстракції потенційної здійсненності необхідно вдатися для того, щоб міркувати про скільки завгодно довгі слова в заданому алфавіті. Об'єкти, побудова і розгляд яких можливо в рамках абстракції потенційної здійсненності (при протиставленні її абстракції актуальної нескінченності), зв. конструктивними об'єктами. Такими є натуральні числа, представлені своїми записами в к.-л. системі їх позначень, слова в заданому алфавіті тощо, а також пари, трійки та взагалі кінцеві послідовності, складені із записів чисел, слів в алфавіті тощо; раціональні числа (к-рі можна як трійки натуральних) та інших. Конструктивними об'єктами є й висловлювання т.зв. обчислень, або формальних систем, що дозволяє застосувати до останніх апарат теорії А. Всякий А. (розуміє як припис) може (після запису цього припису у вигляді комбінації якихось символів) розглядатися як конструктивний об'єкт. Навпаки, об'єкти, розгляд яких неможливо без залучення абстракції актуальної нескінченності, не належать до конструктивних об'єктів. Так, напр., конструктивними об'єктами є дійсні числа (у сенсі Кантора, Дедекінда чи Вейерштрасса), геометрич. точки (оскільки аналіз такої абстракції, як "крапка", призводить до уявлення про точку як про актуально нескінченну систему малих тіл) і т.д. Конструктивні об'єкти групуються природ. чином в сукупності, прикладами яких служать сукупність всіх слів в даному алфавіті і взагалі будь-яка сукупність всіх об'єктів к.-л. "типу" у складі перерах. вище за типи конструктивних об'єктів. Кожна така сукупність конструктивних об'єктів задається способом конструювання об'єктів, що до неї належать. Інший осн. абстракцією, що використовується при розгляді конструктивних об'єктів та А. є абстракція ототожнення. У деяких випадках про два об'єкти говорять як про однакові. Умови "однаковості" встановлюються щоразу стосовно цієї ситуації. Так, напр., при виробництві обчислень людиною на папері зазвичай буває байдужим шрифт, яким пишуться цифри, і записи 1647 і 1647 розглядаються як однакові; проте можна уявити ситуації, коли істотно відмінність прямого і курсивного шрифтів (як, напр., при сприйнятті слів, які у даної Філософської Енциклопедії). Тоді два записи вже розглядатимуться як неоднакові, але записи 1647 і 1647 однаково – у звичайних випадках – як однакові (хоча фізично це різні об'єкти). Зазвичай приймають, що конструктивні об'єкти складаються з деяких досить простих "елементарних частин" (подібно до того, як слова - з букв) і два конструктивні об'єкти вважаються однаковими, якщо вони складаються з однакових елементарних частин, розташованих в однаковому порядку. Без поняття "однаковості", на основі якого вважаються, напр., однаковими цифри, написані крейдою на дошці, і цифри, написані чорнилом у зошити, неможливе навчання. Абстракція ототожнення дозволяє говорити про однакові об'єкти як про один і той самий об'єкт. Вона призводить до утворення поняття "абстрактного об'єкта": саме два однакові конкретні об'єкти вважаються представниками одного і того ж абстрактного об'єкта. Кожен А. застосований до однакових об'єктів, призводить також до однакових об'єктів. Тому можна вважати, що кожен А. задає процес перетворення абстрактних конструктивних об'єктів. Ця властивість А. (разом з детермінованістю) зумовлює їх повторність чи відтворюваність: будучи вироблений у формі А. над абстрактними конструктивними об'єктами, А. може бути повторно відтворений для будь-яких конкретних конструктивних об'єктів, допустимих для даного А. Зі сказаного має стати зрозумілим, що початкові дані так само як закінчать. результати, що виникають під час здійснення к.-л. А., суть завжди конструктивні об'єкти (будь-яке "стан" алгоритмич. процесу є конструктивний об'єкт!). Неможливість навіть потенційно здійснених процесів над неконструктивними об'єктами пов'язана і з відсутністю способу розпізнавання їх як однакових або неоднакових (пор. відоме положення кібернетики про переваги дискретних форм зберігання перед безперервними). Існують різні т. зр. щодо методів, допустимих при вивченні А. Одна з них, що висувається представниками конструктивного спрямування в математиці та логіці, полягає в тому, що оскільки для утворення поняття А. достатньо абстракцій ототожнення та потенційної здійсненності, то розвиток теорії А. повинен вестися в рамках цих абстракцій. Інша т. зр. допускає щодо А. будь-які методи, взагалі допускаються до логіки і математики, зокрема. та вимагають абстракції актуальної нескінченності. Так, можна собі уявити випадок, коли для доказу того, що деякий А., будучи застосований до деякого об'єкта, дасть результат, потрібно використання тісно пов'язаного з абстракцією актуальної нескінченності закону виключеного третього. Основні поняття теорії А. До осн. понять, що виникають на основі поняття А., відносяться поняття обчислюваної функції, розв'язуваної множини і безлічі. Функція зв. обчислюваної, якщо існує А., що обчислює цю функцію в слід. сенс: а) А. застосуємо до будь-якого об'єкта, що входить в область визначення функції, і дає як результат те значення функції, яке вона приймає для цього об'єкта, взятого в якості її аргументу; б) А. не застосовний до жодного об'єкта, що не входить в область визначення функції. Безліч, розташоване в деякій сукупності конструктивних об'єктів (тобто безліч, складене з якихось об'єктів цієї сукупності), зв. розв'язним (щодо об'ємної сукупності), якщо існує А., що дозволяє це безліч (щодо указ. сукупності) у слід. значенні: А. застосуємо до будь-якого об'єкта з об'ємної сукупності і дає як результат відповідь на питання, чи належить цей об'єкт розглядається множині чи ні. Нарешті, непорожнє безліч (див. Пусте) зв. перелічуваним, якщо існує А., що перераховує це безліч у слід. сенс: а) результат застосування А. до будь-якого натурального числа існує і належить розглянутій множині; б) кожен елемент розглянутої множини може бути отриманий як результат застосування А. до деякого натурального числа. За визначенням, порожня множина також відносять зазвичай до класу перелічуваних. Одна і та ж обчислювана функція (відповідно, розв'язувана множина, перелічувана безліч) може обчислюватися (відповідно, вирішуватися, перераховуватися) за допомогою різних А. З визначень випливає, що аргументи і значення обчислюваної функції, елементи розв'язуваної або перелічуваної множини є завжди конструктивні об'єкти. Замінюючи конструктивні об'єкти (нек-рой фікс. сукупності) їх номерами в довільній алгоритміч. нумерації (тобто такої нумерації, для якої існує А. отримання по об'єкту його номера і назад), можна, як це часто роблять в теорії А., обмежитися розглядом лише таких обчислюваних функцій, аргументи і значення яких суть натуральні числа, і лише таких розв'язуваних і перелічуваних множин, елементи яких суть також натуральні числа. Можна довести, що будь-яке розв'язане безліч можна перерахувати. У той самий час вдалося побудувати перелічуване, але з розв'язувана безліч. Цей перший конкретний приклад (опублікований амер. вченим А. Черчем в 1936 у статті "Одна нерозв'язна проблема елементарної теорії чисел") відсутності А. (а саме, А., що дозволяє побудоване безліч) став джерелом або зразком майже всіх подальших прикладів такого роду. Виявилося, що безліч можна розв'язати тоді, і тільки тоді, коли перерахуємо і воно, і його доповнення (до об'ємної сукупності об'єктів). Т.ч., існують такі доповнення до перелічених множин, які самі неперераховані. Зв'язок теорії А. із логікою. Поняття розв'язуваного і перелічуваного множин тісно пов'язані про класифікацією визначень (ми обмежуємося тут лише такими визначеннями, кожне з яких визначає об'єкти деякого типу або, що те ж саме, деякий клас об'єктів). Як відомо, існують дві осн. схеми визначень: "через рід та видову відмінність" та "за індукцією". При визначенні "через рід і видову відмінність" задається нек-ра об'ємна сукупність об'єктів ("рід") і вказується ознака ("видова відмінність"), що виділяє серед об'єктів указ, сукупності клас об'єктів, що визначаються. Якщо; вважати, що це визначення конструктивно, тобто. що об'єкти конструктивні і що наявність або відсутність видової відмінності в елемента роду алгоритмічно розпізнається, то множина, що визначається, виявляється розв'язним (і кожна розв'язувана безліч можна визначити таким чином). Тим самим розв'язувані множини ототожнюються з множинами, що конструктивно визначаються через рід і видову відмінність. Визначення "по індукції" складається з двох частин: базисної частини, що містить деякий перелік об'єктів, які оголошуються належать до визначеного класу, і індуктивної частини, що свідчить, що якщо об'єкти такого-то і такого виду належать до визначеного класу , те й об'єкти такого-то й такого виду, пов'язані з першими об'єктами нек-рым ставленням, також належать до обумовленого класу. (Можливі й складніші випадки т.зв. перехресних визначень, коли одночасно визначається друг через друга кілька класів об'єктів). Якщо припускати визначення конструктивним, тобто. об'єкти конструктивними, перелік вихідних об'єктів, що міститься в базисній частині, кінцевим, а що містяться в індуктивній частині правила переходу від вже визначених об'єктів до нових алгоритмічних (у тому сенсі, що наявність або відсутність відношення, про яке йдеться в індуктивній частині, розпізнається за допомогою якогось А.), то ми приходимо до поняття множини, що конструктивно визначається за індукцією, або (синонім) ефективно породжуваної множини (оскільки таке визначення задає ефективний породжуючий процес, на окремих етапах розгортання якого "виникають" або "породжуються" об'єкти, що визначаються). Прикладом конструктивного визначення по індукції служить визначення допустимих шахових позицій (тобто позицій, які можуть виникнути на дошці в процесі гри). Базова частина містить одну єдність. вихідну позицію. Індуктивна частина містить правила ходів фігур. Безліч допустимих позицій, тобто ефективно породжується. Іншим прикладом ефективно породжуваної множини служить безліч всіх доведених формул к.-л. формальної системи або обчислення: базисна частина визначення доведених формул містить аксіоми, індуктивна частина - правила виведення (аксіоми оголошуються доказними за визначенням і далі говориться, що якщо будь-які формули доводяться, то і формули, отримані з них за правилами виведення, також доведені). Породжувальним процесом є процес доказу всіх доведених формул. Нарешті, процес спростування всіх спростуваних формул обчислення також є прикладом ефективного процесу, що породжує. Поняття ефективного породжувального процесу дуже тісно пов'язане з поняттям А. Ми дали визначення (приблизне) ефективного процесу, що спирається на поняття А. У свою чергу, поняття породжуючого процесу дозволяє визначити на його основі якщо не саме поняття А., то, у всякому разі , Концепція обчислюваної функції. Дійсно, нехай деякий породжувальний процес здатний "породжувати" об'єкти, що мають вигляд пар (х, у), і нехай у будь-яких двох "породжених" пар з співпадаючими першими членами збігаються і другі члени. Тоді процес слід. чином визначає функцію y = f(x): функція визначена для об'єкта х0 тоді і тільки тоді, коли х0 є перший член к.-л. породженої пари: значення функцій для аргументу х0 дорівнює у разі другому члену цієї пари. Функція, визначена указ. сенсі ефективним процесом, що породжує, очевидно, обчислювана [щоб знайти f(x0), треба розгортати процес до тих пір, поки не знайдемо пари з х0 в якості першого члена]. Назад, будь-яку обчислювану функцію можна визначити за допомогою ефективного процесу, що породжує. Алгоритміч. процеси і процеси, що породжують, близькі один одному з логіч. точки зору. В основі кожного їх лежать лише конструктивні поняття. Відмінність з-поміж них у тому, что алгоритмич. процес розгортається з урахуванням вимоги, а породжуючий – з урахуванням дозволу діяти певним чином. Тут проявляється різницю між необхідним і можливим (в алгоритмич. процесі кожен етап однозначно, тобто. з необхідністю, визначається попереднім етапом, у той час як при розгортанні процесу, що породжує, після кожного етапу виникає лише безліч можливостей для слід. етапу). При належних уточненнях поняття ефективного процесу, що породжує, з'ясовується, що кожне ефективно породжуване безліч перелічимо, і назад. Ця обставина, у поєднанні з наведеними вище взаємовідносинами між переліченими і розв'язними множинами, дозволяє укласти таке. Будь-який клас об'єктів, що допускає конструктивне визначення через рід і видову відмінність, допускає і конструктивне визначення індукції, але не назад: існує клас об'єктів, що конструктивно визначається за індукцією, але не допускає конструктивного визначення через рід і видову відмінність; доповнення до цього класу об'єктів (за об'ємною сукупністю конструктивних об'єктів) не допускає ефективного індуктивного визначення. Кожен конструктивний породжувальний процес можна як процесу отримання доведених формул відповідного обчислення. Тому приклад класу, що володіє тільки що описаними властивостями, можна побудувати у вигляді класу всіх доведених формул деякого обчислення. Більше того, виявилося, що ця обставина має місце для будь-якого достатньо утримують. обчислення (напр., для обчислення предикатів чи обчислень, формализующих арифметику), т.к., якщо обчислення досить змістовно, то ньому можна висловити будь-який ефективний процес, що породжує. Клас всіх доведених формул такого обчислення (являючись, звичайно, перерахованим) не є розв'язним, так що не існує А., що розпізнає доказ формул обчислення; у цьому сенсі кажуть, що літочислення є нерозв'язним. Оскільки клас всіх доведених формул обчислення не можна розв'язати, то доповнить. до нього клас всіх недоведених формул не є перерахованим і, отже, не може бути отриманий жодним процесом, що породжує; зокрема, неможливо побудувати таке обчислення, у якому " спростовувалися " всі недоказувані формули первонач. обчислення і лише вони; тим більше, всі ці недоказні формули не можуть бути спростовані засобами самого первонач. обчислення, отже в первонач. обчисленні є т.зв. нерозв'язні (тобто ні доведені, ні спростовані) формули. У цих міркуваннях можна обмежитися лише такими формулами, які містять. інтерпретації обчислення виражають осмислені (тобто або істинні, або хибні) судження, і виявити, отже, і серед таких формул нерозв'язні. Звідси випливає, що можна пред'явити формулу, що виражає справжнє судження, але з доведену в обчисленні; у цьому сенсі кажуть, що система неповна. Підкреслимо, що з загального характеру проведених міркувань властивість неповноти властиво кожному достатньо містять. обчислення. Поняття нерозв'язності обчислення спирається на поняття А., і не дивно, що факт нерозв'язності встановлюється на основі досліджень в галузі теорії А. Дуже істотною (і, можливо, несподіваною на перший погляд) є та обставина, що такий загальнологіч. факт, як неповнота обчислень (факт, що виражає принципову неможливість повністю формалізувати процес логіч. Виводу і вперше суворо доведений австр. вченим К. Геделем ще в 1931, до уточнення поняття "А."), може бути отриманий, як ми тільки що бачили, засобами теорії А. Ця обставина вже одна показує величезні можливості застосування теорії А. до питань логіки. Ці застосування не обмежуються наведеним прикладом. Ще 1932 сов. вчений А. Н. Колмогоров запропонував тлумачення створеної інтуїціоністами конструктивної логіки за допомогою утримуючих. засобів, що не мають жодного відношення до установок інтуїціонізму; саме, кожну пропозицію конструктивної логіки Колмогоров запропонував тлумачити як проблему. Поняття проблеми вимагало, однак, конкретизації, яка могла бути дана тільки на базі вже розробленої теорії А. Два конкретних класу проблем, придатних для інтерпретації конструктивної логіки, запропонували, відповідно, амер. вчений С. К. Кліні в 1945 та сов. вчений Ю. Т. Медведєв у 1955. У 1956 рад. вчений Н. А. Шанін висунув нову концепцію, згідно з якою не всяке висловлювання конструктивної логіки вимагає тлумачення у вигляді проблеми. До цього кола ідей примикають питання "конструктивізації", або "знаходження конструктивних аналогів", класич. математич. понять та пропозицій; вирішення цих питань також можливе лише на основі теорії А. Конструктивізація осн. понять математич. аналізу призвела до т.зв. конструктивний математич. аналізу. Намічаються шляхи конструктивізації та інших. математич. теорій. Одним із осн. прийомів, що використовуються при конструктивізації, є перехід від предметів, що вивчаються, до їх імен, які завжди є конструктивними об'єктами. П р о б ле м і р а з рішення. Окремим випадком масових проблем є вирішення проблеми. Проблеми вирішення к.-л. безлічі є проблема побудови А., що дозволяє це безліч. відповідності. серія одиничних проблем складається з проблем відповіді питання приналежності до безлічі, поставлений кожному за об'єкта з об'ємної сукупності конструктивних об'єктів. Назад, будь-яка масова проблема, відповідності. серії одиничних проблем відповіді питання, може бути розглянута як проблема вирішення деякої множини, саме - безлічі тих одиничних проблем, відповіддю на які служить " так " . Звідси ясна важлива роль проблем вирішення. Саме вони піддавалися вивченню з т. зр. їх розв'язання. Серед проблем вирішення виділяються проблеми, поставлені для класів доведених формул обчислень. Проблема вирішення класу всіх доведених формул к.-л. обчислення зв. також проблемою вирішення самого обчислення. (У рус. текстах проблему вирішення зв. зазвичай "проблемою розв'язності"; проте "проблемою розв'язності" краще називати проблему: "відповісти, чи має рішення дана проблема вирішення"). Нерозв'язні масові проблеми. Проблема вирішення к.-л. обчислення завжди є проблема вирішення перелічуваної множини. Взагалі всі проблеми, що природно виникали в математиці, виявлялися проблемами вирішення перелічуваних множин. Такий згадуваний вище перший приклад нерозв'язної проблеми вирішення (і водночас перший приклад нерозв'язної масової проблеми взагалі), опублікований Черчем в 1936. Така т.зв. проблема тотожності для асоціативних систем, докази нерозв'язності якої опублікували в 1947 незалежно один від одного А. А. Марков і амер. вчений Е. Л. Піст; цей результат представляє інтерес як перший приклад доказу нерозв'язності масової проблеми, що виникла (ще в 1914) поза логікою і теорією А. Така і знаменита проблема тотожності для груп, поставлена ​​ще в 1912, нерозв'язність якої доведена в 1952 сов. вченим П. С. Новіковим (Ленінська премія, 1957). Кожна з проблем тотожності полягає у пошуку А., що встановлює еквівалентність або нееквівалентність двох слів у заданому алфавіті (від того чи іншого визначення еквівалентності залежить, чи маємо ми справу з асоціативною системою або групою). Тому проблему тотожності можна як проблему вирішення безлічі всіх пар еквівалентних одне одному слів (щодо сукупності всіляких пар слів). При цьому, оскільки можна задати процес отримання всіх пар еквівалентних один одному слів, безліч всіх таких пар перелічимо. С о д і м о с т ь. Починаючи з прикладу Черча 1936 і 1944 всі докази нерозв'язності масових проблем проводилися або могли бути проведені слід. одноманітним способом. Заздалегідь нерозв'язна проблема, досліджена Черчем, зводилася до масової проблеми, що розглядається, так що якби розглянута масова проблема була розв'язною, то виявилася б розв'язною і проблема Черча (у цьому сенсі можна сказати, що доказ нерозв'язності аналізованої проблеми зводилося до доказу нерозв'язності проблеми Черча). Виникло питання, чи для будь-якої нерозв'язної проблеми вирішення її нерозв'язність може бути встановлена ​​в такий спосіб. Це питання, що отримало назву проблеми зведеності, було поставлено Постом у 1944; одночасно Пост навів кілька прикладів нерозв'язних проблем вирішення, нерозв'язність яких була встановлена ​​ним методом, відмінним від описаного вище (ці приклади не вирішували ще проблему зведеності, оскільки залишалося відкритим питання, чи не можна і для них знайти такі докази нерозв'язності, які зводилися б до доказу нерозв'язності проблеми Черча, згодом для деяких із зазначених прикладів такі докази були дійсно знайдені). Проблема зведеності стояла в центрі досліджень з теорії А. аж до 1956 року, коли вона була вирішена незалежно сов. вченим А. А. Мучником та амер. вченим Р. М. Фрідбергом. Вил побудований приклад нерозв'язної проблеми вирішення (для перелічуваної множини), нерозв'язність якої не можна довести зведенням до цієї проблеми проблеми Черча. Мучник показав навіть більше, а саме, що не тільки проблема Черча, але й ніяка інша проблема не може служити "стандартною нерозв'язною проблемою" в тому сенсі, що доказ нерозв'язності будь-якої нерозв'язної проблеми розв'язання для перелічуваної множини міг

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

Властивості алгоритму:

-дискретність-Послідовність вирішення (процес) завдань має бути розбитий на послідовність окремих кроків.

-зрозумілість-Алгоритм обов'язково повинен бути зрозумілий виконавцю. У зв'язку з цим алгоритм необхідно розробляти з орієнтацією на опр-ого виконавця, тобто. в алгоритм можна включати команди із систем команд даного виконавця.

-детермінованість- будучи зрозумілим, алгоритм ні містити команди, сенс яких може сприйматися неоднозначно. Порушення упорядниками алгоритмів цих вимог призводить до того, що та сама програма після виконання різними виконавцями дає не однакові результати.

-результативність-полягає в тому, що при точному виконанні всіх команд алгоритму, процес вирішення завдань повинен припинитися за кінцеве число кроків і при цьому повинен бути отриманий опред-ий при постановці завдань результат.

-масовість- Придатність алгоритму для вирішення завдань деякого класу.

Способи запису алгоритму:

-словесний- Метод природною мовою.

-графічний-Описання алгоритму за допомогою схем.

Процес виконання операцій чи груп операцій

введення вихідних даних, виведення результату

Рішення-вибір напряму виконання

Модифікація - виконання операцій, що змінюють команди або групи команд, що змінюють програми.

З'єднувачі ліній на одній сторінці.

Міжсторінкові з'єднувачі.

-мова програмування-Зручний для введення в комп-р.

-псевдокод-це мова, який використовує структуру і синтексис досить формалізованої мови і одночасно допускає конструкції природ. Мова.

Види алгоритмів та основні принципи складання алгоритмів.

-Лінійний– алгоритм, в якому команди виконуються послідовно один за одним у порядку їх природного слідування незалежно від будь-яких умов. S1, s2, S3 ... Sn

-розгалужений (розгалужений)- це процес, в якому його реалізація відбувається по одному з декількох заздалегідь передбачених напрямків, в залежності від вихідних даних або проміжних результатів.

· Повна умовна конструкція (повне розгалуження)

· Неповна умовна конструкція

· Вибір з декількох

-циклічний– алгоритм, в якому послідовність може виконуватися більше 1 разу.

· Цикл з параметром

· Цикл з передумовою. Може не виконатися жодного разу. У тілі циклу обов'язково нах-ся оператор, який змінює значення змінної, що входить в блок Q.

· Цикл з постумовою. Виконується хоч раз.

Основні принципи алгоритмізації:

1. Виявити вихідні дані, результати та призначити їм імена.

2. Метод розв'язання задач.

3. Розбити метод вирішення завдань на етапи.

4. При граф-му поданні алгоритму кожен етап у вигляді відповідного блоку -схеми алгоритму та вказати лініями зв'язку порядок їх виконання.

5. В отриманій схемі за будь-якого варіанта обчислень.

Передбачити видачу результатів або повідомлень про їхню відсутність.

Забезпечити можливості після виконання будь-якої операції так чи інакше перейти до блоку кінець.

40. Основні алгоритмічні структури

Ми вже розглянули основні поняття програмування і переходимо трохи ближче до справи (але лише ближче програмуватимемо пізніше).

Розглянемо основні структури алгоритмів, які шість:

· Слідування.Це послідовність блоків (або груп блоків) алгоритму. У програмі проходження представлено у вигляді послідовного виконання операцій

·
Розгалуження.Ця алгоритмічна структура застосовується в тому випадку, коли в залежності від умови необхідно виконати одну чи іншу дію

·
Обхід.Ця структура є окремим випадком розгалуження, коли в одній з гілок немає жодних дій.

·
Множинний вибір.Ця структура є узагальненням розгалуження, коли необхідно виконати одну з кількох дій, залежно від значення змінної A.