Головна

Алгоритм і його властивості. Методи запису алгоритмів.

  1. Стандартний алгоритм симплекс-методу
  2. HSR: алгоритм сортування по глибині
  3. I.3.3. Методи виносу в натуру проектних точок.
  4. I.3.4. Методи підготовки даних для перенесення проекту на місцевість.
  5. IV. Багатовимірні статистичні методи
  6. L1-L2, L2-L1 закони. ART1 алгоритм.
  7. N Навчання різним формам записи

алгоритм - Це система формальних правил, однозначно призводить до вирішення поставленого завдання. У програмуванні, алгоритм - Це послідовність арифметичних і логічних дій над даними, що призводить до отримання рішення поставленого завдання.

властивості:

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

Визначеність - кожен крок алгоритму має бути строго сформульоване (мати точний сенс).

Зв'язаність - на кожному наступному кроці використовуються результати попереднього.

Кінцівка - алгоритм повинен завершуватися після кінцевого числа кроків.

Результативність - алгоритм повинен призводити до отримання кінцевих результатів.

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

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

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

Алгоритми записуються у вигляді:

словесних правил,

блок-схем,

програм.

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

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

Недоліки словесного засобу опису алгоритмів:

відсутність наочності,

недостатня точність.

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

У блок-схемі можна використовувати строго певні типи блоків:

1) початок / кінець 2) Обчислювальний дію 3) перевірка умови 4) Введення / висновок

 та ні

       
   


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

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

Алгоритм, записаний на мові програмування, називається програмою. Словесна і графічна форми запису алгоритму призначені для людини. Алгоритм, призначений для виконання на комп'ютері, записується на мові програмування (мовою, зрозумілою ЕОМ).


Булева алгебра і питання, пов'язані з її застосуванням

булева алгебра - Непорожня множина, для якого визначено три операції: дві бінарні операції, представлені знаками E, C і одна унарна операція, представлена ??рисою, яка ставить перед елементом безлічі (доповнення).

Елементи непорожньої безлічі (обозн. Чер. U) прийнято позначати буквами A, B, ... В результаті бінарних операцій з довільних елементів A і B з U виходять більш складні елементи: AEB і ACB, кіт. соотв.-но зв. об'єднанням и перетином A і B. За визначенням для кожного елемента A з мн. U однозначно представлений елемент -A, кіт. наз. доповненням до A. Для непорожньої безлічі U характерно наступне:

1) разом з елементами A і B в ньому містяться їх теоретико-множинне перетинання (C) і їх теоретико-множинне об'єднання (E);

2) якщо елемент A міститься в безлічі U, то в U міститься і теоретико-множинне доповнення до A, т. Е. Безліч всіх піделементи з U, кіт. не належать A. При цьому кожен елемент має тільки одне доповнення.

Система аксіом, запропонована Сікорським:

  1. закони коммутативности: A E B = B E A, A C B = B C A
  2. закони асоціативності: AE (BEС) = (AEB) EС, AC (BCС) = (ACB) CС
  3. закони поглинання: (ACB) EB = B, (AEB) CB = B
  4. закони дистрибутивности: AC (BEС) = (ACB) E (ACС), AE (BCС) = (AEB) C (AEС)
  5. (AC-A) EB = B, (AE-A) CB = B. З цих аксіом випливає, що AC-AI B і BI AE-A, де I - знак включення.

Елемент AC-A зв. нульовим елементом, або нулем бул. алгебри і позначу. U.

Елемент AE-A зв. одиничним елементом, або одиницею бул. алгебри і обозн. U.

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

У бул алгебри дійсні закони ідемпотентності, відповідно до кіт.

AEA = A, ACA = A.

Бул. алгебра зв. вироджених алгеброю, Якщо в ній є тільки один елемент. Необхідною і достатньою умовою вирожденність бул. алгебри счіт.-ся рав.-під U = U, т. е. збіг нуля і одиниці.

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

У булевої логіки дійсні закони де Моргана, відповідно до кіт.

- (A E B) = -A C -B, - (A C B) = -A E -B. З цих законів випливає, що A I B тоді і т. Т., Коли -B I -A, а також те, що AEB = - (-AC -B), ACB = - (-AE -B).

Коли для непорожньої подмн.-ва счіт.-ся виконаними слід. дві умови:

1) з того, що A, BID, слід, що AE BID,

2) з того, що BID і A I B, слід, що AID, то таке непорожнє мн.-під наз. ідеалом і позначу. гр. бук. D (дельта).

У тому випадку, коли для непорожньої подмн.-ва оказ.-ся виконаними слід. умови:

1) з A, B IN, слід, що A C BIN,

2) з B IN і A E B, слід, що AID, то таке непорожній. подмн.-під наз фільтром і обозн. переверне. гр. бук.N.Поняття фільтра двояко до поняття ідеалу.

Якщо непорожнє подмн.-під U0 бул. алгебри U замкнуто щодо операцій E, C, -, т. е. задовольняє слід. ум .:

1) якщо A, B I U0 , То A E BI U0

2) якщо A, B I U0, То A C BI U0

3) якщо A I U0, То - A I U0, То воно U0 наз. подалгебру алгебри U.

Відображення (обозн. Його h) алгебри U в алгебру U ? зв. гомоморфизмом, якщо воно зберігає операції об'єднання, пересеч.-я, взяття доповнення, т. е.

h (A EB) = h (A) E h (B), h (A CB) = h (A) C h (B), h (- A) = - h (A).

Взаємно однозначну гомоморфізм зв. изоморфизмом.

Бул. алгебра U наз. атомної, Якщо для кожного електромагнітного та A?U (AIU) існує атом а IA. Безатомною бул. алгебра зв. тоді, коли вона не містить жодного атома. Атомом бул. алгебри зв. електромагнітного т а?U, якщо для будь-якого AIU включення а IA означає, що або A = U, або A = а. Поняття атома явл. бул. аналогією одноточечного мн.-ва. Ізоморфізм h бул. алгебри U на себе зв. автоморфізмом.

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

визначення:

бінарна операція - Така операція мат. логіки, коли связ.-ся два висказив.-я в нове, більш складне висловлювання. (Й, диз'юнкція, імплікація, еквів.-ть)

унарна операція - Так. операція, в кіт. бере участь одна пропорційна зв'язка і один вислів. Такими операціями явл .: операція заперечення uA або 'A, операція необхідності yA, операція можливості aA.

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

? E М = М ? C М = ? ? \ М = ? М \ ? = М.

Непорожнє мн.-під - Таке мн.-во, кіт має хоча б один елемент. (Обозн. М).




Формула повної ймовірності. | Вектори в тривимірному просторі. Поняття правого ортонормированного базису. Скалярний, векторний та змішане твори.

Класичне визначення ймовірності Колмагорова | геометрична ймовірність | Види рівнянь площин і прямих у просторі. Умови їх паралельності і перпендикулярності. | Групи, кільця, поля (визначення і приклади) | Диф-ть ф-та однієї пров-й. | Диференціюється багатьох дійсних змінних. Екстремуми функцій багатьох дійсних змінних. | Діалоговий і пакетний режим роботи ЕОМ з користувачем. Принципи функціонування мультипрограмних ОС. | Елементарні функції комплексної змінної та їх властивості. | Інтеграл Рімана. | Інтерполяція функцій. Інтерпол. поліном Лагранжа |

© um.co.ua - учбові матеріали та реферати