Способи опису алгоритмів
1. Алгоритм і його властивості. Способи опису алгоритму
Для пояснення поняття «алгоритм» важливе значення має визначення поняття «виконавець алгоритму». Алгоритм формулюється в розрахунку на конкретного виконавця; алгоритм є керівництвом до дії для виконавця, тому значення слова «алгоритм» близьке за змістом до значення слів «вказівку» або «розпорядження». Можна сказати, що алгоритм - зрозуміле і точне розпорядження виконавцю здійснити певну послідовність дій для досягнення зазначеної мети чи розв'язання поставленої задачі або алгоритм - точне розпорядження, яке задає обчислювальний процес, що починається з довільного початкового даного з деякої сукупності можливих для цього процесу даних і спрямований на отримання повністю визначається цими вихідними даними результату.
Основні властивості алгоритму.
1. Алгоритм має деяке число вхідних величин - аргументів, що задаються до початку виконання. Мета виконання алгоритму - отримання результату, що має цілком визначене ставлення до вихідних даних. Для алгоритму можна вибирати різні набори вхідних даних з безлічі допустимих для цього процесу даних, тобто можна застосовувати алгоритм для вирішення цілого класу задач одного типу, що розрізняються вихідними даними. Це властивість алгоритму називаютьмасовістю. Однак існують алгоритми, що застосовуються тільки до єдиного набору даних. Тоді властивість масовості означає застосовність алгоритму до всіх об'єктів цього класу.
2. Щоб алгоритм можна було виконати, він повинен бути зрозумілий виконавцю. Зрозумілість алгоритму означає знання виконавця про те, що треба робити для виконання цього алгоритму.
3. Алгоритм представляється у вигляді кінцевої послідовності кроків, (алгоритм має дискретну структуру) і його виконання розчленовується на виконання окремих кроків.
4. Кожен крок алгоритму має бути чітко і недвозначно визначено і не повинен допускати довільного трактування виконавцем. Алгоритм розрахований на суто механічне виконання. Саме визначеність алгоритму дає можливість доручити його виконання автомату.
5. Виконання алгоритму закінчується після виконання кінцевого числа кроків. При виконанні алгоритму деякі його кроки можуть повторюватися багато разів.
6. Кожен крок алгоритму має бути виконаний точно і за кінцевий час. Алгоритм повинен бути ефективним.
Навчальнаалгоритмічнамова
(НАМ)- система позначень і правил для запису алгоритмів,
зрозумілихвиконавцю.
Алфавіт
НАМ складається з букв українського і латинськогоалфавітів,
символіварифметичнихоперацій, розділовихзнаків. Словник
НАМ утворюють слова, за
допомогоюякихзаписуютьвказівки, щовходять до системивказівоквиконавця. Для
наочності й однотипностізаписуалгоритміввикористовують службові
слова:
Запис
заголовку, позначення початку й кінця алгоритму-алг, поч, кін
Позначення
типу змінних та стандартних величин-нат(натуральний), ціл(цілий),
дійсн(дійсний), літ(символьний), таб(табличний)
Позначеннязмінних
для введення та виведенняданих-арг (аргументи, введенняданих), рез (результати,
виведенняданих)
Запис
умов і конструюванняскладних умов — якщо то, інакше, все, не, і, або, поки
Записциклів —
пц (початок циклу), кц (кінець циклу)
Запис
алгоритму НАМ виконується за схемою:
алг<назва алгоритму> (<тип змінних>)
арг<іменазмінних-аргументів>
рез
<іменазмінних-результатів>
поч<тип та іменапроміжнихзмінних>
<тіло алгоритму>
кін
Правила опису алгоритму Нам
1. Кожен
алгоритм маєім'я (заголовок), щобможнабуловідрізнитийоговідінших. Наприклад: алг квадратнерівняння
2. За
ім'ям алгоритму записують (у круглих дужках) змінні, вказуючи тип та ім'якожної
з них. Наприклад:
алг квадратнерівняння
(дійсн a, d, c, x1, x2)
3. За
словом арг записуютьіменазмінних,
які є вхіднимиданими, а за службовим словом рез —
іменазмінних, які є результатами.
4.
Післяслужбового слова почзаписують проміжнізмінні (які не
належать ні до аргументів, ні до результатів), вказуючи тип та
ім'якожноїзмінної. Наприклад: почціл k, дійсн S.
5.
Міжслужбовими словами поч і
кін записується тіло
алгоритму: вказівкаабосеріявказівок, при цьомувказівки, записанів
одному рядку, відокремлюютьсярозділовим знаком «;».
Базові структури алгоритмів (керуючи структури) – це
способи керування процесом обробки даних.
Існує три базові структури алгоритмічної конструкції:
1. лінійні алгоритми
(слідування)
2. умова (розгалуженя)
3. цикли (повторення)
Лінійна структура передбачає, що тіло алгоритму
являє собою послідовність команд, виконуваних одна за одною.
Умова (розгалуження) – це керуюча структура, що
передбачає можливість вибору з кількох варіантів, для кожного з яких, залежно
від умови виконується різна послідовність команд.
Цикл – це керуюча структура, що дозволяє
багаторазово повторювати задану послідовність команд.
- Цикл з передумовою
- Цикл з післяумовою
- Цикл із параметром
Способи опису алгоритмів:
- Словесний
- Формульний
- Графічний
- Алгоритмічною мовою
Задача: знайти корені квадратного рівняння ах2+bх+с=0
Словесний:
1. Розпочати процес обчислень
2. Визначити a,b,c
3. Обчислити D =b2+ac
4. Якщо D>0, то перейти на крок 8 інакше на крок 5
5. Обчислити
6. Вивести на
екран X1 X2
7. Перейти на крок 9
8. Вивести повідомлення про те,
що коренів немає.
9. Завершити процес обчислень.
Формульний
Графічний
Блок – схема – графічне зображення алгоритмів за допомогою
окремих блоків.
Початок або кінець Блок перевірки умови
алгоритму
Блок введення,
Виведення
даних Блок виклику підпрограм
Блок
обчислень Виведення документу
1
Початок
2
a,b,c
3
D =b2+ac
45
D>0 так
8ні
Рішень
немає 6
7
Вивести х1 х2
9
Кінець
Лінійна структура передбачає, що тіло алгоритму
являє собою послідовність команд, виконуваних одна за одною.
|
Виконати
дію
А
|
|
Виконати
дію N
|
|
Виконати
дію
В
|
.....
Умова(розвилка, розгалуження) – означає перевірку значення логічного виразу(ЛВ) та вибір одного з двох
варіантів дій, залежно від значення ЛВ. В ЛВ можуть використовуватися логічні
операції «НЕ» «І» «АБО». ЛВ може набувати одного здвох значень – істина чи хиба.
Наприклад: алгоритм обчислення значень
функції
можна
представити в такому вигляді:
х<>0
так ні
y = 0
Можливо
, що при одному зі значень ЛВ на потрібно виконувати жодних дій. В такому
випадку існує коротка форма розгалуження:
|
x>0
|
Ні
Так
|
Виконати
дію
|
Цикл означає повторення виконання тієї самої дії,
або блока дії, що звуться тілом
циклу, доти,
поки певний ЛВ лишатиметься істинним.
1.
« цикл – поки», або цикл з передумовою,
(умова перевіряється
перед виконанням циклу).
На першому кроці
перевіряється значення
ЛВ. І<n
Якщо воно є істинним –
виконується тіло циклу.
Потім на другому кроці знову
перевіряється значення ЛВ s=s+a1
і якщо воно істинне знову
виконується тіло циклу.
Цикл завершується, коли
значення ЛВ стає
помилковим. I=i+1
В тілі циклу повинні бути
команди, які змінюють
значення величини, яка
входить в ЛВ.В циклі
використовують лічильник циклів, який рахує кроки циклу.
На початку алгоритму значення
лічильника дорівнює 0.
2. « цикл – до», або цикл з післяумовою,
(умова перевіряється після
виконанням
циклу). s=s +a1
Це означає, що тіло
циклу – добуде виконано .
принаймні один раз. « цикл
– до»
повторюється
доти, поки значення ЛВ
є помилковим, іI = i + 1
завершується коли воно
стає
істинним.
I > n
Структурнийпідхідпередбачаєвикористаннятількидекількохосновних
структур, комбінаціяякихдає все різноманіттяалгоритмів і програм.
Послідовнерозміщенняблоків і групблоків.
У програміреалізуєтьсяпослідовнимрозміщеннямоператорів
Розгалуження
Цеалгоритмічна альтернатива. За цією командою
виконавецьвибирає один ізшляхіввиконання алгоритму з неодміннимвиходом на
загальнепродовження. Вибірвідбувається по якомусьумові і може в свою
чергуміститикількаетапів.
На
природніймовірозгалуженнявідповідаєпослідовністьоператорів:
Якщо<Умова>
«ВиконуєтьсяабоІСТИНА» тоді<Дію
1>інакше<Дію 2>
Кінецьрозгалуження
Розглянутийваріанткомандирозгалуженняназиваєтьсяповнимрозгалуженням.
Якщо ж на гілки «НЕТ »відсутняпослідовність
команд, то такерозгалуженняназиваєтьсянеповнимчиобхід
М н о ж е с т в е н н и й
в и б о
р .
Є узагальненнямрозгалуження, коли в
залежностівідзначеннязмінної (I) виконується одна з декількохдій. При I = 1
виконуєтьсядія S1, при I = 2 - дія S2 і т.д.
Якщо на гілкахрозвилки в свою
чергузнаходятьсярозгалуження, то говорять, щотакий алгоритм має структуру Вкладенихрозгалужень
У мовахпрограмуваннявисокогорівнярозгалуженняреалізується
за допомогоюумовного оператора.
Цикл
Способивирішеннябагатьохскладнихзавдань часто засновані
на повторенні одних і тих же дій аж до досягненняпевної мети.
Організаціяповторень в алгоритмах називається циклом.
Протеорганізаціяциклів, ніколи не приводять до зупинки у
виконанні алгоритму, є порушеннямвимогийогорезультативності.
Розглянемографічнепредставленняциклічного алгоритму. В ньоговходять як
базовихелементівнаступніструктури: логічнийелемент з перевіркоюумови і блок,
званий тілом циклу. Розглянемоосновнірізновидициклічнихалгоритмів
Технологія побудови з гори в низ
Знизу вгору
У
простих випадках, коли неважко передбачити, які процедури знадобляться в
головному алгоритмі, можна почати вирішення завдання з написання допоміжних алгоритмів нижнього рівня.Тобто з процедур, які містять тільки команди з СКІ , без викликів інших процедур. Від нижнього рівня можна перейти до процедур
для опису більш складних дій, а в самому кінці скласти головний алгоритм.
Такий метод побудови алгоритмів називають програмуванням знизу вгору: від нижнього рівня - до верхнього, від простих приписів - до більш складних, від приватного - до загального. Суть цього методу: використовуючи вже написані алгоритми, як допоміжні, звести задачу до вже вирішеним.
Такий метод побудови алгоритмів називають програмуванням знизу вгору: від нижнього рівня - до верхнього, від простих приписів - до більш складних, від приватного - до загального. Суть цього методу: використовуючи вже написані алгоритми, як допоміжні, звести задачу до вже вирішеним.
|
Схоже на маніпуляції з
дитячим конструктором: з елементарних деталей спочатку збираються прості
блоки, з них - більш складні, і врешті-решт з великих блоків виходить (або не
виходить) задумана юним конструктором машинка.
|
Однак, далеко не завждицей метод результативний. Нерідко
при переході на черговийрівеньз'ясовується, щонаписані на попередніхетапахпроцедуризовсіммарні
при складаннічергового алгоритму. Нарікаючи
на даремновитраченого часу, доводиться повертатися до нижньогорівня і
починатиспочатку.
Зверху вниз (МПУ)
У
важких випадках програма складається у зворотному порядку - зверху вниз.
Щобзрозуміти, якіпроцедуридійснонеобхідні для
виконаннязавдання, а потімописуватитількиїх, достатньопочати з загального
плану. Цей план одночасно є і головним алгоритмом,
а йогопунктиіменами майбутніх процедур. Таким
чином з'ясовуються не тількиімена процедур, а й порядок, в якомуїх треба
викликати.
На наступномуетапіможнапереходити до уточнення окремихпунктівзагального
плану, тобто до написання допоміжнихалгоритмів . Тут
можназастосувати той самийприйом: відразуприступати до сотавленіюпроцедури, замінюючивсіприписи,
якихнемає в СКІ, викликаминовихдопоміжнихалгоритмів.
Зрозуміло,
що на кожному етапідоведеться послідовно уточнювати пункти
плану виник на попередньомурівні. І так
до тих пір, поки на самому нижньомурівні не вийдутьпроцедури, щоскладаютьсятільки
з команд, щовходять в СКІ . Це і
є метод послідовногоуточнення.
|
Уявіть юного
конструктора, котрий, перед тим як почати малопередбачуваним діяльність по
з'єднанню деталей, вирішується накидати малюнок майбутнього чуда техніки,
потім - креслення його основних блоків, потім частин цих блоків і так до тих
пір, поки не буде абсолютно ясно, як ці дрібні частини виходять з
елементарних деталей конструктора.
|
- вихідна задача розбивається на ряд великих частин (Підзадач);
- спочатку повністю складається основний алгоритм (план рішення задачі);
- при цьому для вирішення підзадач (пунктів плану) використовуються команди виклику ще не написаних допоміжних алгоритмів;
- потім складаються допоміжні алгоритми, які в свою чергу можна розбити на підзадачі для виконання більш дрібних дій.
Струк.
Прог.
o Отже,
структурнепрограмування є технологієюпрограмування, яка об’єднує
o способискладання
добре структурованихнадійнихпрограм, зручнихдля
o читання
і розумінняїхлюдиною, слідкування за логікоюїхроботи,
o внесення
до них виправлень та іншихзмін. Згідно з думкоюН.Вірта
o “структурізація
є принциповимінструментом, якедопомагаєпрограмісту
o систематично
синтезуватискладніпрограми, зберігаючи про них повне
o уявлення”
[1].
o
o Реалізаціяцихідей
заснована на таких принципах:
o
o аналітичне
(згори донизу) програмування;
o
o структурнекодування
,тобтовикористаннялишебазовихелементів
o програми;
o
o принцип
модульності.
o
o З точки
зору структурного програмування, правильна програма – це
o програма,
структура якоївключаєтількибазовіелементи, і жоден з цих
o базовихелементів
не є недоступним і не допускаєзациклювання. Правильна
o програмамаєтільки
один вхід і тільки один вихід. В правильнійпрограмі
o не
повинно бути такихчастин, якініколи не виконуються.
o Принцип
модульності
o
o Принцип модульностіполягаєу
тому, щопрограмарозбивається на логічно
o незалежнічастини
(модулі), якідотримуютьсязв’язків. Історичнопоняття
o модульноїпрограмивиниклораніше,
ніжбулисформульованіпринципи
o структурного
програмування, протецяідеявиявилася просто необхідною
o те
цяідеявиявилася просто необхідною
o складовоюновоїтехнологіїпрограмування
разом з аналітичним
o проектуванням.
o
o Поняття
модуля цілкомлогічноз’являється на відповідномуетапі
o аналітичногопрограмування:
модуль – цечастинапрограми, яка розв’язує
o порівнянонескладну
задачу, логічнонезалежнувідінших задач.
o
o Зовсім
просто: модулі – цепідпрограми (процедуриабофункції), які
o маютьпевнівластивості.
o
o Деякінеобхіднівластивості
модуля:
o
o єдинийвхід,
єдинийвихід (деякімовидозволяютьіснуваннядекількох
o входівабовиходів);
o
o окремакомпіляція;
o
o кожний
модуль доступний за своїмідентифікатором;
o
o модуль
можевикликатиінший модуль;
o
o модуль
не повинен зберігатиісторіюсвоїхвикликів (інакшеможевиникати
o так
званий побічнийефект);
o
o модуль
порівняно невеликий;
o
o кожен
модуль відповідаєлишеоднійзадачі;
o
o незалежністьфункціонування
(заміна модуля на аналогічний не впливає на
o всю
програму).
o
o З часом,
коли принцип модульності став підтримуватисьмовами
o програмування,
на перший план висунуласьвимогалогічної та програмної
o незалежності
модуля.
o
o Слідзауважити,
щоповноїнезалежностіміж модулями бути не може.
o Залежністьміж
модулями існує:
o
o через
списки параметрів;
o
o тоді,
коли воникористуютьсяспільними (глобальними) змінними;
o
o всімодуліпрограмизалежатьвідструктуриданихцієїпрограми;
o
o модулізалежатьвідлогікифункціонуванняпрограми
(від того фактору, що
o модуль
можевикликатисяіншими модулями).
o
o Отже,
модуліповинні бути незалежні в межах інтерфейсупрограми і
o структуриданих.
Практика показала, щочимвищийстепіньнезалежності
o модулів,
тимпростішерозібратись в окремих модулях і в програмі в
o цілому;
тимменшаймовірністьз’явленняновихпомилок при виправленні
o старих,
абовнесеннізмін в програму, тобтоменшаймовірність так
o званого
хвильовогоефекту.
o
o Ізсказаноговищевипливає,що
не слід без крайньоїнеобхідності
o використовувати
в модулях глобальнізмінні. Всізв’язкиміж модулями
o повинніпідтримуватися
через списки параметрів.
o
o 1.2.
Процедурнаабстракція. Модулі в TurboPascal.
o
o Процедурнаабстракція
– цефілософія, яка полягаєу тому, що при
o розробціпідпрогрампіклування
про те, що повинна виконувати процедура
o абофункція,
відокремлюєтьсявід того, як цевиконується.
o
o Потенціалпроцедурноїабстракціїбільшповноможнареалізувати
не у
o стандартнійреалізаціїмови
Паскаль, а у TurboPascal (TP).
o
o Післяутворенняякоїсьпроцедури,
яка маєуніверсальнезначення, TP
o надає
вам можливістьпоміститиїї у свою особистубібліотекупідпрограм,
o або
модуль (unit). Потімцей модуль можнавикористати (імпортуватицю
o процедуру)
в іншійпрограмі. При цьомувидійсновідокремлюютещовід
o як.
Знаючи, щоробить дана процедура і як їївикликати, ви можете без
o обмеженьїївикористовувати,
не маючи при цьомужодногоуявлення, як
o саме
вона реалізована [7, 11].
o
o Модулі
TP знаходяться в окремих файлах на диску. Вониможутьмістити
o описи
констант, типівданих, змінних, процедур і функцій. Компілювати
o модуль і
виправляти у ньомузнайденіпомилкиможнаокремовідпрограм, у
o ожнаокремовідпрограм,
у
o якихцей
модуль використовується.
o
o Виклик:
usesMyUnit;
o
o Структура
модуля аналогічна до структури Паскаль-програми:
o
o unit<ім’я
модуля>;
o
o interface
o
o загальнодоступні
описи
o
o implementation
o
o приховані
описи (змінні, вкладеніпроцедури і т.д.)
o
o описи
загальнодоступних процедур і функцій
o
o [розділініціалізації]
o
o end.
Моделювання біологічних систем - процес
створення моделей біологічних
систем з характерними їм властивостями. Об'єктом моделювання може стати
будь-яка біологічна система
Хижак-Жертва
Припустимо,
що на деякійтериторіїмешкають два види тварин : кролики (харчуються рослинами )
і лисиці (харчуються
кроликами). Нехай число кроликів ,
Число лис .Використовуючи Модель Мальтуса з
необхідними поправками, щовраховуютьпоїданнякроликівлисицями, приходимо до
наступногосистемі, що носить ім'я моделіВольтерра - Лотки:
Ця
система має рівноважний стан ,
коли число кроликів і лисиць постійно. Відхиленнявідцього
стану призводить до коливаньчисельностікроликів і лисиць, аналогічнимколиваннямгармонійногоосцилятора . Як
і у випадкугармонійногоосцилятора, цеповедінка не є структурно стійким :
малезмінамоделі (наприклад, щовраховуєобмеженістьресурсів, необхідних кроликам)
може привести до якісноїзміниповедінки . Наприклад, рівноважний стан може
стати стійким, і коливаннячисельностібудуть затухати . Можлива
і протилежнаситуація, коли будь-яке малевідхиленнявідположеннярівновагипризведе
до катастрофічнихнаслідків, аж до повного вимирання одного
з видів. На питання про те, який з цихсценаріївреалізується, модель
Вольтерра - Лотки відповіді не дає: тут потрібнідодатковідослідження.
З точки
зорутеоріїколивань модель Вольтерра - Лотки є
консервативною системою, має перший інтеграломруху. Ця система не є
грубою, оскількинайменшізміниправійчастинірівняньпризводять до
якіснихїїзміндинамічногоповедінки. Однак, можливо "злегка"
модифіковані праву частинурівнянь таким чином, що система стане
автоколебательной.Наявністьстійкого граничного циклу, властивого грубим
динамічним системам, сприяєзначномурозширеннюобластізастосуваннямоделі
БІОЛОГІЧНІ МОДЕЛІ
БІОЛОГІЧНІ МОДЕЛІ
Будь-яку кінетичну
біологічну систему можна охарактеризувати як сукупність деяких параметрів,
значення яких підтримуються незмінними протягом часу спостереження за системою,
та змінних у часі. Параметрами є, наприклад, такі фізичні величини, як температура,
вологість, електрична провідність мембрани, рН і т. д. Залежно від
досліджуваних біосистем змінними вважаються: в екології – чисельність виду, у
біофізиці – мембранний потенціал, у мікробіології – кількість мікроорганізмів,
у біохімії – концентрація речовини тощо.
Припустимо, що в
біосистемі є різних компонент (напр., хімічних
сполук), які з часом зазнають метаболічних перетворень. Це означає, що значення
концентрації кожної -ї сполуки ( ) змінюється з часом унаслідок її взаємодії з будь-якою
іншою ( ) компонентою. Такого припущення
достатньо для побудови загальної математичної моделі, яка є системою диференціальних рівнянь першого порядку.
(2.1.1)
У системі (2.1.1),
де – швидкості зміни невідомих концентрацій
(змінних), – деякі функції, які можуть залежати
як від внутрішніх (напр., рН), так і від зовнішніх (напр., температура)
параметрів біосистеми.
Знайти загальний розв'язок
моделі (2.1.1) в аналітичному вигляді, як правило, вдається лише тоді, коли
вона є лінійною. Однак процеси, які відбуваються в біологічних системах, як
правило, є нелінійними; відповідно нелінійними є й математичні моделі цих
процесів. Проте існують методи якісного аналізу диференціальних рівнянь, які дають
можливість виявити важливі загальні властивості (закономірності) моделі
(2.1.1), не знаходячи в явному вигляді невідомі функції .
Ці методи базуються на
таких експериментальних фактах. По-перше, різні функціональні процеси в
біосистемах суттєво відрізняються один від одного за часом проходження або
характерними швидкостями. Так, наприклад, у біосистемі одночасно мають місце
швидкі процеси ферментативного каталізу (час обороту ферменту становить с), фізіологічні процеси (час – хвилини) та процеси
репродукції (від кількох хвилин і більше). По-друге, якщо окремі (проміжні)
стадії загального процесу в біосистемі характеризуються часом і найповільніша стадія має час такий, що , то визначальною ланкою всього процесу є -та стадія, і загальний час проходження процесу практично
збігається з . Отже, наявність такої часової
ієрархії процесів у біосистемі дає можливість значно спростити вихідну модель,
звівши її, по суті, до кінетичного опису поведінки найбільш повільної стадії.
Як видно з рівнянь
(2.1.1), зміна стану системи описується деякою точкою у -мірному просторі значень змінних . Простір з координатами називається фазовим. Крива, яку описує
в цьому просторі точка , називається фазовою траєкторією.
Однією
з важливих властивостей відкритих систем (на відміну від ізольованих) є
наявність у них стаціонарних станів. За означенням, у стаціонарному
стані
.
(2.1.2)
У результаті отримуємо
систему алгебраїчних рівнянь для визначення стаціонарної (особливої) точки
фазового простору :
(2.1.3)
Динамічні біосистеми, які описуються
за допомогою звичайних диференціальних рівнянь типу (2.1.1), називаються
точковими системами. Це означає, що в будь-якій точці такої системи значення
шуканої величини (напр., концентрації речовини) зберігається з часом. Однак
загальнішим є випадок, коли значення змінних є різними в різних точках
простору. Наприклад, коли одночасно з реакцією, яка відбувається на деякій
ділянці системи, реагенти дифундують, переходячи до іншої ділянки. Кінетичні
рівняння, які враховують дифузійний зв’язок між окремими ділянками простору в
біосистемі, мають вигляд
(2.1.4)
де – коефіцієнт дифузії речовини , – просторова координата.
Система рівнянь (2.1.4) дає можливість
пояснити деякі загальні принципи процесів самоорганізації в живих організмах.
Модель Мальтуса одновидової
популяції
Розглянемо модель одновидової
біологічної популяції. Через позначимо кількість особин у момент часу . Наша мета – вивести закон зміни кількості особин із
часом. Для цього, згідно з принципами математичного моделювання, зробимо деякі
спрощувальні припущення. А саме: будемо вважати, що дана популяція існує
ізольовано й на деякій території розміщена однорідно. Пізніше ми ці припущення
дещо послабимо.
Виберемо закон, згідно з яким
відбувається розвиток популяцій. За основу візьмемо відомий закон Мальтуса:
швидкість зміни популяції пропорційна величині популяції з певним коефіцієнтом,
що є різницею між коефіцієнтом народжуваності і смертності . За цих припущень можна отримати закон зміни чисельності
популяцій, що в математичній формі має вигляд
.
(2.1.5)
З формули (2.1.5) можна зробити
висновки про зміни чисельності з часом. Так, якщо (миттєва народжуваність більша за миттєву
смертність), то при ; якщо , то – чисельність із часом не змінюється; якщо – чисельність популяції прямує до нуля.
З математичного погляду дана модель є
дуже зручною, оскільки її можна повністю дослідити. Зокрема, з неї випливає
результат, який ще у 1798 р. отримав Мальтус і запропонував свою “похмуру
теорію”: людство може вижити, тільки якщо періоди зростання в
геометричній прогресії будуть перериватися епідеміями, війнами й стихійними
лихами. Дійсно, це той випадок, коли і при . Насправді це не так. Модель Мальтуса дуже наближено
відповідає оригіналу, коли інтервали часу є невеликими. Її можна розглядати
лише як перше наближення до реального процесу.
Дуже складний процес зміни чисельності
населення, залежний до того ж від свідомого втручання самих людей, не може
описуватись простими законами. Навіть в ідеальному випадку ізольованої
біологічної популяції запропонована модель не відповідає реальності повною
мірою хоча б через обмеженість ресурсів, необхідних для її існування. З цього випливає
так званий ефект насичення.
Вправа. За яких умов на і є:
1) обмеженою при ;
2) періодичною?
Більш точна модель має враховувати
конкурентну боротьбу в обмеженому життєвому просторі. Зробимо відносно моделі
таке припущення, що підтверджується практичними спостереженнями:
середньостатистична кількість попарних сутичок у популяції за одиницю часу
пропорційна . Тоді рівняння балансу “зміна
кількості” = “приріст” – “втрати” можна подати у вигляді
.
(2.1.6)
Це рівняння вивів у 1837
р. данський учений Ферхюльст. Воно називаєтьсялогістичним і є
математичною моделлю одновидової популяції з урахуванням ефекту насичення.
Проаналізуємо дану
математичну модель. Основна вимога до неї – досить точно описувати реальний
процес за великих значень . З математичного погляду цій вимозі відповідає нелінійне
рівняння Ріккатті, загальний розв’язок якого може бути знайденим у квадратурах
шляхом його зведення до лінійного. Однак точні формули виявляються досить
громіздкими для практичного користування. Проте нас цікавить лише асимптотична
поведінка розв’язків при . Таке дослідження у випадку, коли і є сталими, можна провести й без інтегрування
рівняння (2.1.6).
Заміною змінних і рівняння (2.1.6) можна звести до вигляду
,
(2.1.7)
тобто коефіцієнти і можна вважати рівними 1.
Розв’язки залежать від
зміни знаків функції . Очевидно, що при і при (нас цікавить випадок ).
Отже, дане рівняння має
два положення рівноваги: і , причому перше з них є нестійким, а друге – асимптотично
стійким, усі розв’язки при наближуються до нього. Поведінку інтегральних
кривих зображено на рис. 2.1.1.
Рис. 2.1.1
Отже,
у логістичній моделі всі розв’язки з часом прямують до рівноважного стану, і
ніякого перенаселення, як стверджував Мальтус, бути не може.
Наступною ланкою в ієрархічному
ланцюзі є перехід до моделі багатовидової популяції. Розглянемо таку модель, а
також укажемо на задачі, пов’язані з нею. Розв’язання таких задач може стати
темою подальших наукових досліджень і кваліфікаційних робіт різного рівня.
Нехай – кількість
особин і-го виду . Математичною моделлю їх співіснування
є узагальнення моделі Лотки – Вольтерра на рівнянь
,
(2.1.14)
де – коефіцієнти системи.
Аналогічно можна
переконатися, що перший квадрант є фазовим простором даної системи. При її
дослідженні (навіть у випадку сталих коефіцієнтів) виникає низка серйозних
математичних проблем, відповідь на які потрібно отримати в термінах
коефіцієнтів системи, тобто функцій і :
1. Дослідити умови конкурентного
зникнення одного чи кількох видів, тобто умови, за яких при для деяких .
2. Знайти умови обмеженості числа особин
певного виду, тобто щоб для деяких .
3. Знайти умови періодичності зміни числа
особин
4. Дослідити умови перманентності системи
(2.1.14).
Останнє означає існування в першому
квадранті деякої компактної множини , що має таку властивість: усі розв’язки системи
(2.1.14), починаючи з деякого моменту часу (для кожного розв’язку – свого),
лежать у даній множині.
З погляду біологічних популяцій, умови
перманентності означають умови “мирного” співіснування всіх видів, коли жоден з
видів не зникає.
Узагальненням моделі (2.1.14) є
модель, що враховує вплив зовнішніх факторів на розвиток популяції. Це може
бути, наприклад, відловлення риби, збирання врожаю, запускання у водойму
мальків. Проміжки часу, протягом яких відбувається зовнішній вплив, є малими
порівняно з часом розвитку популяції, тому можна вважати, що такі впливи є
миттєвими. Останнє приводить до математичних моделей, що є диференціальними
рівняннями з імпульсною дією. Нехай – моменти зовнішніх впливів. Тоді, якщо , то популяції еволюціонує за законом, що описується
системою (2.1.14), а в моменти відбувається стрибок розв’язку. У математичній
формі це записується у вигляді
,
(2.1.15)
.
Функції характеризують величини зовнішніх впливів. Тобто
розв’язками систем з імпульсною дією є кусково-розривні функції, на відміну від
розв’язків звичайних диференціальних рівнянь, що значно ускладнює їх вивчення.
Систематичне дослідження таких рівнянь було започатковано одночасно в
Київському університеті імені Тараса Шевченка та Інституті математики НАН
України й отримало подальший розвиток у роботах викладачів Київського
університету.
Для імпульсних
моделей можна ставити всі задачі, анонсовані в п. 1.2.5, а також
порівнювати результати для ізольованих біологічних популяцій і популяцій, що
зазнають впливу ззовні. Їх поведінка є зовсім різною. Наприклад, у популяції
без зовнішнього впливу деякі види можуть зникати, а за рахунок зовнішньої
корекції – відновлюватися. Усі проблеми, перелічені в п. 1.2.5, є досить
цікавими й доволі складними математичними задачами для систем з імпульсами,
розв’язання яких вимагає практика. На сьогодні ці проблеми розв’язані лише в
деяких частинних випадках.
У всіх розглянутих вище моделях
популяцій швидкість зміни їх чисельності залежить лише від їх кількості на
даний момент. Однак швидкість залежить і від попередньої чисельності популяцій
(особливо, якщо мова йде про людське суспільство, де суттєвим є людський
фактор). Якщо врахувати таку залежність, то отримаємо математичну модель
біологічної популяції, що є системою диференціальних рівнянь з післядією:
, (2.1.16)
де функції характеризують запізнення. Порівняно з попередніми
моделями, ця система є значно складнішим математичним об’єктом. Наприклад,
множина розв’язків розглянутих вище рівнянь утворює скінченновимірний простір,
розв’язки ж системи (2.1.16) – нескінченно вимірний. Теорія таких рівнянь знаходиться
лише на початковій стадії розвитку. Для отримання більш-менш змістовних
результатів у цьому напрямі потрібно залучати найсучасніші математичні методи.
Однак мета виправдовує засоби. За допомогою даних рівнянь можна пояснити деякі
ефекти, які не підлягають математичному дослідженню без урахування післядії.
Наприклад, урахування часу – запізнення в логістичній
моделі – приведе до рівняння
,
де за певних співвідношень між та удається
встановити існування стійкого періодичного режиму коливань чисельності виду, на
відміну від звичайної логістичної моделі. Такі коливання дійсно спостерігаються
в деяких випадках і не можуть бути пояснені, виходячи з простої логістичної
моделі.
Урахування запізнення в ланцюгу
оберненого зв’язку математичної моделі локатора (відоме рівняння Мінорського)
дозволило виявити стійкі коливання у -контурі на частоті, що дуже відрізняється від частоти
контуру. Цей ефект було виявлено експериментально, але він не мав математичного
пояснення, оскільки відповідні математичні моделі мали дуже малий степінь
адекватності оригіналу. Введення запізнення в математичну модель процесу
обробки деталі на токарному станку дозволило пояснити появу небажаних вібрацій
різця. Ефект “галопування”, що спостерігався багатьма дослідниками під час руху
літака ґрунтівкою, став очевидним, як тільки в лінійному рівнянні руху було
враховане запізнення, викликане часом проходження літаком відстані між
передніми й задніми колесами шасі. Урахування післядії бажано й у інших
математичних моделях. Воно дозволить не тільки пояснити явища, експериментально
виявлені раніше, але й передбачити нові ефекти. Якщо подібні роботи з’являються
в інженерних журналах і монографіях порівняно рідко, то це, скоріше за все,
викликано або складністю, або навіть повною відсутністю потрібного
математичного апарату. Таким чином, моделі біологічних популяцій з урахуванням
запізнення є наступною ланкою в побудові ієрархічного ланцюга.
Перейдемо до ще
однієї ланки. Усі вказані вище моделі апріорі будувалися на тому, що кількість
особин усіх видів у просторі розміщується однорідно. Якщо врахувати залежність
кількості особин не тільки від часу, а й від розташування в просторі, то
прийдемо до моделей біологічних популяцій з дифузією, що математично
зображуються системою параболічних рівнянь у частинних похідних. Для
одновидової популяції, де – кількість
особин у момент у точці , отримаємо
рівняння
Таким рівнянням описується, наприклад,
динаміка скупчення амеб. На сьогодні добре вивчена лише двовидова популяція з
урахуванням дифузії.
Останньою, найвищою ланкою в
ієрархічному ланцюзі є моделі, що враховують випадковий вплив на динаміку
чисельності популяції. Усі впливи на популяцію носять випадковий характер і
коефіцієнти і – випадкові процеси. У детермінованих моделях ці
коефіцієнти є деякими усередненими характеристиками випадкових процесів.
Останнє означає, що детерміновані
моделі дуже мало враховують випадковий характер впливу. Якщо його прийняти до
уваги, то прийдемо до математичних моделей, що є диференціальними рівняннями з
випадковими збуреннями. Аналіз таких рівнянь не менш складний, ніж рівнянь із
запізненням. При їх дослідженні, окрім методів звичайних диференціальних
рівнянь, використовуються методи теорії випадкових процесів. Отримані при цьому
результати можуть якісно відрізнятися від аналогічних результатів
детермінованого випадку. Так, наприклад, у логістичній моделі з урахуванням
випадковостей можуть бути нестійкими обидва положення рівноваги або стійким
нульове, а друге – нестійким, на відміну від звичайної логістичної моделі.
На завершення розгляду даних моделей
наведемо схематично ієрархічний ланцюжок як приклад побудови ієрархій у
математичному моделюванні (рис. 2.1.5).
Имитационныекомпьютерныемодели
включаютпредставления
о компонентах систем и ихвзаимосвязяхкак в
видесобственноматематическихобъектов: формул, уравнений, матриц, логических
процедур, так и в видеграфиков, таблиц, баз данных,
оперативнойинформацииэкологическогомониторинга. Такие
многомерныемоделипозволяютобъединитьразнороднуюинформацию об
экологическойилиэколого-экономическойсистеме, "проигрывать"
различныесценарииразвития и вырабатывать на
моделиоптимальныестратегииуправления, чтоневозможноделать на реальнойсистеме в
силу ееуникальности и ограниченностивремени.
Имитационныйподход, такжекак и моделированиеэкосистем с помощьюфункцийотклик, требуютвысокоразвитойвычислительнойтехники, поэтомуматематическаяэкологиякакразвитая и практическииспользуемая наука получила распространениетолько в последниедесятилетия 20 века. Широкое применениематематическогоаппаратастимулировалоразвитиетеоретическойэкологии. Построениематематической моделей требуетупорядочивания и классификацииимеющейсяинформации об экосистемах, приводит к необходимостипланировать систему сбораданных и позволяетобъединить на содержательномуровнесовокупностьфизических, химических и биологическихсведений и представлений об отдельныхпроисходящих в экосистемахпроцессах.
Имитационныйподход, такжекак и моделированиеэкосистем с помощьюфункцийотклик, требуютвысокоразвитойвычислительнойтехники, поэтомуматематическаяэкологиякакразвитая и практическииспользуемая наука получила распространениетолько в последниедесятилетия 20 века. Широкое применениематематическогоаппаратастимулировалоразвитиетеоретическойэкологии. Построениематематической моделей требуетупорядочивания и классификацииимеющейсяинформации об экосистемах, приводит к необходимостипланировать систему сбораданных и позволяетобъединить на содержательномуровнесовокупностьфизических, химических и биологическихсведений и представлений об отдельныхпроисходящих в экосистемахпроцессах.
Інтуїтивне поняття алгоритму -
одне з основних понять математики, не допускає визначення у термінах більш простих
понять.
Нехай задано безліч завдань і
зазначено, що розуміється під рішенням кожної з них. Кажуть,
що існує алгоритм для вирішення даного нескінченної кількості завдань, якщо
існує єдиний спосіб, що дозволяє, для будь-якої задачі цієї множини, в кінцеве
число кроків, знайти її рішення.
Це не є визначенням, тому що вираз
«єдиний», «кінцеве число кроків» позбавлені математичної точності.
Риси, характерні для
інтуїтивного поняття алгоритму
1. Дискретність. Ця
властивість полягає в наступному: в початковий момент задається вихідна система
величин, а в кожен наступний момент система величин виходить з попередньої
системи величин за певним законом (програмі).
2. Детермінованість. Система
величин, одержуваних в будь-який, відмінний від початкового, момент часу,
однозначно визначається системою величин в попередні моменти часу.
3. Елементарність
кроків. Закон
отримання подальшої системи величин з попередньої повинен бути простим і
локальним.
4. Ефективність
(результативність). Кожен
крок роботи алгоритму повинен закінчуватися результатом.
5. Масовість
алгоритму. Початкова
система величин може вибиратися з деякого нескінченного рахункового безлічі Х.
6. Конструктивність. Об'єкти
з Х, над яким працює алгоритм, повинні бути конструктивними.
Конструктивний об'єкт -
той, який може бути набраний весь цілком і представлений для розгляду.
Прикладами конструктивних об'єктів
є булеві функції, формули алгебри логіки, натуральні та раціональні числа,
матриці з натуральними або раціональними елементами, многочлени від невідомих з
раціональними коефіцієнтами.
Неконструктивними
об'єктами є,
наприклад, будь-які дійсні числа, подання яких в десяткового запису a0 a 1 ...
a n ...
ні для якого nіз натуральних чисел не може бути цілком представлено для
розгляду. Числа
і не є конструктивними об'єктами.
Зрозуміло, що поняття алгоритму, що
описується властивостями 1-6, є нестрогим: у формулюванні цих властивостей
зустрічаються слова, які не мають точного математичного визначення. Необхідно
також зазначити, що, взагалі кажучи, не передбачається, що процес застосування
алгоритму до вихідних даних обов'язково повинен закінчитися результатом через
кінцеве число кроків. Процес
може закінчитися безрезультатно або не закінчитися взагалі. В
цьому випадку говорять, що алгоритм застосуємо до досліджуваних вихідними
даними.
Приклади алгоритмів:
§ Алгоритми
арифметичних дій з числами в двійковій системі числення
§ алгоритм
знаходження НОД 2-х цілих чисел, 2-х многочленів від змінної х;
§ алгоритм
вилучення? n,? n? N;
§ алгоритм
диференціювання многочлена від змінної;
§ алгоритм
знаходження визначника квадратної матриці А над?;
Аж до 30-х років двадцятого
століття поняття алгоритму залишалося інтуїтивно зрозумілим, що мав швидше
методологічне, а не математичне значення. Так,
до початку ХХ ст. багато
яскравих прикладів дала алгебра і теорія чисел. Серед
них згадаємо алгоритм Евкліда знаходження найбільшого загального дільника двох
натуральних чисел або двох цілочисельних многочленів, алгоритм Гаусса рішення
системи лінійних рівнянь над полем, алгоритм знаходження раціональних коренів
многочленів одного змінного з раціональними коефіцієнтами, алгоритм Штурма
визначення числа дійсних коренів многочлена з дійсними коефіцієнтами на деякому
відрізку дійсних чисел, алгоритм розкладання многочлена одного змінного над
кінцевим полем на Непріводімие множники. Зазначені
алгоритмічні проблеми вирішені шляхом зазначення конкретних дозвільних
процедур. Для
отримання результатів такого типу досить інтуїтивного поняття алгоритму.
Але тоді ж були висунуті
алгоритмічні проблеми, для яких не вдавалося побудувати алгоритм, та й саме
існування таких алгоритмів було під сумнівом.
Приклади:
§ 10-я
проблема Гільберта про можливості розв'язання довільного диофантово рівняння;
§ Проблема
визначення общезначимости довільної формули логіки предикатів.
Зазначені проблеми були вирішені
негативно, тобто доведено,
що не існує алгоритму для їх вирішення (відповідно Ю. Матіясевіч (1970 р.) і А.
Черч (1936г.)).
Для доказу неіснування алгоритму,
інтуїтивного поняття алгоритму недостатньо. Воно
повинно бути уточнено і формалізовано. З
цією метою побудовано кілька формальних
алгоритмічних моделей, що представляють
алгоритм як:
1. обчислення
функції натурального аргументу (частково-рекурсивні функції);
2. роботу
деякої абстрактної машини (машини Тьюринга, машина з необмеженими регістрами);
3. послідовні
перетворення слів, записаних в довільному алфавіті (нормальні алгоритми
Маркова).
Для теорії складності обчислень,
вибір моделі, в якій конструюються алгоритми, не має принципового значення. Існують
способи реалізації одних алгоритмічних моделей за допомогою інших. При
цьому зберігається приналежність алгоритмів певного класу складності (P, N і
ін.)
Алгоритм, записаний у вигляді
програми на мові програмування високого рівня, також може бути змодельований за
допомогою однієї із згаданих формальних моделей.
Уточнення поняття алгоритму за його властивостями
Поняття «алгоритм» можна уточнити, вказавши перелік властивостей, які
характерні для алгоритмів. До них відносяться:
1. Дискретність алгоритму означає, що алгоритм розділений на окремі кроки (дії), причому, виконання чергового кроку можливо тільки після завершення всіх операцій на попередньому кроці. При цьому набір проміжних даних кінцевий і він виходить за певними правилами з даних попереднього кроку.
2. Детермінованість алгоритму полягає в тому, що сукупність проміжних величин та будь-якому кроці однозначно визначається системою величин, що були на попередньому кроці.Дана властивість означає, що результат виконання алгоритму не залежить від того, хто (або що) його виконує (тобто від виконавця алгоритму), а визначається тільки вхідними даними і кроками (послідовністю дій) самого алгоритму.
3. Елементарність кроків: закон отримання подальшої системи величин з попередньої повинен бути простим і локальним. Який крок (дія) можна вважати елементарним, визначається особливостями виконавця алгоритму.
4. Спрямованість алгоритму: якщо спосіб отримання наступних величин з будь-яких вихідних не призводить до результату, то повинно бути вказано, що слід вважати результатом алгоритму.
5. Масовість алгоритму: початкова система величин може вибиратися з деякого безлічі.
1. Дискретність алгоритму означає, що алгоритм розділений на окремі кроки (дії), причому, виконання чергового кроку можливо тільки після завершення всіх операцій на попередньому кроці. При цьому набір проміжних даних кінцевий і він виходить за певними правилами з даних попереднього кроку.
2. Детермінованість алгоритму полягає в тому, що сукупність проміжних величин та будь-якому кроці однозначно визначається системою величин, що були на попередньому кроці.Дана властивість означає, що результат виконання алгоритму не залежить від того, хто (або що) його виконує (тобто від виконавця алгоритму), а визначається тільки вхідними даними і кроками (послідовністю дій) самого алгоритму.
3. Елементарність кроків: закон отримання подальшої системи величин з попередньої повинен бути простим і локальним. Який крок (дія) можна вважати елементарним, визначається особливостями виконавця алгоритму.
4. Спрямованість алгоритму: якщо спосіб отримання наступних величин з будь-яких вихідних не призводить до результату, то повинно бути вказано, що слід вважати результатом алгоритму.
5. Масовість алгоритму: початкова система величин може вибиратися з деякого безлічі.
Остання властивість означає, що один алгоритм, тобто одна
і та ж послідовність дій, в загальному випадку, може застосовуватися для
вирішення деякого класу (тобто багатьох) завдань.Для практики і, зокрема,
рішення задачі на комп'ютері, це властивість істотно, оскільки, як правило,
призначена для користувача цінність програми виявляється тим вище, чим більший
коло однотипних завдань вона дозволяє вирішити. Однак
для побудови алгоритмічної теорії це властивість не є істотним і обов'язковим. Поняття
алгоритму, в якійсь мірі визначається перерахуванням властивостей 1 - 5, також
не можна вважати суворим, оскільки у формулюваннях властивостей використані
терміни «величина», «спосіб», «простий», «локальний» та інші, точний зміст яких
не встановлено. Дане
визначення буде називатися нестрогим (іноді його називають інтуїтивним)
поняттям алгоритму. [4]
Алгоритмічна розв'язність
Матеріал з Вікіпедії - вільної енциклопедії
Поточна
версія сторінки поки не
перевірялася досвідченими учасниками
і може значно відрізнятися від версії ,
перевіреної 7 липня 2011; перевірки вимагає 1
правка .
У математичній логіці та теорії алгоритмів під розв'язність увазі
властивість формальної теорії володіти алгоритмом ,
визначальним по даній формулі ,
виведена вона з безлічі аксіомданої
теорії чи ні. Теорія називається розв'язною, якщо
такий алгоритм існує, і нерозв'язною, в
іншому випадку. Питання про виводимості
у формальній теорії є приватним, але разом з тим, найважливішим випадком більш
загальної проблеми розв'язання .
|
Зміст
|
Поняття алгоритму та
аксіоматичної системи мають давню історію. І те
й інше відоме ще з часів античності . Досить
згадати постулати геометрії Евкліда і алгоритм знаходження найбільшого загального
дільника того ж Евкліда. Незважаючи
на це, чіткого математичного визначення обчислення та особливо алгоритму не
існувало дуже довгий час. Особливість
проблеми, пов'язаної з формальним визначенням нерозв'язності полягала в тому,
що для того, щоб показати, що деякий алгоритм існує, достатньо його просто
знайти і продемонструвати. Якщо
ж алгоритм не знаходиться, можливо його не існує і це тоді потрібно строго
довести. А для цього потрібно
точно знати, що таке алгоритм.
Великий прогрес у
формалізації цих понять було досягнуто на початку XX століття Гільбертом і
його школою. Тоді, спочатку,
сформувалися поняття обчислення і формального виводу, а потім Гільбертом ж, в
його знаменитій програмі обгрунтування
математики була поставлена
амбітна мета формалізації всієї математики. Це
передбачало, в тому числі, можливість автоматичної перевірки будь-якої
математичної формули на предмет істинності. Відштовхуючись
від робіт Гільберта Гедель вперше
описав клас так званих рекурсивних функцій , за
допомогою якої довів свої знамениті теореми про неповноту . Згодом
був введений ряд інших формалізмів, таких як машина Тьюринга , λ-числення , що
опинилися еквівалентними рекурсивним функціям. В
даний час, кожен з них вважається формальним еквівалентом інтуїтивного поняття
обчислюваною функції. Ця еквівалентність
постулюється тезою Черча .
Коли поняття обчислення
і алгоритму були уточнені, пішов ряд результатів про нерозв'язності різних
теорій. Одним з перших таких
результатів була теорема, доведена Новіковим , про
нерозв'язності проблеми слів в групах . Розв'язні
ж теорії були відомі задовго до цього.
Інтуїтивно зрозуміло,
що чим складніше і виразно теорія, тим більше шансів, що вона виявиться
нерозв'язною. Тому, грубо кажучи,
«нерозв'язна теорія» - синонім до «складна теорія».
Формальне обчислення в
загальному випадку має визначати мову ,
правила побудови термів і формул ,
аксіоми і правила виводу. Таким
чином, для кожної теореми T, завжди
можна побудувати ланцюжок A 1, A 2, ..., A n = T, де
кожна формула A i або є
аксіомою, або виводиться з попередніх формул, по одному з правил виводу. Розв'язність
означає, що існує алгоритм, який для кожного правильно побудованого пропозиції T, за
кінцевий час видає однозначну відповідь: так, ця пропозиція виводиться в рамках
обчислення чи ні - воно не виводиться.
Очевидно, що
суперечлива теорія розв'язна, так як будь-яка формула буде виведеної. З
іншого боку, якщо обчислення не володіє рекурсивно перечислимого
безліччю аксіом, як наприклад, логіка другого порядку ,
воно, очевидно, не може бути розв'язаним.
|
Згідно з задумом
одного з учасників Вікіпедії, на цьому місці повинен розташовуватися спеціальний розділ.
Ви можете допомогти проекту, написавши цей розділ. |
|
Згідно з задумом
одного з учасників Вікіпедії, на цьому місці повинен розташовуватися спеціальний розділ.
Ви можете допомогти проекту, написавши цей розділ. |
Розв'язність - дуже
сильне властивість, і більшість корисних і використовуються на практиці теорій
їм не володіють. У зв'язку з цим було
введено більш слабке поняттяполуразрешімості. Полуразрешімость
означає наявність алгоритму, який за кінцевий час завжди підтвердить, що
пропозиція істинно, якщо це дійсно так, але якщо ні - може працювати
нескінченно.
Вимога полуразрешімості
еквівалентно можливості ефективно перерахувати всі теореми даної теорії. Іншими
словами, безліч теорем повинно бути рекурсивно-перечислимого .Більшість
використовуваних на практиці теорій задовольняють цій вимозі.
Велике практичне
значення мають ефективні полуразрешающіе процедури длялогіки першого порядку,
так як вони дозволяють (напів) автоматично доводити
формалізовані затвердження дуже широкого класу. Проривом
в цій області було відкриття Робінсоном в 1965 методу резолюцій . Іншим
найважливішим полуразрешающім алгоритмом на сьогоднішній день є табло-метод .
У математичній логіці ,
традиційно використовується два поняття повноти: власне повнота і повнота, щодо
деякого класу інтерпретацій (або структур). У
першому випадку, теорія повна, якщо будь-яка пропозиція в ній є або істинним,
або хибним. У другому - якщо
будь-яка пропозиція, істинне при всіх інтерпретаціях з даного класу виводиться. Наприклад, натуральна арифметика неповна,
згідно теоремам Геделя про неповноту , але
вона сповнена щодо своєї стандартної інтерпретації - це випливає з теореми Геделя про
повноту .
Обидва поняття тісно
пов'язані з розв'язність. Наприклад,
якщо безліч аксіом повної теорії першого порядку рекурсивно перечислимого, то
вона вирішувана. Це випливає з відомоїтеореми Посту , яка
стверджує, що якщо безліч і його доповнення обидва рекурсивно перечислимого то
вони також рекурсивно . Інтуїтивно,
аргумент, що показує істинність наведеного твердження наступний: якщо теорія
повна, і безліч її аксіом рекурсивно перечислимого, то існують полуразрешающіе
процедури, для перевірки істинності будь-якого затвердження, так само як і його
заперечення. Якщо запустити обидві
ці процедури паралельно , то
враховуючи повноту теорії, одна з них повинна коли-небудь зупинитися і видати
позитивну відповідь.
Якщо теорія повна, щодо
деякого класу інтерпретацій, це можна використовувати для побудови роздільної
процедури. Наприклад пропозіціональная логіка сповнена
щодо інтерпретації на таблицях істинності . Тому
побудова таблиці істинності по даній формулі буде прикладом дозволяє алгоритму
для пропозіціональной логіки.
Алгоритм вирішення
проблеми.
Вам дано 4 схеми-алгоритму вирішення проблеми, але тільки одна з них правильна.
Проаналізуйте алгоритми і виберіть той, який ви вважаєте правильний. Чому саме цей варіант ви вибрали?
Що нового з даного алгоритму ви взяли для себе на озброєння?
Відповідь аргументуйте на форумі.
Варіант 1.
1. Діагностика проблеми і ситуації, в якій її належить вирішити: характеристика ситуації на основі зібраної інформації, визначення причин виникнення проблемної ситуації, формулювання проблеми, формулювання мети подальших дій.
2.Обнаруженіе проблеми.
3. Збір інформації про ситуацію.
4. Аналіз інформації про ситуацію.
5. Реалізація рішення, призначення відповідальних.
6. Формування множини альтернатив вирішення проблеми.
7. Оцінка альтернатив, прогнозування наслідків кожного з них.
8. Прийняття рішень.
9. Розробка критеріїв для оцінки ступеня досягнення поставленої мети. Тут мається на увазі, як дізнаюся, що проблема вирішена? В якості критерію може виступати позитивна динаміка розвитку дитини або зростання якості успішності і т.д.
10. Контроль дотримання, оцінка ефективності та узагальнення досвіду.
Варіант 2.
1. Аналіз інформації про ситуацію.
2. Збір інформації про ситуацію.
3. Виявлення проблеми.
4. Діагностика проблеми і ситуації, в якій її належить вирішити: характеристика ситуації на основі зібраної інформації, визначення причин виникнення проблемної ситуації, формулювання проблеми, формулювання мети подальших дій.
5. Формування множини альтернатив вирішення проблеми.
5. Оцінка альтернатив, прогнозування наслідків кожного з них.
7. Прийняття рішень.
8. Реалізація рішення, призначення відповідальних.
9. Контроль дотримання, оцінка ефективності та узагальнення досвіду.
Варіант 3.
1. Виявлення проблеми.
2. Збір інформації про ситуацію.
3. Аналіз інформації про ситуацію.
4. Діагностика проблеми і ситуації, в якій її належить вирішити: характеристика ситуації на основі зібраної інформації, визначення причин виникнення проблемної ситуації, формулювання проблеми, формулювання мети подальших дій.
5. Розробка критеріїв для оцінки ступеня досягнення поставленої мети. Тут мається на увазі, як дізнаюся, що проблема вирішена? В якості критерію може виступати позитивна динаміка розвитку дитини або зростання якості успішності і т.д.
6. Формування множини альтернатив вирішення проблеми.
7. Оцінка альтернатив, прогнозування наслідків кожного з них.
10. Контроль дотримання рішень, оцінка ефективності та узагальнення досвіду.
Варіант 4.
1. Виявлення проблеми.
2. Формування множини альтернатив вирішення проблеми.
3.Cбор інформації про ситуацію.
4. Аналіз інформації про ситуацію.
5. Діагностика проблеми і ситуації, в якій її належить вирішити: характеристика ситуації на основі зібраної інформації, визначення причин виникнення проблемної ситуації, формулювання проблеми, формулювання мети подальших дій.
6. Розробка критеріїв для оцінки ступеня досягнення поставленої мети. Тут мається на увазі, як дізнаюся, що проблема вирішена? В якості критерію може виступати позитивна динаміка розвитку дитини або зростання якості успішності і т.д.
7. Оцінка альтернатив, прогнозування наслідків кожного з них. (Яке з рішень найбільш безпечно і найбільш ефективно приведе до досягнення цілей)
8. Прийняття рішень.
9. Реалізація рішення, призначення відповідальних.
10. Контроль дотримання, оцінка ефективності та узагальнення досвіду.
Вам дано 4 схеми-алгоритму вирішення проблеми, але тільки одна з них правильна.
Проаналізуйте алгоритми і виберіть той, який ви вважаєте правильний. Чому саме цей варіант ви вибрали?
Що нового з даного алгоритму ви взяли для себе на озброєння?
Відповідь аргументуйте на форумі.
Варіант 1.
1. Діагностика проблеми і ситуації, в якій її належить вирішити: характеристика ситуації на основі зібраної інформації, визначення причин виникнення проблемної ситуації, формулювання проблеми, формулювання мети подальших дій.
2.Обнаруженіе проблеми.
3. Збір інформації про ситуацію.
4. Аналіз інформації про ситуацію.
5. Реалізація рішення, призначення відповідальних.
6. Формування множини альтернатив вирішення проблеми.
7. Оцінка альтернатив, прогнозування наслідків кожного з них.
8. Прийняття рішень.
9. Розробка критеріїв для оцінки ступеня досягнення поставленої мети. Тут мається на увазі, як дізнаюся, що проблема вирішена? В якості критерію може виступати позитивна динаміка розвитку дитини або зростання якості успішності і т.д.
10. Контроль дотримання, оцінка ефективності та узагальнення досвіду.
Варіант 2.
1. Аналіз інформації про ситуацію.
2. Збір інформації про ситуацію.
3. Виявлення проблеми.
4. Діагностика проблеми і ситуації, в якій її належить вирішити: характеристика ситуації на основі зібраної інформації, визначення причин виникнення проблемної ситуації, формулювання проблеми, формулювання мети подальших дій.
5. Формування множини альтернатив вирішення проблеми.
5. Оцінка альтернатив, прогнозування наслідків кожного з них.
7. Прийняття рішень.
8. Реалізація рішення, призначення відповідальних.
9. Контроль дотримання, оцінка ефективності та узагальнення досвіду.
Варіант 3.
1. Виявлення проблеми.
2. Збір інформації про ситуацію.
3. Аналіз інформації про ситуацію.
4. Діагностика проблеми і ситуації, в якій її належить вирішити: характеристика ситуації на основі зібраної інформації, визначення причин виникнення проблемної ситуації, формулювання проблеми, формулювання мети подальших дій.
5. Розробка критеріїв для оцінки ступеня досягнення поставленої мети. Тут мається на увазі, як дізнаюся, що проблема вирішена? В якості критерію може виступати позитивна динаміка розвитку дитини або зростання якості успішності і т.д.
6. Формування множини альтернатив вирішення проблеми.
7. Оцінка альтернатив, прогнозування наслідків кожного з них.
10. Контроль дотримання рішень, оцінка ефективності та узагальнення досвіду.
Варіант 4.
1. Виявлення проблеми.
2. Формування множини альтернатив вирішення проблеми.
3.Cбор інформації про ситуацію.
4. Аналіз інформації про ситуацію.
5. Діагностика проблеми і ситуації, в якій її належить вирішити: характеристика ситуації на основі зібраної інформації, визначення причин виникнення проблемної ситуації, формулювання проблеми, формулювання мети подальших дій.
6. Розробка критеріїв для оцінки ступеня досягнення поставленої мети. Тут мається на увазі, як дізнаюся, що проблема вирішена? В якості критерію може виступати позитивна динаміка розвитку дитини або зростання якості успішності і т.д.
7. Оцінка альтернатив, прогнозування наслідків кожного з них. (Яке з рішень найбільш безпечно і найбільш ефективно приведе до досягнення цілей)
8. Прийняття рішень.
9. Реалізація рішення, призначення відповідальних.
10. Контроль дотримання, оцінка ефективності та узагальнення досвіду.
Стійка сортування
Матеріал з Вікіпедії - вільної енциклопедії
Поточна
версія сторінки поки не
перевірялася досвідченими учасниками
і може значно відрізнятися від версії ,
перевіреної 2 липня 2011; перевірки вимагають 13
правок .
Стійка (стабільна)
сортування - сортування, яка не
змінює відносний порядок сортованих елементів, що мають однакові ключі. Більшість
простих методів сортування стійкі, більшість складних - ні.
Стійкість є дуже
важливою характеристикою алгоритму сортування, але, тим не менш, вона практично
завжди може бути досягнута шляхом подовження вихідних ключів за рахунок
додаткової інформації про їх первісному порядку. Незважаючи
на гадану необхідність, що випливає з назви, стабільність зовсім не обов'язкова
для правильності сортування і найчастіше не дотримується, так як для її
забезпечення практично завжди необхідні додаткова пам'ять і час.
|
Зміст
|
Нижче наводяться описи
алгоритмів стійкою сортування з часом роботи не гірше O (n log 2 n) (крім
найгірших випадків в алгоритмі з використанням стійкого поділу). У
всіх псевдокоду пара косих / / означає коментар до кінця рядка як у мові C + +.
При цьому алгоритмі
сортування спочатку здійснюється рекурсивне поділ вихідного масиву на частини
до тих пір, поки в кожній частині масиву не виявиться один або нуль елементів
(на кожному кроці рекурсії здійснюється поділ навпіл). Після
цього отримані частини попарно «зливаються». Загальна
складність алгоритму - O (n log n), при
цьому алгоритму потрібно O(n) додаткової
пам'яті для зберігання злитих масивів.
Даний алгоритм схожий
на алгоритм швидкого сортування . Так
само як і в алгоритмі швидкого сортування, в даному алгоритмі вихідний масив
поділяється на дві частини - в одній всі елементи менше або дорівнюють деякого
опорного елементу, а в іншій - більше або рівні. Після
цього розділені частини масиву рекурсивно сортуються таким же чином. Відмінність
цього алгоритму від алгоритму швидкого сортування в тому, що тут
використовується сталий поділ замість нестійкого. Нижченаведенареалізаціяданогоалгоритмунапсевдокоді:
Sort(a[1..n]) if(n > 1) then N ← a[ 1
]; m ← StablePartition(a[1..n], N); Sort(a[1..m]); Sort(a[m+1..n]);
StablePartition(a[1..n], N) if( n > 1 ) then m ←
n/2
; m1 ← StablePartition(a[1..m], N);
m2 ← m+StablePartition(a[m+1..n], N); Rotate(a[m1..m2], m); return(m1 +
(m2-m)); else if(a[1] < N) then return(1); else return(0)
Процедура Rotate:
Rotate(a[1..n], m) if( n > m > 1 )
//вмассивехотябыдваэлементаисдвигимеетсмысл
shift ← mn; //числопозицийнакотороебудетосуществлятьсясдвиг
gcd ← GCD(m-1, n); //GCD - этонаибольшийобщийделитель
for i ← 0 to gcd-1 do head ← i+1; headVal ← a[head]; current ← head; next ←
head+shift; while(next
head)
do a[current] ← a[next]; current ← next; next ← next+shift; if(next>n) next
← next-n; a[current] ← headVal;
Rotate(a[1..n], m) if( n > m > 1 )
//вмассивехотябыдваэлементаисдвигимеетсмысл
shift ← mn; //числопозицийнакотороебудетосуществлятьсясдвиг
gcd ← GCD(m-1, n); //GCD - этонаибольшийобщийделитель
for i ← 0 to gcd-1 do head ← i+1; headVal ← a[head]; current ← head; next ←
head+shift; while(next
head) do a[current] ← a[next];
current ← next; next ← next+shift; if(next>n) next ← next-n; a[current] ←
headVal;
Для сталого поділу
масиву потрібно O (n log n) елементарних
операцій. Так як «глибина»
здійснюваного рекурсивного спуску в середньому випадку становить O (log n) то
загальна складність алгоритму становить O (n log ² n). При
цьому алгоритму для здійснення рекурсії буде потрібно O (log n) стекової пам'яті,
хоча в гіршому випадку загальна складність дорівнює O (n ² log n) і
потрібно O (n) пам'яті.
Всі описані нижче
алгоритми засновані на злитті вже відсортованих масивів без використання
додаткової пам'яті понад O (log ² n) стекової
пам'яті (це - т. зв. Умова мінімальної пам'яті [1]) і
відрізняються лише алгоритмом злиття. Далі
наведено псевдокод алгоритмів (алгоритми злиття - процедура Merge - наводяться
окремо для кожного методу):
Sort(a[1..n]) if( n > 1 ) then m← n/2 ;
Sort(a[1..m]); Sort(a[m+1..n]); Merge(a[1..n], m);
Sort(a[1..n]) if( n > 1 ) then m← n/2 ;
Sort(a[1..m]); Sort(a[m+1..n]); Merge(a[1..n], m);
В алгоритмі Пратта в
відсортованих масивах знаходять два елементи α і β, які є
медианами масиву, що складається з елементів обох масивів. Тоді
весь масив можна представити у вигляді aαbxβy. Після
цього здійснюється циклічний зсув елементів в результаті чого отримуємо таку
послідовність: axβαby. Далі
алгоритм злиття рекурсивно повторяться для масивів ax і by.
Merge(a[1..n], m) if(m <> 1 and m
<> n) //это условие означает, что в массиве должно быть хотя бы 2
элемента if( n-1 > 2 ) //случай, когда элементов ровно два, приходится
рассматривать отдельно if( m-1 > nm ) leftBound←1; rightBound←m; while(
leftBound < rightBound ) do //в этом цикле ищем медианы m1 ←
(leftBound+rightBound)/2; m2 ← FindFirstPosition(a[m..n], a[ m1 ]);
//реализация процедуры FindFirstPosition см. след.пункт if( m1 + (m2-m) >
n/2 ) then rightBound ← m1-1; else leftBound ← m1+1; Rotate(a[m1..m2], m);
Merge(a[1..m1+(m2-m)], m1); Merge(a[m1+(m2-m)+1..n], m2); else if(a[m] <
a[1]) a[m]
a[1];
Merge(a[1..n], m) if(m <> 1 and m
<> n) //это условие означает, что в массиве должно быть хотя бы 2
элемента if( n-1 > 2 ) //случай, когда элементов ровно два, приходится
рассматривать отдельно if( m-1 > nm ) leftBound←1; rightBound←m; while(
leftBound < rightBound ) do //в этом цикле ищем медианы m1 ←
(leftBound+rightBound)/2; m2 ← FindFirstPosition(a[m..n], a[ m1 ]);
//реализация процедуры FindFirstPosition см. след.пункт if( m1 + (m2-m) >
n/2 ) then rightBound ← m1-1; else leftBound ← m1+1; Rotate(a[m1..m2], m);
Merge(a[1..m1+(m2-m)], m1); Merge(a[m1+(m2-m)+1..n], m2); else if(a[m] <
a[1]) a[m]
a[1];
Циклічний зсув
елементів вимагає O (n) елементарних
операцій і O (1) додаткової пам'яті, а пошук медиан в двох вже відсортованих
масивах - O (log ² n) елементарних
операцій і O (1) додаткової пам'яті. Так
як здійснюється O (log n) кроків
рекурсії, то складність такого алгоритму злиття становить O (n log n), а
загальна складність алгоритму сортування - O (n log ² n).При
цьому алгоритму потрібно O (log ² n) стекової
пам'яті.
Від пошуку медиан в
попередньому алгоритмі можна позбутися в такий спосіб. В
більшому з двох масивів вибираємо середній елемент α (опорний елемент). Далі
в меншому масиві знаходимо позицію першого входження елемента більшого чи
рівного α. Назвемо його β. Після
цього здійснюється циклічний зсув елементів так само як і в алгоритмі Пратта (aαbxβy →axβαby) і
здійснюється рекурсивне злиття отриманих частин. Псевдокод
алгоритму злиття наведено нижче.
Merge(a[1..n], m) if(m <> 1 and m
<> n) //это условие означает что в массиве должно быть хотя бы 2 элемента
if( n-1 > 2 ) //случай когда элементов ровно два приходится рассматривать
отдельно if( m-1 > nm ) m1 < (m+1)/2 ; m2 < FindFirstPosition(a[m..n],
a[ m1 ]); else m2 < (n+m)/2 ; m1 < FindLastPosition(a[1..m], a[ m2 ]);
Rotate(a[m1..m2], m); Merge(a[1..m1+(m2-m)], m1); Merge(a[m1+(m2-m)+1..n], m2);
else if(a[ m ] < a[ 1 ]) a[ m ]
a[ 1 ];
Merge(a[1..n], m) if(m <> 1 and m
<> n) //это условие означает что в массиве должно быть хотя бы 2 элемента
if( n-1 > 2 ) //случай когда элементов ровно два приходится рассматривать
отдельно if( m-1 > nm ) m1 < (m+1)/2 ; m2 < FindFirstPosition(a[m..n],
a[ m1 ]); else m2 < (n+m)/2 ; m1 < FindLastPosition(a[1..m], a[ m2 ]);
Rotate(a[m1..m2], m); Merge(a[1..m1+(m2-m)], m1); Merge(a[m1+(m2-m)+1..n], m2);
else if(a[ m ] < a[ 1 ]) a[ m ]
a[ 1 ];
Процедури
FindFirstPosition і FindLastPosition практично збігаються з процедурою
двійкового пошуку:
FindFirstPosition(a[1..n], x) leftBound
< 1; rightBound < n; current < 1; while(leftBound < rightBound) do
current < [(leftBound+rightBound)/2]; if(a[ current ] < x) then leftBound
< current+1 else rightBound < current; return(current);
FindLastPosition(a[1..n], x) leftBound < 1; rightBound < n; current <
1; while(leftBound < rightBound) do current < [(leftBound+rightBound)/2];
if( x < a[ current ] ) then rightBound < current; else leftBound <
current+1 return(current);
FindFirstPosition(a[1..n], x) leftBound
< 1; rightBound < n; current < 1; while(leftBound < rightBound) do
current < [(leftBound+rightBound)/2]; if(a[ current ] < x) then leftBound
< current+1 else rightBound < current; return(current);
FindLastPosition(a[1..n], x) leftBound < 1; rightBound < n; current <
1; while(leftBound < rightBound) do current < [(leftBound+rightBound)/2];
if( x < a[ current ] ) then rightBound < current; else leftBound <
current+1 return(current);
Навідміну від алгоритму
Пратта в даному алгоритмі розбиття може бути істотно нерівним. Але
навіть у гіршому випадку алгоритм розіб'є весь діапазон [a .. y] в
співвідношенні 3:1 (якщо все елементи другого діапазону будуть більше або менше
опорного і при цьому обидва діапазону мають рівне число елементів). Це
гарантує логарифмічне число кроків рекурсії при злитті будь-яких масивів. Таким
чином отримуємо, що так само, як і в алгоритмі Пратта, складність алгоритму
злиття дорівнює O (n log n), складність
алгоритму сортування - O (n log ² n), а
необхідна пам'ять - O (log ² n).
§ У
всіх вищенаведених алгоритмах при розбитті вихідного масиву на частини
рекурсивне розбиття можна зупинити, якщо розмір разбиваемого масиву стане
досить маленьким. Тоді можна застосувати
будь-якої з простих алгоритмів сортування (наприклад, сортування вставками ),
які, як відомо, працюють швидше ніж складні, якщо розмір вхідного масиву
невеликий. Фактично даний прийом
можна застосувати не тільки для представлених тут алгоритмів, а й для
будь-якого іншого алгоритму, де застосовується рекурсивне розбиття вихідного
масиву (наприклад, звичайна нестабільна швидке сортування ). Конкретне
число вхідних елементів, при якому треба переходити на простий алгоритм сортування,
залежить від використовуваної обчислювальної машини.
§ В
алгоритмі Пратта, алгоритмі без пошуку медиан і алгоритмі з використанням
стійкого поділу замість того, щоб кожен раз рекурсивно викликати процедуру
злиття, можна динамічно виділити масив тимчасових змінних. Тоді
можна буде продовжувати розбиття діапазону лише до тих пір, поки число
елементів в більшому діапазоні не стане менше або дорівнює місткості
тимчасового масиву. Фактично на деякому
кроці рекурсії алгоритм Пратта і алгоритм без пошуку медиан перетворюються в
алгоритм простого злиття. Т. о. якщо
в системі досить динамічної пам'яті, то асимптотичну час роботи можна довести
до O (n log n) замість
O (n log ² n).
Немає коментарів:
Дописати коментар