12978

Математичний аналіз. Відповіді до екзамену

Конспект

Математика и математический анализ

Математичний аналіз Числова послідовність та її границя. Означення. Послідовність – це будьяка функція fn визначена на множині N натуральних чисел. Означення. Послідовність називають обмеженою якщо існують такі числа т і М що для всіх п викону

Украинкский

2013-05-07

4.31 MB

71 чел.

  1.  Математичний аналіз
    1.  Числова послідовність та її границя.

Означення. Послідовність – це будь-яка функція f(n), визначена на множині N натуральних чисел.

Означення. Послідовність  називають обмеженою, якщо існують такі числа т і М, що для всіх п виконується нерівність m<=<=M.

Означення. Число а називається границею числової послідовності , якщо для довільного як завгодно малого  числа  існує такий номер N, починаючи з якого для всіх n>N виконується нерівність .

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

Означення. Числова послідовність, у якої всі члени рівні між собою, називають сталою послідовністю або просто сталою.

Способи задання:

  •  Формула загального члена.
  •  Рекурентна формула.

Означення. Скінченою числовою послідовністю називають послідовність, що містить скінчену кількість членів.

  1.  Границя й неперервність функції в розумінні Коші та Гейне.

Означення. (Коші) Число а називається границею функції f(x) в точці , якщо для довільного як завгодно малого існує таке , що як тільки , то .

Означення. (Гейне) функція y=f(x) називається неперервною в точці , якщо для довільної послідовності , що має границею , відповідна їй послідовність являється збіжною і має границею число А.

Теорема. Означення за Коші та за Гейне є еквівалентними.

Доведення. Нехай існує границя функції за Коші. Доведемо, що тоді існує границя за Гейне. З того, що існує границя функції за Коші, слідує, що для довільного як завгодно малого  існує таке , що як тільки .

Розглянемо тепер довільну послідовність . Очевидно, що існує такий номер N, починаючи з якого буде виконуватися нерівність , але так як виконується означення Коші, то для членів цієї послідовності , а це означає, що послідовність збіжна і має границею число A.

Нехай тепер  - збіжна за Гейне, тобто для довільної послідовності , відповідна їй послідовність .

Доведемо, що справедливе в цьому випадку буде і означення неперервності за Коші.

Припустимо протилежне, тобто припустимо, що існує таке , що як тільки .

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

Отже, наше припущення було не вірне

.

  1.  Властивості неперервних функцій на відрізку.

Теорема. (Больцано-Коші) Якщо функція  неперервна на сегменті  і приймає на кінцях сегменту значення, які протилежні за знаком, то існує одна така точка с, яка належить сегменту , що .

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

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

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

Теорема. (Больцано-Коші) Якщо  - неперервна на сегменті  і принаймні на кінцях сегмента приймає різні значення А і В, то для довільного числа С, такого що , існує точка , така що .

Доведення. Для визначеності будемо вважати, що  і введемо для розгляду функції .

.

.

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

.

Теорема. (Веєрштрасса) Якщо функція  - неперервна на сегменті , то вона обмежена на цьому сегменті, тобто існують такі числа .

Доведення. Для визначеності доведемо, що  обмежена зверху. Будемо доводити методом від супротивного.

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

Теорема. (Веєрштрасса) Якщо функція  неперервна на сегменті , то вона досягає на цьому сегменті свого найменшого і найбільшого значення.

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

  1.  Диференційованість функції. Критерії диференційованості.

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

Доведення. Необхідність. Дано, що  - диференційована, тобто має похідну. Потрібно довести, що її приріст можна представити за формулою.

.

Отже рівність має місце, причому .

Достатність. Дано, що виконується рівність . Потрібно довести, що функція має похідну. Поділимо обидві частини на

, перейдемо до границі .

  1.  Локальний екстремум. Необхідні та достатні умови екстремуму.

Означення. Точка  називається точкою локального максимуму (мінімуму), якщо знайдеться такий окіл цієї точки, в кожній точці якого виконується нерівність  ().

Теорема. (Необхідна умова існування екстремуму) Нехай функція  в точці має екстремум. Якщо в цій точці існує похідна, то вона неминуче дорівнює нулю.

Доведення. Доведення даної теореми слідує з теореми Ферма.

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

Теорема. (Перша достатня умова) Якщо при переході через точку  похідна змінює знак, то екстремум існує. Якщо зберігає знак, то екстремум не існує.

Доведення. Доведення теореми проведемо для того випадку, коли точка  - локальний максимум.

. Візьмемо довільні .

. Т оді розглянемо .

Аналогічно, можна довести .

Теорема. (Друга достатня умова) Нехай функція визначена в околі точки, причому, а   існує. Якщо , то в точці  - , якщо , то в точці  - .

Правило дослідження функції на екстремум:

  1.  Знаходимо похідну функції.
  2.  Знаходимо корені рівняння.
  3.  Перевіряємо, чи змінює похідна знак при переході через ці точки.
  4.  Якщо змінює, то знаходимо значення функції в цих точках.

 

  1.  Інтеграл Рімана. Критерій інтегрованості функції за Ріманом.

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

Як і в невизначеному інтегралі, функція  f(x) називається підінтегральною функцією, вираз f(x)dx – змінною інтегрування. Інтервал основою  [a, b] називається інтервалом інтегрування, число а – нижньою, а число b -  верхньою межами інтегралу.

Відмітимо очевидний результат .

3. Суми Дарбу та їх властивості.

Нехай функція f(x) визначена на відрізку [a, b],  - деяке розбиття відрізку  [a, b] і

.

Покладемо

,

.

Очевидно, .

Означення. Сума  називається верхньою інтегральною сумою Дарбу, а сума  - нижньою.

Відмітимо наступні властивості інтегральних сум Дарбу.

  1.  Якщо функція f обмежена, то при довільному розбитті суми  і  визначенні, тобто і  - скінченні, і тому вирази  мають смисл.
  2.  Якщо , то  і .

Доведення. Нехай  і  - два розбиття відрізка [a, b], нехай  і нехай

, .

Якщо  , то, очевидно, .

В силу умови  кожний відрізок  розбиття  являється об'єднанням деякий відрізків розбиття будемо позначати ці відрізки .

Таким чином, якщо  і , то .

Використовуючи ці позначення і нерівність , отримаємо

.

Ми довели, що . Аналогічно доводиться, що .

  1.  Наслідок з 2. для будь-яких розбиттів   і  відрізка [a, b] виконується нерівність .

4. Необхідна і достатня умова інтегрованості функції на відрізку

Теорема. Для того щоб обмежена на деякому відрізку функція була інтегрованою на цьому відрізку, необхідно і достатньо, щоб  .

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

Оскільки  , то нерівність  рівносильна нерівності .

Необхідність. Нехай на відрізку [a,b] функція f  інтегрована на цьому відрізку і нехай , тоді . Тому для будь-якого  існує , таке, що якщо , то  , чи .

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

Таким чином, якщо , то , а це і означає виконання умови .

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

Звідси в силу  слідує , що , а значить, .Але в силу властивості інтегральних сум Дарбу . З  і  слідує, що , це і означає інтегрованість функції f.

5. Класи інтегрованих функцій

Твердження. Якщо функція f(x) – неперервна на сегменті [a, b], то вона інтегрована.

Твердження. Якщо обмежена функція f(x) на сегменті [a, b] має скінчене число точок розриву, то вона інтегрована.

Твердження. Монотонно-обмежена функція буде завжди інтегрованою

  1.  Числові ряди. Достатні ознаки збіжності.

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

Зауваження. Слід пам’ятати, що у виразі  суттєвим є порядок слідування чисел , а саме всі вони слідують один за одним в порядку зростання номера n.

Означення. Позначимо через  і скажемо, що  називаються відповідно частинними сумами ряду  першого, другого,...,n-го порядку.

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

Якщо границя  не існує або дорівнює нескінченно великому числу, то ряд   називається розбіжним.

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

Сума членів нескінченної геометричної прогресії:  .

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

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

Наслідок. У збіжному ряді сума n-го залишку при   прямує до нуля.

  1.  Застосування визначеного інтеграла.

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

Візьмемо будь-яке розбиття  відрізку . Йому відповідає розбиття траєкторії АВ на чистини .

Виберемо довільно по точці .

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

Сума всіх елементарних робіт  являється інтегральною сумою .

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

Таким чином, якщо позначити цю роботу буквою W, то в силу даного означення , маємо .

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

2. Визначення тиску. Нехай рідина заповнює посудину прямокутної форми. Обрахуємо тиск Р цієї рідини на одну із стінок посудини, рахуючи, що основа цієї стінки рівна а, а висота h.

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

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

Отже, ми довели, що вираз  дійсно являється диференціалом функції . Інтегруючи  на проміжку від 0 до h, отримаємо .

3. Загальна схема. У всіх задачах на використання визначеного інтеграла схема розв'язку одна і та сама. Шукана величина (площа, робота, шлях, об’єм) відповідала  деякому інтервалу зміни змінної величини, як раз той, яка в наступний випадок слугувала змінною інтегрування. Так, площа трапеції відповідала інтервалу  зміні абсциси х, робота – інтервалу  зміні шляху, шлях – інтервалу  зміні часу і т.д.

Припустимо, що ця змінна величина позначена через х, а інтервал її зміни через  .

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

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

Переходячи до границі при  , ми знаходили шукану величину І у вигляді інтегралу , де  - дана за умовою задачі функція.

  1.  Невласні інтеграли, ознаки збіжності.

Означення. Невласним інтегралом першого роду від функції f(x) в інтервалі  називається границя інтегралу  при . Записується так:  .

Якщо вказана границя існує, то невласний інтеграл називається збіжним, а якщо не існує, то розбіжним.

Теорема. (ознака збіжності). Нехай для всіх значень х виконується нерівність . Тоді:

якщо збігається інтеграл , то збігається і .

якщо розбігається інтеграл , то і розбігається інтеграл .

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

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

Теорема. Якщо збігається інтеграл  , то збігається і інтеграл .

Доведення. Для доведення розглянемо дві функції  і , визначивши їх наступним чином:     

                                                   

    =              =          

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

Але , і оскільки збігаються інтеграли від   і , то  інтеграл  теж збігається.

Означення. Інтеграл  називається абсолютно збіжним, якщо він сам збігається і збігається інтеграл .

Означення. Інтеграл  називається умовно-збіжним, якщо він збіжний, але  - розбіжний.

Означення. Невласним інтегралом другого роду від функції f(x) називається границя , при умові, що вона існує і являється скінченою.

Твердження. Щоб збігався невласний інтеграл , де - невід'ємна, обмежена функція на відрізку [a,b], необхідно і достатньо, щоб існувало число М, незалежне від х, таке, що , для всіх .

Теорема. Якщо  і  - невід'ємні, обмежені на піввідрізку   [a,b) інтегровані за Ріманом на кожному відрізку   і якщо , де с- стала, то із збіжності інтеграла  випливає збіжність інтеграла .

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

Теорема. Нехай - визначена на проміжку [a,b), обмежена на цьому проміжку і інтегрована на кожному відрізку , де . Якщо збігається , то збігається .

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

Означення. Інтеграл  називається абсолютно збіжним, якщо збіжний .

  1.  Степеневі ряди та їх застосування.

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

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

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

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

Звідси, враховуючи, що , дістанемо нерівність .

Беручи до уваги цю нерівність, матимемо таку оцінку для загального члена ряду: .

Нехай . Введемо позначення .

Складемо геометричний ряд . Цей ряд збіжний. Тоді збігається й ряд .

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

Першу частину теореми доведено. Справедливість другої частини випливає з доведеного вище.

Справді, візьмемо довільне число   таке, що . Тоді, якби ряд  збігався в точці , то він збігався б і в точці . Маємо суперечність. Теорему доведено.

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

Означення. Число  називається радіусом збіжності степеневого ряду.

Очевидно, що можливі наступні три випадки:

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

Однак теорема Абеля не дає відповідь на питання: яким буде ряд на кінцях проміжку.

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

Знаходження радіусу збіжності за ознакою д’Ламбера: .

Знаходження радіусу збіжності за радикальною ознакою Коші: .

38. Властивості степеневих рядів

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

Доведення. Нехай степеневий ряд збігається в інтервалі  .

Візьмемо додатне число . Тоді для всіх  справджується нерівність .

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

Властивість. Сума степеневого ряду всередині інтервалу збіжності є функція неперервна.

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

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

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


  1.  

  1.  Алгебра та геометрія
  2.  Прямі та площини у просторі.

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

Різні рівняння прямої:

- канонічне рівняння прямої (рівняння прямої, що проходить через точку  і паралельна вектору ).

рівняння прямої, що проходить через дві задані точки.

- рівняння прямої „у відрізках на осях”.

Ненульовий вектор, що перпендикулярний до прямої, називають вектором нормалі до прямої.

4.  - рівняння прямої, що проходить через відому точку і має відомий вектор нормалі ( - фіксована точка прямої;  - вектор нормалі прямої).

5.        - параметричне рівняння прямої.

                                     

6.  - загальне рівняння прямої.

Різні види рівнянь прямої в просторі:

  1.   - канонічне рівняння прямої.

        

2.      - параметричне рівняння прямої.

         

3.  - рівняння прямої, що проходить через дві відомі точки.

2.Критерій сумісності системи лінійних рівнянь.

Теорема. Система лінійних рівнянь є сумісною тоді і тільки тоді, коли ранг розширеної матриці рівний рангу основної матриці.

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

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

3.Лінійна залежність та ранг системи векторів, методи обчислення рангів.

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

Теорема. Найвищий порядок відмінний від нуля мінорів матриці рівна рангу цієї матриці.

Теорема. Рядкові і стовпцеві ранги довільної матриці рівні між собою.

Довільну матрицю можна звести до зведеної ступінчастої матриці.

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

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

4.Лінійні оператори в скінченно-вимірних просторах та їх матриці.

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

Означення. Лінійне відображення простору  самого в себе називається лінійним оператором.

Приклади лінійних просторів:

  1.   простори векторів на прямій, на площині і в просторі;
  2.  арифметичний n-вимірний дійсний простір.

Твердження. Лінійне відображення векторного простору переводить будь-яку лінійну комбінацію даних векторів  в лінійну комбінацію (з тими ж коефіцієнтами  нульовий вектор 0 залишається незмінним: , а образом вектора протилежного даному вектору а, служить вектор, протилежний для образу вектора а: .

Теорема. Якщо у просторі V вибрано деякий базис векторів , то довільне лінійне відображення простору V у простір W однозначно визначається заданням образів базису векторів. І навпаки, якщо в просторі W вибрати довільні n вектори , то існує, причому єдине, лінійне відображення простору V у W, при якому вектори базису  переходять відповідно у вектори .

Візьмемо в просторі V базис , а в просторі W , тоді  ... .

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

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

5.Власні вектори та власні значення лінійного оператора. Оператори з простим спектром.

Означення. Лінійний підпростір М простору V називається інваріантним відносно оператора , що переводить , якщо або, що те саме .

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

Теорема. Якщо  - інваріантний підпростір відносно не виродженого оператора в скінчено вимірному просторі V, то оператор  також – невироджений.

Означення. Вектор називається власним вектором а, якщо виконується умова , для деякого скаляра .

Означення. Число  називається власним значенням лінійного оператора А.

Говорять, що власний вектор а відноситься до власного значення .

Нехай  - квадратна матриця порядку n з дійсними елементами. Нехай, з іншої сторони,  - деяке невідоме.

Означення. Матриця , де Е – одинична матриця порядку n, називається характеристичною матрицею матриці А.

Так як в матриці  по головній діагоналі стоїть , всі ж решта елементи рівні нулю, то

.

Визначник матриці  буде многочлен від , причому степеня n. Дійсно, добуток елементів, які стоять на головній  діагоналі, буде многочлен від з старшим членом , всі решта члени визначника не містять по крайній мірі два з числа елементів, які стоять на головній діагоналі, і тому їх степінь відносно  не перевищує . Коефіцієнти цього многочлена можна було б легко знайти. Так, коефіцієнт при  рівний , а вільний член співпадає з визначником матриці А.

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

Означення. Рівняння виду  називається характеристичним рівнянням.

Теорема. Подібні матриці володіють однаковими характеристичними многочленами і, як наслідок, однаковими характеристичними коренями.

Доведення. Нехай, дійсно, . Тоді, враховуючи, що , отримаємо: , що і треба було довести.

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

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

Доведення. Нехай, дійсно, оператор  в базисі  має матрицю  і нехай вектор  являється власним вектором оператора ,  і .

Рівності   і  приводять до системи рівностей

,

          ,        (1)

....................

.

Так як , то не всі числа  рівні нулю. Таким чином, враховуючи систему, система лінійних однорідних рівнянь

,

         ,      (2)

......................

має ненульовий розв'язок, а тому її визначник рівний нулю,

.             (3)

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

Навпаки, нехай  буде будь-яким дійсним характеристичним коренем оператора  і, як наслідок, матриці А. Тоді має місце рівність , а тому і отримана з неї транспортуванням рівність (3). Звідси слідує, що система лінійних однорідних рівнянь (2) має ненульовий розв'язок, причому навіть дійсний, так як всі коефіцієнти цієї системи дійсні. Якщо цей розв'язок позначити через , то має місце рівність (1). Позначимо через b вектор простору V, який має в базисі  рядок координат ; ясно, що . Тоді справедлива рівність , а з (1) і цієї рівності слідує . Вектор b виявився, таким чином, власним вектором оператора .

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

Доведення. Нехай задано деякий оператор А і деяку його лінійну систему векторів  і власні значення , тоді потрібно довести, що . Будемо доводити методом математичної індукції:

1. ;

2. припустимо, що система лінійно-незалежна при ;

3. ; ; ;

6.Квадратичні форми. Зведення квадратичних форм до канонічного вигляду.

Означення. Білінійна функція називається симетричною, якщо виконується умова .

Означення. Матриця А називаються симетричною, якщо .

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

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

Розглянемо функцію

.     - квадратична форма від n змінних.

Означення. Рангом квадратичної функції називається ранг її матриці.

Лема. Якщо , тобто ранг добутку двох матриць не перевищує рангів цих матриць.

Лема. Якщо С=АВ і А – невироджена, тоді ранги С і В рівні.

Теорема. Ранги двох квадратичних форм, що є записами однієї і тієї ж квадратичної функції рівні між собою.

Доведення.  і С –невироджена. , тоді  за попередньою лемою. Теорему доведено.                                                                             

зведення квадратичної форми до канонічного вигляду методом лагранжа

- канонічний запис.

- матриця канонічного вигляду.

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

7.Основна теорема про подільність многочленів.

Теорема. (основна теорема теорії многочленів). Будь-який многочлен степеня більшого нуля з комплексними коефіцієнтами має в полі С принаймні один корінь.

Доведення. Доведемо спочатку конкретний випадок, а саме випадок, коли вільний член многочлена  рівний нулю, причому доведемо лише неперервність в точці . Іншими словами, ми доведемо наступну лему:

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

Дійсно, нехай . Число  нам вже дане. Покажемо, що якщо за число  взяти , то воно задовольняє умови.

Дійсно, , тобто . Так як  і, за , , то , і тому , що і треба було довести.

  1.  

  1.  Дискретна математика
  2.  Множини. Операції над множинами. Застосування теорії множин в математиці.

Поняття множини відноситься до аксіоматичних понять.

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

Означення. Предмети, які входять до складу множин називаються її елементами.

                                                                                                         Г. Кантор

Зауваження.

  1.  Канторівський вислів ніяк не обмежує природу елементів.
  2.  Дає змогу розглянути множини, елементи яких з певних причин не можна визначити.
  3.  Повинна існувати можливість з’ясувати, чи різні ці предмети чи однакові.
  4.   Повинна існувати можливість з’ясувати чи належить предмет даній множині.

Інтуїтивний  принцип об’ємності або аксіома екстенціональності:

Означення. Дві множини рівні тоді і тільки тоді, коли вони складаються з однакових елементів.

Означення. Множина А називається скінченою, якщо вона складається з скінченої кількості елементів.

Означення. Множина , яка складається з елементів деякої множини А, які входять в неї декілька разів називається мультимножиною. М(А).

Зауваження. З точки зору теорії множин множина А і її М(А) – один і той же об’єкт.

Інтуїтивний підхід до поняття властивість:

Означення. Під властивістю предмета х будемо розуміти речення, яке містить певну характеристику об’єкта х і про яке можна сказати істинне воно чи хибне.

Р – властивість.

Нехай Р(х). Задання множини в термінах властивості досягається за допомогою інтуїтивного принципу абстрактності (аксіома згортання):

Аксіома. Всяка властивість Р(х) визначає деяку множину А, за допомогою умови: елементами множини А є ті і тільки ті предмети а, які мають властивість Р.

Зауваження. Властивість Р може бути способом побудови елементів множини.

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

Позначення:

- випливає;

- необхідно і достатньо;

- будь-який;

- існує.

Означення. Множина А є підмножиною множини В, якщо всі її елементи є елементами множини В.

Аксіома екстенціональності:

Вираз А включається в В за умовою:

А – власна підмножина, В –власна множина.

Означення. Множина називається порожньою, якщо вона не містить жодного елемента.

Порожня множина є підмножиною будь-якої множини.

Означення. Нехай U – деяка множина, тоді B(U) – множина всіх підмножин множини U. У цьому випадку U – універсальна множина, B(U) – булеан множини U.

Означення. Об’єднанням множин А і В називається така третя множина, яка складається з усіх елементів цих множин.

Зауваження. Для наочності множини зображують за допомогою діаграм Ейлера-Венна.

Означення. Перерізом множин А і В називається така третя множина, яка складається з усіх елементів, які одночасно належать цим множинам.

Означення. Різницею множин А і В називається така множина, яка складається з усіх елементів, які належать множині А, але не належать множині В.

Зауваження. Якщо , то можна розглядати операцію доповнення .

Означення. Симетричною різницею називається така множина, яка складається з усіх елементів, які одночасно належать множині А, але не належать множині В і належать множині В, але не належать множині А.

Означення. Якщо множина , то називають покриттям множини А, якщо при цьому , то множину  називають розбиттям множини А.  називають класами розбиття.

Розглянуті операції – теоретикомножинні операції.

  1.  Відношення, операції над відношеннями.

Означення. Довільна підмножина R декартового добутку називається відношенням множини .

Якщо розглядається , то R = п-арне відношення на множині А.

Означення. Коли , то кажуть, що елементи  знаходяться між собою у відношенні п: п=1 – унарне; п=2 – бінарне; п=3 – тернарне.

Оскільки R – підмножина декартового добутку, то для відношень визначені операції : об’єднання, перерізу, різниці, доповнення.

  1.  
  2.  
  3.  
  4.  

Зауваження. Операція доповнення називається запереченням відношення R.

Бінарні відношення та їх властивості.

aRb означає, що . Нехай .

Означення. називається оберненим до R, якщо .

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

. Суперпозиція може бути невизначена, якщо не існує відповідного елемента множини В, якщо А=В=С, то суперпозиція завжди існує.

Теорема. Якщо  - бінарні відношення, задані на множині А, то:

  1.  
  2.  
  3.  
  4.  
  5.  
  6.  Комбінаторика. Основні комбінаторні схеми.

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

Якщо для певної мети слід вилучити елементи множини, які задовольняють певну властивість або властивості, то маємо задачу пер6елічення.

Основний принцип комбінаторики. (правило множення) Нехай потрібно послідовно виконати k дій, якщо першу дію можна виконати  способами, ..., k-ту дію  способами, тоді всі k дій можна виконати  способами.

Правило суми. Якщо об’єкт А може бути вибраний т способами, а об’єкт В може бути вибраний п способами, то вибір одного елемента – або А, або В – може бути здійснений т+п способами.

Означення. Комбінаціями з п елементів по k називають невпорядковані k- елементні підмножини з множини з п елементів.

Число всіх комбінацій із п елементів по k позначається символом .

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

.  Зауваження. Числа  називаються бінальними коефіцієнтами.

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

Означення. Характеристичним вектором називається вектор .

Твердження. Підмножина  дорівнює підмножині , коли .

Наслідок. Число різних підмножин п-елементної множини дорівнює .

Наслідок. .

Означення. Комбінації з повторенням називають класи еквівалентності, на які можна розбити п-елементну множину.

Їх число позначається .

Означення. Нехай є множина, яка містить п елементів. Кожна її впорядкована підмножина, що складається з k елементів, називається розміщенням з п елементів по k.

Число таких розміщень позначається .

Означення. Розміщення з повтореннями або розміщення з повтореннями з п по k називаються будь-які кортежі довжини k, що складаються з елементів множини А.

Число розміщень з повтореннями позначається .

Означення. Різні впорядковані множини, які відрізняються лише порядком  елементів називають перестановкою цієї множини.

Перестановки є окремим випадком розміщення. Оскільки кожна перестановка містить всі п-елементи множини, то різні перестановки відрізняються одна від одної тільки порядком елементів. Число перестановок із п елементів позначають через .

У загальному випадку число перестановок із п елементів . Отже, число перестановок із п елементів дорівнює п!

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

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

  1.  Біном Ньютона.

Біном Ньютона:

. Узагальнення цієї формули є поліноміальна формула. .

  1.  Булеві функції. Мінімізація булевих функцій.

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

Всі булеві функції від одного аргументу

аргумент

 0

0

0

1

1

1

0

1

0

1

Функція:

- тотожний  нуль;

-  тотожна функція;

- заперечення;

- тотожна одиниця

Означення. Булева  функція від двох аргументів називається функція g, така що .

х

у

0

0

1

х

2

3

4

y

5

6

7

8

9

10

11

12

13

|

14

1

15

0

0

0

0

0

0

0

0

0

0

1

1

1

1

1

1

1

1

0

1

0

0

0

0

1

1

1

1

0

0

0

0

1

1

1

1

1

0

0

0

1

1

0

0

1

1

0

0

1

1

0

0

1

1

1

1

0

1

1

0

0

1

0

1

0

0

0

1

0

1

0

1

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

Функції: 0 – тотожній нуль (); 1 – кон’юнкція (); 2 – тотожна х;

3 – заперечення імплікації; 4 – заперечення антиімплікації; 5 – тотожна у;

6 – заперечення (додавання за модулем 2); 7 – диз’юнкція; 8 – стрілка Пірса (функція Верба);

9 – еквівалентність;10 – заперечення у; 11 – антиімплікація; 12 – заперечення х;

13 – імплікація; 14 – штрих Шефера; 15 – тотожна одиниця.

Означення. Дві булеві функції  - рівні, якщо кожному набору аргументів х і у вони ставлять у відповідність однакове значення 0 або 1.

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

  1.  Функціональна повнота систем булевих функцій. Теорема Поста.

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

Доведення. Для доведення треба розглянути 5 функцій.

повна.

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

З поняття повноти системи тісно пов’язане поняття замикання і замкненого класу.

Означення. Нехай А деяка підмножина булевих функцій. Замиканням А [A]  називається множина всіх булевих функцій, які можна виразити у вигляді формул через функції множини А.

Означення. Множина А називається функціонально замкненою, якщо замикання А співпадає з А. A=[A].

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

Для їх опису використовують 5 класів булевих функцій, які називають класами Поста., замкнених відносно суперпозиції:

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

Означення. Функція  називається функцією, що зберігає нуль, якщо .

Означення. Функція f від п змінних називається функцією, яка зберігає одиницю, якщо  виконується .

Означення. Функція двоїста сама собі називається самодвоїста   .

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

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

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

функція   клас Поста           

+

+

-

+

+

+

-

-

-

-

+

-

-

-

+

+

+

+

-

-

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

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

Достатність. Для доведення зафіксуємо 5 функцій:

- функція не зберігає нуль;  - функція не зберігає одиницю;

- несамодвоїста;  - нелінійна;  - немонотонна.

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

Покажемо, як будуються константи 0 і 1. підставляючи у функцію  змінну х одержимо нову функцію . Для якої за умовою справедлива рівність h(0)=1.  Якщо виявиться, що h(1) =1, mo . Підставляючи її  замість  у , одержимо другу константу 0. якщо таким шляхом не можна одержати 0 і 1, то функція h(x) є запереченням.

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

  1.  Графи, їх різновиди. Шляхи у графах. Зв”язність графів.

Нехай V – деяка непорожня скінчена множина, а  - множина всіх двохелементних підмножин множини V.

Означення. Графом називається пара множин V і E.

Означення. Елементи множини V називають вершинами графа. Елементи множини Е називають ребрами графа ().

Ребра позначають парами чисел: (u,v).

Означення. Граф, який складається з однієї вершини називається тривіальним.

- порожній граф.

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

Означення. Якщо , то вершини  називають кінцями ребра .

Означення. Два ребра називають суміжними, якщо вони мають спільну вершину.

Означення. Граф називається скінченим, якщо множини V і Е – скінченні.

Кількість вершин графа позначається таким чином . Кількість ребер - .

Означення. Кількість вершин графа називається його порядком.

Означення. Кількість ребер інцидентних деякій вершині називається степенем вершини.

Означення. Якщо множина Е співпадає з порожньою множиною, то граф називають нуль-графом (повністю незв’язним графом).

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

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

Означення. Скінчений неорієнтований граф без петель і кратних ребер називають звичайним.

Означення. Вершина степеня 0 називається ізольованою, а 1 – кінцевою або висячою.

Теорема. У будь-якому графі сума степенів вершин дорівнює .

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

Теорема. У будь-якому графі кількість вершин непарного степеня – парна.

Доведення. Нехай   - множина вершин парного степеня, а  непарного степеня. . . .

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

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

Теорема. Кількість ребер у повному графі з n вершин дорівнює .                        

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

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

Повним граф n-го порядку є регулярним графом n-1-го порядку.

Граф в) називається графом Петерсена і він називається тривалентним.

Графи а), г), і д) – Платонові графи.

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

Зауваження. Узагальненням двочастинних графів є к-частинні графи.

Означення. Якщо пара  - впорядкована, то граф називають орієнтованим графом або орграфом.

Означення. Ребра орграфа називаються дугами і зображаються напрямленими відрізками.

Кожному неорієнтованому графу можна поставити у відповідність орграф з тією самою множиною вершин, в якому кожне ребро замінено дугами, що інцидентні тим самим вершинам і мають зворотний напрямок. Така відповідність між графами і орграфами називається канонічною.

Означення. Граф, який має і ребра і дуги називається мішаним.

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

Означення. Кількість ребер у маршруті називається довжиною маршруту.

Означення. Маршрутом, довжини 0, називається послідовність, що складається з єдиної вершини.

Означення. Маршрут, в якому всі ребра попарно різні називається ланцюгом.

Означення. Маршрут, в якому всі проміжні вершини різні називається простим ланцюгом.

Означення. Маршрут називають замкненим, якщо   і  збігаються.

Означення. Замкнений ланцюг називається циклом.

Лема. Будь-який маршрут, що веде з вершини v у вершину w містить у собі простий ланцюг, що веде з v у w.

Доведення. Справді, нехай дано деякий маршрут М такий, що серед його проміжних вершин є однакові.

Нехай , тоді ділянка  буде замкненою, викинувши з М ділянку, отримаємо новий маршрут М’, який також веде з v у w. Якщо М’ – непростий ланцюг, то процедуру вилучення його внутрішніх циклічних ділянок можна повторити. Врешті решт отримаємо простий ланцюг.

Граф, усі ребра якого утворюють простий цикл з довжиною n, позначають .

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

Означення. Компонентою  зв’язності графа G називається його зв’язний підграф такий, що не є власним підграфом жодного іншого зв’язного підграфа графа G.

Означення. Відстанню між вершинами v і w зв’язного графа називається довжина найкоротшого простого ланцюга, що з’єднує ці вершини.

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

Означену функцію відстані задовольняють три аксіоми:

1. , ;

2.  ;

3.  - трикутна.

Означення. Ексцентриситет  довільної вершини v зв’язного графа називається найбільша відстань між вершиною v і всіма іншими вершинами графа.

Означення. Діаметром  зв’язного графа називається максимальних з усіх ексцентриситетів вершин графа.

Означення. Мінімальний з усіх ексцентриситетів називається радіусом.

Означення. Вершина v називається центральною, якщо ексцентриситет цієї вершини дорівнює радіусу.

Означення. Центром графа називається множина всіх його центральних вершин.

Означення. Вершини v і w називаються зв’язаними, якщо існує маршрут, що їх з’єднує.

Відношення зв’язності – транзитивне, рефлексивне, симетричне, звідки слідує, що воно є відношенням еквівалентності.

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

Теорема. Будь-який граф є сам зв’язний або його доповнення є зв’язним графом.

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

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

Наслідок. Якщо  - незв’язний граф, то  - зв’язний і .

  1.  Планарні графи. Гіпотеза про 4 фарби.

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

Простий цикл, дерево, ліс є планарними графами.

Лема. Будь-який підграф планарного графа є планарним.

Лема. Граф є планарним тоді і тільки тоді, коли кожна його зв’язна компонента – планарний граф.

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

Наслідок. Для правильного розфарбування кубічного графа достатньо 4 фарби.

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

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

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

Для правильного розфарбування вершин довільного планарного графа потрібно не більше чотирьох фарб – математичне формулювання гіпотези.

  1.  Алгебра та числення висловлювань.
  2.  Числення предикатів та теорії 1-го порядку
  3.  Основні поняття абстрактної теорії автоматів. Автомати Мілі та Мура.

Теорія автоматів – розділ теорії керованих систем, що вивчає математичні моделі перетворювачів дискретної інформації (автомат).

Теорія автоматики виникла в середині ХХ століття у зв’язку з вивченням скінчених автоматів, як математичних моделей нервових систем обчислювальних машин. З певної точки зору автоматами є як реальні пристрої (обчислювальні  машини, живі істоти, автомати) так і абстрактні системи (аксіоматичні теорії).

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

Теорія автоматів знаходить застосування, крім суто математичних розділів (теорії алгоритмів, розв’язність формальних числень інших спеціальних розділів математики), так і в розв’язані деяких практичних задач.

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

Означення. П’ятірка   називається автоматом Мілі, якщо вона складається з множини станів автомата А, множини вхідних символів , функції переходів , яка переводить прямий добуток ; і функції виходів , яка ставить .

Означення. Множини  і  називаються відповідно вхідним і вихідним алфавітами автомата.

 

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

Коли на вхід  автомата подати слово (послідовність вихідних символів), то автомат А можна розглядати як алфавітний перетворювач інформації. Послідовність вхідних символів можна розглядати як функцію натурального аргументу – дискретного автоматного часу. Це дає підстави розглядати автомат як дискретну автоматну систему, яка змінює свій стан під дією зовнішніх і внутрішніх факторів.

Означення. Автомат А називається ініціальним, якщо в множині його станів виділено деякий стан, який називається початковим.

При цьому вважається, що в початковий момент часу автомат перебуває в початковому стані.

Означення. Автомат називається скінченим, якщо три множини  є скінченими; і нескінченним, якщо хоч одна з них є нескінченною.

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

Означення. Якщо  - відношення, то автомат називається не детермінованим (у таких автоматах порушена умова однозначності переходу).

Означення. Якщо - функція, то автомат називають детермінованим.

Означення. Автоматом Мура називається п’ятірка  причому , де . Якщо його функція виходів g виражається через функцію переходів f за допомогою функції h.

  1.  Основні поняття теорії скінченних автоматів.
  2.  Методи оптимізації
  3.  Задача лінійного програмування. Її властивості.

Загальна схема формалізації задач керування і планування може бути описана наступним чином. Як правило такі задачі зводяться до вибору деякої системи параметрів і деякої системи функцій, які називатимемо характеристиками управління. Щоб надати перевагу тим чи іншим значенням параметрів планування і тим чи іншим функціям керування, необхідно перш за все чітко усвідомити собі наступні дві обставини. По-перше, необхідно сформулювати і виразити через шукані характеристики показник якості – критерій, який визначає відповідність планів, що розробляються тій меті, за ради якої дана розробка ведеться. По-друге, необхідно з’ясувати умови роботи системи і обмеження, які звідси випливають, і які повинні задовольняти шукані характеристики. Таким чином, проблеми управління і планування зводяться до екстремальних задач наступного виду: – необхідно знайти максимум (мінімум) функції f(x1,x2,...,xn) (1) при умовах gi(x1,x2,...,xn)≤0, i=1,2,...,m, (2) xjі0, j=1,2,...,t≤n (3).

Лінійним програмуванням називається розділ математичного програмування, що вивчає задачі типу (1)-(3), в яких функції f та gi є лінійними, тобто gi(x1,x2,...,xn)=ai1x1+ai2x2+...+ainxn (i=1,2,...,m), f(x1,x2,...,xn)=c1x1+c2x2+...+cnxn, де aij, cj (i=1,2,...,m; j=1,2,...,n) – задані константи.

Очевидно, що допустимою областю D загальної ЗЛП є многогранна множиною. Тоді, використовуючи доведені раніше твердження про опуклі множини приходимо до наступної важливої властивості допустимої області ЗЛП.

Теорема 6.1. Допустима область D ЗЛП є опуклою многогранною множиною (опуклим многогранником розв’язків – обмеженим чи необмеженим).

Таким чином, ЗЛП полягає в знаходженні мінімуму (максимуму) лінійної форми L(x) на опуклому многограннику розв’язків D.

Введемо наступне важливе поняття. Точки опуклої множини, які не є опуклою лінійною комбінацією двох різних точок цієї множини, називаються кутовими (крайніми) точками. Іншими словами, точка xОW – є кутовою, якщо не існує точок x1,x2 (x№x1,x№x2) таких, що x1№x2, x1,x2ОW і x=a1x1+a2x2, де a1,a2і0, a1+a2=1.

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

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

Доведення. Нехай многогранник розв’язків визначений, має скінчене число кутових точок. Позначимо його через К. В двохвимірному просторі К має вид многогранника (рис.6.1). Позначимо кутові точки К через Х12,...,Хр, а оптимальний план – через Х0. Тоді L(Х0)≤L(Х) для всіх Х з К. Якщо Х0 – кутова точка, то перша частина теореми доведена. Нехай Х0 не є кутовою точкою; тоді Х0 на основі теореми 6.1 можна представити як опуклу лінійну комбінацію кутових точок К. Іншими словами X0=l1X1+...+lpXp, liі0 (i=1,...,p), еli=1.

Оскільки L(X) – лінійна функція, отримаємо: L(X0)=L(l1X1+...+lpXp=l1L(X1)+...+lpL(Xp). (6.1)

В цьому виразі серед значень L(Xi) (i=1,2,...,p) виберемо найменше (припустимо, що воно досягається в кутовій точці Xk (1≤k≤p)) і позначимо його через m. Іншими словами L(Xk)=m.
Замінимо в (6.1) кожне значення L(X
i) найменшим значенням. Тоді, в силу того, що liі0, еli=1 матимемо: L(X0)іl1m+...+lpm=m.

За припущенням Х0 – оптимальний план. Тому, з одного боку, L(X0)≤m. Але, з іншого боку, маємо, що L(X0)іm. Отже, Z(X0)=m=Z(Xk), де Xk – кутова точка. Таким чином, існує кутова точка Xk, в якій лінійна функція приймає мінімальне значення.

Для доведення другої частини теореми припустимо, що L(X) приймає мінімальне значення більше ніж в одній кутовій точці, наприклад в точках X1,X2,...,Xq, 1<q≤p. Тоді Z(X1)=Z(X2)=... =Z(Xq)=m. Якщо X – опукла лінійна комбінація цих кутових точок, тобто X=l1X1+..+lqXq, liі0 (i=1,...,q), еli=1, то Z(Xq)=Z(l1X1+..+lqXq)=l1Z(X1)+..+lqZ(Xq)=l1m+..+lqm=m іншими словами лінійна функція Z приймає мінімальне значення в будь-якій точці Х, яка є опуклою лінійною комбінацією кутових точок Х12,...,Хq. Теорема доведена.

Зауваження. Якщо многогранник розв’язків – необмежена область, то не кожну точку області можна представити опуклою лінійною комбінацією точок області. В цьому випадку задачу лінійного програмування можна привести до задачі з обмеженою областю, ввівши у систему допоміжне обмеження Х12+...+Хn<Q, де Q - достатньо велике число. Введення цього обмеження рівносильне відсіку гіперплощиною Х12+...+Хn=Q (рис 6.2) від многогранної необмеженої області обмеженого многогранника, для точок якого теорема вже виконується. Очевидно, що координати кутових точок E i F, які з’являються в результаті введення нового обмеження, залежать від Q. Якщо в одній з них лінійна функція приймає мінімальне значення, то і воно залежатиме від Q. Змінюючи Q, значення лінійної функції можна зробити скільки завгодно малим, а це означає, що лінійна функція необмежена на многограннику розв’язків.

  1.  Критерій оптимальності базисного розв’язку задачі лінійного програмування.

Теорема 10.1. (критерій оптимальності допустимого базисного розв’язку ЗЛП) Якщо для деякого допустимого базисного розв’язку X* ЗЛП виконуються умови Dj≤0, де Dj – відносні оцінки змінних xj (j=1,...,n), то X* – оптимальний розв’язок.

Доведення. Не обмежуючи загальності будемо вважати, що X*=(x*1,...,x*m,0,...,0). Тоді еx*iAi=B. (10.1)

Значення цільової функції для плану X* буде дорівнювати еcix*i=Z0. Допустимому базисному розв’язку відповідає система лінійно незалежних векторів A1,...,Am, яка утворює базис. Розклад векторів Aj за векторами базису має такий вигляд: Aj=еaijAi (j=1,...,n). (10.2)

Нехай Y=(y1,...,yn) – будь-який допустимий розв’язок ЗЛП. Тоді еyjAj=B. (10.3)

Значення цільової функції для плану Y дорівнює еcjyj=`Z. (10.4)

Доведемо, що при Dj≤0 завжди Z0≤`Z. Оскільки, з (9.8) маємо Zj≤cj, то при заміні в (10.4) cj на Zj одержимо еZjyj≤`Z. Підставимо у цю нерівність замість Zj їх значення. Тоді еZjyj=е(еciaij)yj=е(еaijyj)ci≤`Z. (10.5)

Підставимо тепер в рівність (10.3) замість Aj їх значення з (10.2). Одержимо еyjAj=еy,sub>j(еaijAi)=е(еaijy,sub>j)Ai=B. (10.6)

Оскільки система векторів A1,...,Am лінійно незалежна, то коефіцієнти при однакових векторах в (10.1) і (10.6) повинні бути однакові, тобто x*i=еaijyj (i=1,...,m). Враховуючи це нерівність (10.5) можна переписати у вигляді е(еaijyj)ci=еx*ici=Z0≤`Z. Теорема доведена.

Отже, якщо відносні оцінки Dj змінних xj ЗЛП недодатні, то покращити отриманий допустимий базисний є оптимальним.

  1.  Двоїсті задачі лінійного програмування. Теорема двоїстості.

Кожній задачі лінійного програмування можна єдиним чином співставити деяку іншу задачу (ЗЛП), яка називається двоїстою або спряженою по відношенню до початкової (або прямої). Нехай маємо стандартну ЗЛП:

,

,  де ,  , .

Знайдемо в області допустимих розв’язків ЗЛП оцінку знизу для цільової функції СХ. Оскільки , то для будь-якого вектора  маємо:

.

Нехай вектор U задовольняє обмеження  або, що те ж саме, . Тоді . У зв’язку з наведеними вище простими міркуваннями визначимо двоїсту до стандартної ЗЛП задачу:

,

.

Наведені вище міркування можна сформулювати у вигляді твердження:

Лема 1. Цільові функції прямої та двоїстої задач задовольняють співвідношення: .

Звідси, очевидно, випливає, що .

Запишемо пряму та двоїсту задачі в координатній формі:

Пряма: ,  (7.1)

, , (7.2)

, .  (7.3)

Двоїста:  ,  (7.4)

  , .  (7.5)

Відмітимо, що якщо пряма задача задана в стандартній формі, то двоїста до неї не містить прямих обмежень на змінні . Тобто  можуть бути довільними дійсними числами (не обов’язково додатніми). Змінні  називаються двоїстими (або множниками Лагранжа).

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

,

 (7.6)

.

Запишемо цю задачу в стандартній формі:

,

де , , I – одинична матриця розмірності . Двоїстою до отриманої стандартної ЗЛП (а, отже, і до вихідної загальної ЗЛП) буде задача:

, ,

або  ,

,  (7.7)

.

Безпосередньо можна показати, що двоїстою до задачі (7.7) є задача (7.6). Задачі (7.6)-(7.7) називаються симетричними двоїстими задачами. Справедливе твердження: Для будь-якої ЗЛП двоїста задача по відношенню до двоїстої співпадає з вихідною. Тому можна говорити не про пряму та двоїсту задачу, а про пару двоїстих задач.

Зв’язок між розв’язками прямої та двоїстої задач.

Розглянемо пару двоїстих задач, утворених стандартною ЗЛП і двоїстої до неї:

Пряма:   (7.10)

,   (7.11)

, .  (7.12)

Двоїста:   (7.13)

,   (7.14)

Кожна із пари двоїстих задач є фактично самостійною ЗЛП і може бути розв’язана незалежно одна від одної. Проте, між розв’язками прямої і двоїстої задач є взаємозв’язок.

Лема 1. Значення цільової функції прямої задачі (7.10)-(7.12) при будь-якому допустимому розв’язку Х не менше значення цільової функції двоїстої задач (7.13)-(7.14) при будь-якому допустимому розв’язку Y.

Лема 2. Якщо для деяких допустимих розв’язків  і  прямої та двоїстої задач значення цільових функцій співпадають , то  – оптимальний розв’язок прямої задачі, а  – оптимальний розв’язок двоїстої задачі.

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

Доведення. Доведемо першу частину теореми. Нехай пряма ЗЛП задана в стандартній формі:

.

Двоїста до неї має вигляд:

.

Нехай  оптимальний розв’язок прямої задачі, йому відповідає базис A1,...,Am та базисна матриця . Перейдемо від стандартної ЗЛП до канонічної ЗЛП:

 

, .

при цьому , . Відмітимо, що тоді . Згідно з критерієм оптимальності, для розв’язку  відносні оцінки недодатні:

.

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

.

Тобто, значення цільової функції двоїстої задачі в точці  співпадає із значенням цільової функції прямої задачі при , отже, згідно леми 2,  – оптимальний розв’язок двоїстої задачі.

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

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

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

Крім того, оскільки відносні оцінки , а матриця А, містить одиничну (таке припущення не обмежує загальності, адже симплекс-метод застосовується лише до канонічної ЗЛП), то для координат вектора  можемо записати простіші співвідношення, а саме

, ,  (7.15)

де  – номери векторів умов вихідної задачі, що утворюють одиничну матрицю.

Теорема 2. (друга теорема двоїстості). Для того, щоб  був оптимальним розв’язком прямої задачі, а  – двоїстої необхідньо і досить, щоб вони були допустимими розв’язками відповідних задач та виконувались умова:

,  (7.16)

Доведення. Необхідність. Нехай  – оптимальний розв’язок стандартної ЗЛП. Тоді, згідно з першою теоремою двоїстості, існує оптимальний розв’язок  двоїстої задачі, причому . Враховуючи, що , останньої рівності будемо мати:

або .

Умова (7.16) виконана.

Достатність. Нехай справедливе співвідношення (7.16). Тобто, для деяких допустимих розв’язків пари двоїстих задач  та  виконується рівність . Звідси матимемо . Тоді згідно з лемою 2,  та  – оптимальні розв’язки відповідно прямої та двоїстої задач. Теорема доведена.

  1.  Транспортна задача лінійного програмування. Властивості. Методи розв’язання транспортних задач. Транспортна задача з обмеженими пропускними спроможностями.

Математична постановка задачі.

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

Розглянемо ТЗ, в якості критерія оптимальності якої взята мінімальна ціна перевезення всього вантажу.

Введемо позначення:

– тарифи первозу одиниці вантажу із і-го пункту відправлення в j-тий пункт призначення;

– запаси вантажу в і-ому пункті відправлення;

– потреби вантажу у j пункті призначення;

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

Математична постановка транспортної задачі формулюється наступним чином: необхідно знайти мінімальне значення функції (загальної вартості перевезень)

(9.1) при обмеженнях: , (9.2) , (9.3)

(9.4)

Обмеження (9.2)-(9.3) з економічної точки зору означають, що з пунктів відправлення вивозиться вся продукція та повністю задовольняються потреби споживачів. Оскільки змінні , то це означає, що зворотні перевезення виключається.

Відмітимо, що транспортна задача  (9.1)-(9.4) є стандартною задачею лінійного програмування . Дійсно, ввівши позначення:

,  ,

, ,

та позначивши через А матрицю, стовпчиками якої є вектори ,, задачу (9.1)-(9.4) можемо записати в такому вигляді:

,

,

.

З умов (9.2)-(9.3) очевидно випливає наступне співвідношення:  (9.5)

Транспортна задача, для якої виконується умова (9.5) називається закритою або збалансованою. На практиці зустрічаються і незбалансовані або відкриті ТЗ. Тобто коли . В цьому випадку також може бути поставлена задача про побудову плану перевезень з мінімальними транспортними витратами, причому умови (9.2)-(9.3) модифікуються. Зокрема, у випадку  обмеження (9.2) замінюється наступним:

,  (9.2')

У випадку  обмеження (9.3) замінюється таким: ,  (9.3')

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

Для зручності розв’язання транспортної задачі її дані часто записують у вигляді таблиці:

Пункт відправлення (постачальник)

Пункти призначення (споживачі)

Запаси

Q1

Q2

...

Qj

...

Qn

    с11

 x11

  c12

x12

...

    c1j 

x1j

...

        c1n

x1n

a1

c21

x21

c22

x22

...

c2j 

x2j

...

c2n

x2n

a2

...

...

...

...

...

...

...

...

cj1

xj1

cj2

xj2

...

cji

xji

...

cjn

xjn

ai

...

...

...

...

...

...

...

...

cm1

xm1

cm2

xm2

...

cmj

xmj

...

cmn

xmn

an

Потреби

b1

b2

...

bj

...

bn

Властивості транспортної задачі.

1. Закрита ТЗ (9.1)-(9.4) завжди допустима та має розвязок.

Дійсно, розглянемо перевезення , де  які є невід’ємними і задовільняють систему обмежень (9.2)-(9.3):

,

Отже, перевезення  – допустимі. Існування ж мінімуму цільової функції ТЗ безпосередньо випливає з очевидної обмеженості допустимого багатогранника розвязків .

2. Ранг матриці системи рівнянь обмежень ТЗ рівний m+n–1 або, іншими словами, серед рівнянь (9.2)-(9.3) лише m+n-1 лінійно незалежних.

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

Додамо n останніх рівнянь системи і від одержаної суми віднімемо суму другого, третього і т.д. m-го рівняння. Одержимо  або .

Отже, перше рівняння системи обмежень є лінійною комбінацією всіх інших рівнянь, тобто дана система містить не більше ніж m+n–1 лінійно незалежних рівнянь.

Щоб показати, що число лінійно незалежних рівнянь системи дорівнює m+n–1, досить у матриці А системи 

де  – вектори розміру m+n, компонентами яких є коефіцієнти при невідомих  системи обмежень, виявити квадратну підматрицю порядку m+n–1, визначник якої не дорівнює нулеві. Такою підматрицею є, наприклад, матриця, складена з перших m+n–1 компонент векторів P1n, P2n, ... , Pmn, P11, P12, ... , P1n-1. Легко помітити, що на головній діагоналі цієї підматриці стоять одиниці, а під нею – нулі. Тобто розлянутий мінор дорівнює 1.

В силу другої властивості одне (будь-яке) з рівнянь-обмежень (9.2)-(9.3) можна відкинути. Цього як правило не роблять для збереження симетричності запису.

3. Якщо в ТЗ всі числа    ,  – цілі, то хоча б одне її оптимальне рішення також цілочислове. В справедливості цієї властивості впевнимось пізніше, аналізуючи запропонований нижче метод розв’язку ТЗ.

Оскільки ТЗ є задачею лінійного програмування, її базисні розв’язки – вершини допустимого багатогранника – відіграють особливу роль. Приймаючи до уваги другу властивість, можемо зробити висновок, що невироджений базисний розв’язок ТЗ містить рівно  ненульових перевезень xij. У виродженому випадку базисний розв’язок  ТЗ  містить менше  ненульових компонент.

Для того, щоб надати поняттю базисного розв’язку ТЗ наочний геометричний зміст, введемо деякі визначення.

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

Теорема 9.1  Вектори умов Pij є лінійно-незалежними тоді і тільки тоді, коли з відповідних комунікацій неможливо скласти замкнутий маршрут (цикл перевезень).

Теорема 9.2 Розв’язок ТЗ є базисним, якщо з його основних комунікацій неможливо скласти замкнутий маршрут (цикл). Вказані визначення і сформульовані твердження можна трансформувати стосовно транспортної таблиці. При цьому, якщо неможливо скласти замкнутий ланцюжок (цикл) з занятих клітин  згаданої таблиці, то записане рішення є базисним, в іншому випадку – ні.

Висловлене вище проілюструється наступними таблицями.

Таблиця 7 Таблиця 8

Q1

Q2

Q3

Q4

ai

Q1

Q2

Q3

Q4

ai

P1

3

3

2

2

10

P1

3

5

2

10

P2

2

8

5

15

P2

8

7

15

P3

7

7

P3

7

7

bj

3

5

10

14

32

bj

3

5

10

14

32

В таблиці 7 легко знайти замкнуті ланцюжки (цикли) з занятих клітин (вказана одна з них). Записані в цій таблиці допустимі рішення не є базисним (міжіншим, в цьому можна було б впевнитися, підрахувавши число занятих клітин, їх - 8, в той час як базисне рішення цієї ТЗ повинно мати не більше 3+4–1=6 відмінних від нуля перевезень). В таблиці 8 приведено одне з невироджених рішень даної ТЗ. Нехай R – деяка лінійно незалежна система векторів  умов транспортної задачі й вектор .

Теорема 9.3. (Критерій розкладу довільного вектора  через систему лінійно незалежних векторів  умов транспортної задачі). Для того, щоб вектор  був лінійною комбінацією векторів системи R, необхідно і досить, щоб із клітин, які відповідають векторам системи R, можна було скласти замкнутий маршрут, який замикається на клітинці .

Знаходження початкового базисного розв’язку (опорного плану) ТЗ.

Для розв’язування ТЗ методом потенціалів, потрібно мати початковий опорний план задачі. Існує ціла низка методів пошуку початкових опорних планів ТЗ. Найбільш поширеними серед них є:

а) метод північно-західного кута;

б) метод  мінімального елемента;

в) метод подвійної переваги;

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

Метод мінімального елементу. Ідея методу полягає в тому, щоб максимальним чином завантажити перевезеннями ті комунікації, які мають найменші транспортні витрати. Метод реалізується наступним чином. На першому кроці визначаємо мінімальний елемент матриці . Нехай це буде . Покладаємо . Можливі два випадки: 1) ; 2) . В першому випадку покладаємо , в другому – . Зрозуміло, що в результаті виконання першого кроку будуть заповнені або рядок або стовпчик транспортної таблиці. На першому кроці з матриці  викреслюємо відповідний рядок чи стовпчик. Отримаємо матрицю .

Покладемо також:

             

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

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

Метод подвійної переваги. Якщо таблиця вартості перевезень велика, то перебір всіх елементів ускладнюється. В цьому випадку використовують метод подвійної переваги, суть якого полягає в наступному: в кожному стовпчику помічають значком V клітинку з найменшим значенням вартості перевезення. Це ж  саме виконують і для кожного рядка. В результаті деякі клітинки матимуть подвійну мітку VV. В них знаходиться мінімальна вартість перевезень як в стовпці так і в рядку. Саме в ці клітини і розміщують максимально можливі об’єми перевезень, кожний раз виключаючи із розгляду відповідні стовпці або рядки. Потім розподіляють перевезення в клітинки, які відмічені значком V. В решті таблиці перевезення розподіляють за найменшою вартістю (найменшому тарифу).

Метод потенціалів розв’язку транспортної задачі.

Розглянемо спочатку невироджений випадок. Це означає, нагадаємо, що будь-який базисний розв’язок  ТЗ має рівно m+n-1 позитивних елементів.

В методі потенціалів істотно використовується приведений вище двоїстий критерій оптимальності ТЗ. Сформулюємо цей критерій, в інших, ніж раніше, термінах.

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

Сутність метода потенціалів полягає  в наступному.

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

2) Визначаються потенціали   та  так, щоб в кожній базисній клітині виконувалась умова:  або,  що теж саме . Відмітимо, що система має m+n–1 рівнянь (за кількістю базисних клітин) і m+n змінних. Тому одну  із змінних задаєм довільно (наприклад, покладемо ), останні знаходимо виходячи з вказаної системи (це легко зробити в силу специфіки рівнянь, яка визначається, в свою чергу, специфікою матриці A).

3) Визначимо відносні оцінки  для небазисних (вільних) клітин. Якщо для всіх цих клітин , то в силу двоїстого критерію оптимальності ТЗ відповідний базисний розв’язок є оптимальним. Якщо існують небазисні клітинки, для яких , то досліджуваний базисний розв’язок можна покращити, вводячи в число базисних одну з вказаних клітин (звичайно ту, для якої ). Розглянемо питання про те, яка з базисних клітин виводиться з числа базисних.

З клітин транспортної таблиці утворюємо цикл так, щоб він включав небазисну клітинку , а інші клітинки були б базисними. Можна довести, що в невиродженому випадку цикл будується однозначно. Відмітимо клітинки циклу наступним чином: небазисну – знаком “+”, інші (базисні) – знаком “–” або “+“, але так, щоб сусідні в рядку або стовпчику  клітинки мали  б різні знаки.

Таблиця 11.

Q1

Q2

Q3

Q4

ai

P1

3

5  –

2 +

10

P2

8 -

 + 7

15

P3

+

 –  7

7

bj

3

5

10

14

32

Клітина циклу: (3,2) – небазисна, а (1,2), (1,3), (2,3), (2,4), (3,4) – базисні.

Збільшимо тепер перевезення, що містяться в клітинках зі знаком “+”, на величину . а перевезення, що містяться в клітинах зі знаком “–”, зменшимо на ту ж саму величину . Щоб отриманий таким чином новий вектор  , був допустимим, потрібно, очевидно, вибрати   так, щоб , де мінімум береться по всіx i, j, що відповідають клітинкам зі знаком “–”. Якщо ж вибрати  то одна з старих базисних клітинок буде виведена з числа базисних . Замість неї базисною клітиною буде клітинка . Можна довести, використовуючи теореми 9.1 і 9.2, що вказана процедура приводить до нового базисного розв’язку ТЗ. При цьому значення цільової функції на сусідніх ітераціях зв’язані співвідношенням:

.

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

Неважко побачити, що

де l вміщує складові цільової функції, які не змінюються при переході від х до . Оскільки величини  відповідають базисним клітинкам, то для них виконується співвідношення: cij =vj -ui . Отже,

=

,

що й потрібно було довести. Відмітимо, що в невиродженому випадку  і тому . Таким чином , останній пункт метода потенціалів полягає в наступному:

4) За допомогою описаного вище процесу перерозподілу грузів по циклу, клітинка  вводиться в число базисних; а базисна клітинка  , яка входить в цикл та для якої  виводиться з числа базисних. Отриманий новий допустимий базисний розв’язок перевіряємо на оптимальність (пункт 2,3) і т. д., до тих пір поки не для деякого поточного базисного рішення не буде виконаний критерій оптимальності. Неважко побачити, що у невиродженому випадку (,  метод потенціалів приводить до оптимального рішення ТЗ за скінченне число кроків. Так само як і для довільної ЗЛП, при розв’язанні ТЗ у виродженому випадку в принципі можливе зациклення. Зауважимо, що у виродженому випадку в число базисних включають всі зайняті клітинки, а також необхідне число вільних (загальна їх кількість повинна дорівнювати m+n–1), але таким чином, щоб всі вказані клітинки не утворювали цикл.

  1.  Потоки на мережі. Умови існування потоку. Задача про найкоротший шлях. Задача про максимальний потік.
  2.  Оптимальні чисті стратегії у матричній грі. Теорема про міні-макс.
  3.  Диференціальні рівняння
  4.  Теорема існування та єдності розв’язку задачі Коші диференціального рівняння першого порядку.

Теорема. Якщо функція f(x,y) неперервна в області, яка містить точку Р(х0,у0), то рівняння y’=f(x,y) має розв'язок y=y(x), такий, що y(x0)=y0. якщо крім того, неповна похідна f/у, то цей розв'язок рівняння єдиний.

Як правило, твердження єдності доводиться методом від супротивного. Припустимо від супротивного, що задача Коші, крім розв'язку У(х) має і інший розв'язок Z(x), який задовольняє ті мамі початкові умови:

Y(x)=y0+xx0f(x,Y(x))dx

Y(x)|y0x=x0

Z(x)=y0+xx0f(x,Z(x))dx

Z(x)|y0x=x0

Розглянемо функцію |Y(x)-Z(x)|. Різниця неперервних функцій – неперервна. Розглянемо для >0 правосторонній окіл точки [x0,x0+]; так як функції Y(x)Z(x), то в цьому околі модуль їх різниці не дорівнює тотожньо нулеві.

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

Нехай max|Y(x)-Z(x)|x==Q [x0,x0+];

Q=|Y(x)-Z(x)|=| y0+x0f(x,Y(x))dx- y0+x0f(x,Z(x))dxN+x0x0|Y(x)-Z(x)|dxNQ.

Отримали суперечність з припущення, ми припускали, то - будь-яке, а отримали, що >1/n. Ця суперечність і доводить  єдинність розв'язку задачі Коші.

  1.  Лінійні однорідні диференціальні рівняння n-го порядку із сталими коефіцієнтами. Побудова загального розв’язку.
  2.  Знаходження частинного розв’язку лінійного неоднорідного рівняння n-го порядку за допомогою методу варіацій довільної сталої.
  3.  Системи лінійних диференціальних рівнянь. Формула Коші.
  4.  Лінійні диференціальні рівняння та їх розвязування методом Лагранжа та Бернуллі..
  5.  Теорія ймовірностей та математична статистика
  6.  Випадкові події та їх ймовірності.

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

Означення. Результат – елементарна подія ().

Означення. Всі елементарні події деякого досліду утворюють простір елементарних подій (, ).

Означення. Випадковою подією А називається підмножина елементарних подій простору ).

Приклад. ={герб, решка} – кидання монети.

Означення. Елементарні події, з яких складається  подія А, називаються сприятливими для події А.

Означення. Сумою двох випадкових подій називається така подія, яка складається з елементарних подій, які є сприятливими для події А або для події В (А+В={x|xAxB}).

Приклад.   - 36 гральних карти. А – „вийнята карта-козир”, |A|=9, В – „вийнята карта з картинкою”, |B|=16, А+В – вийнята карта-козир або з картинкою. |A+B|=21.

Означення. Добутком подій А і В називається подія, яка відбувається тоді і тільки тоді, коли відбуваються обидві події разом (АВ={x|xAxB}).

Означення. Різницею двох подій А і В називається подія, яка відбувається тоді і тільки тоді, коли відбувається подія А і не відбувається подія В(А-В={x|xAxB}).

Означення. Подія називається протилежною до події А, якщо А = і А+=.

Означення. Подія, яка внаслідок випробування обов’язково відбувається називається достовірною подією u (А+=u.).

Означення. Подія, яка ніколи не відбувається внаслідок випробувань називається незалежною подією v (А =v).

Означення. Події А і В називаються несумісними, якщо виконується умова АВ=v.

Означення. Події А1,...,Аn утворюють певну групу подій, якщо АіАj=v, а .

Інтуїтивне означення ймовірності. Ймовірність  - міра об'єктивної можливості випадкової події.

Класичне означення. Ймовірність події А рівна відношенню сприятливих для події А елементарних подій (m) до всіх можливих елементарних подій (n).

Р – імовірність. Р(А)=.

Властивості ймовірностей:

  1.  0<P(A)<1;
  2.  P(u)=1 – ймовірність достовірної події;
  3.  p(v)=0 – імовірність неможливої події.

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

Статистичне означення. Відносною частотою події А N(А) називається відношення числа випробувань М, в яких ця подія сталась, до загального числа випробувань N.

N(А)=.Відносна частота при необмеженому збільшені числа випробувань має властивість стійкості  Р(А)=.

Зауваження. Суттєва відмінність між класичним і статистичним означенням імовірності полягає в тому, що класичну ймовірність можна обчислити до досліду (apriori), а статистичну – після досліду (aposteriori).

Геометричне означення. Нехай в області  n-вимірного простору навмання беруть точку, ймовірність того, що ця точка попаде в область А=Р(А)= , - міра Лебега на просторі .

Аксіоматичне означення. Розглянемо простір симетричних подій. В цьому просторі зафіксуємо деяку непорожню систему підмножин з . S={A1,A2,…}, Ai.

Відносно структури системи S припустимо, що вона є -алгеброю (-алгебра – система об’єктів: АіS, i=, AiS; ASAS S), назвемо Аі-подіями.

І. АіSАіS;

ІІ.ASAS;

В цьому випадку S називається борелівським полем подій, для якого вводять аксіоми ймовірності:

1. для будь-якого  AS поставимо у відповідність р(А)0, яке назвемо ймовірністю;

2. якщо А1, А2,... попарно-несумісні події, то Р(Аі)= Р(Аі) – аксіома зчисленої адитивності;

3. p(u)=p()=1 імовірність достовірної події рівна 1;

Означення. Сукупність трьох об’єктів , S, р(А), де S задовольняє аксіоми (І-ІІ), а функція р(А) задовольняє (1-3) називається імовірнісним простором.

Зауваження. Вище наведена аксіоматика є аксіомами, які ввід Колмогоров.

  1.  Основні теореми теорії ймовірностей.

Теорема. Імовірність появи хоча б однієї з двох подій рівна сумі їх імовірностей без імовірності їх сумісної появи: р(А+В)=р(А)+р(В)-р(АВ).    (1)

Доведення. (за класичним означенням). Нехай подія А має m1 сприятливих подій (|A|=m1), |B|=m2, |AB|=m3, ||=n. P(A+B)= , m=|A+B|, = =Р(A)+Р(B)-Р(AB). (2)

Зауваження. Якщо АВ=vР(А+В)=Р(А)+Р(В).

Зауваження. Формули (1-2) можна узагальнити на довільну скінчену суму доданків: Р()=-+-...+(-1)n-1Р(A1,…,An); Р(Аі)= Р(Аі).

Зауваження. Р(А)=р, то р(А)=1-р.

Означення. Подія В називається незалежною від події А, якщо ймовірність події В не залежить від здійснення події А.

А      і      В

 

 

                                                           сумісні              несумісні

залежні     незалежні     залежні

Означення. Якщо події А і В залежні, то ймовірність події В при умові, що подія А відбудеться називається умовною ймовірністю (Р(А/В)).

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

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

Теорема. Імовірність сумісної появи двох подій рівна добутку ймовірностей однієї з них на умовну ймовірність іншої при умові, що перша відбувалася (Р(АВ)=Р(А)Р(В/А)=Р(В)Р(А/В)).

Зауваження. якщо події А і В незалежні, то Р(АВ)=Р(А)Р(В).

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

Р(А1,...,Аn)=Р(А1)Р(А21)Р(А31А2)…Р(Аn1...Аn-1).

Для незалежних подій зручно використовувати формулу:  Р(А1,...,Аn)=1-Р(А1) Р(А2)... Р(Аn).

Для незалежний подій зручно використовувати формулу: P(A1+…+An)=1-P(A1)…P(An).

  1.  Схема Бернуллі та її наближені формули.

Означення. Під схемою Бернуллі в теорії ймовірностей розуміють n раз підряд повторення одного і того ж досліду (випробування), який має два результати: успіх – подія А відбулася, невдача – подія А не відбулася, причому ймовірність успіху в кожному випробувані стала і не залежить від номеру випробування.

n, р – параметри схеми Бернуллі.

Імовірність того, що в n випробуваннях подія А відбулася m разів обчислюється за формулою Pn(m)=Cmnpmqn-m  (1), q=1-p – формула Бернуллі.

Означення. Імовірності Pn(m) називається біноміальними.

Права частина розкладу (1) (p+q)n=.

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

Імовірність того, що внаслідок n випробувань успіх відбудеться хоча б один раз обчислюється за формулою Pn(1mn)=1-qn.

Приклад. Що імовірніше виграти у рівносильного противника:

1. 3 партії з 4 чи 5 з 8

 .

Відмітимо, що спочатку біноміальні ймовірності зростають до певного m0, а потім спадають.

Означення. Число m0 називається найімовірнішим числом схеми Бернуллі. m0=[p(n+1)].

Якщо число p(n+1) – ціле, в схемі Бернуллі є два найімовірніших числа m0 i  m0-1.

  1.  Дискретна випадкова величина та її числові характеристики.

Означення. Кажуть, що задана дискретна випадкова величина , якщо вказана скінчена або злічена множина чисел х1,...,хn і кожному з них поставлено у відповідність число рі0, причому .

Означення. Числа хі називаються значеннями випадкової величини і, а рі – її випадковістю.

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

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

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

Випадкові величини також можна задати за допомогою функції розподілу.

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

Властивості функції розподілу:

  1.  0F(x)1;
  2.  P(axb)=F(b)-F(a) ;
  3.  F(x)F(x1) F(x2)x1x2;
  4.  F(x) – неперервна справа;
  5.  F(x)1, x+; F(x)0, x-;

. Математичне сподівання випадкової величини (М) – її середнє значення в імовірнісному сенсі. Математичне сподівання наближено рівне М==.

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

  1.  МС=С, де С – стала;
  2.  М(С)=СМ();
  3.  М(і)= М(і);
  4.  і – незалежні, M(і)=Мі.

Зауваження. М - це величина невипадкова.

Теорема. У схемі Бернуллі математичне сподівання рівне М=np, де n, p – параметри схеми Бернуллі.

Для дискретної випадкової величини математичне сподівання обчислюється за формулою М=хірі.

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

2. Дисперсія  випадкової величини (розсіювання) показує розсіювання значень випадкової величини відносно її середнього значення (D).

DM(-M)2=M(2-2M+(M)2)=M2-2M(M)+M((M)2)=M2-2(M)2+(M)2=M2-(M)2.

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

  1.  DC=0, C-const;
  2.  D(C)=C2D;
  3.  інезалежні, D(i)=Di.

Теорема. Дисперсія числа появ подій в схемі Бернуллі D=npq.

3. Середнє квадратичне відхилення випадкової величини =.

Зауваження. Якщо випадкову величину розглядати як систему матеріальних точок, дисперсія – це момент інерції відносно математичного сподівання.

  1.  Неперервна випадкова величина та її числові характеристики.

Означення. Випадкова величина називається неперервною, якщо її функція розподілу F(x) – неперервна на R.

Для неперервної випадкової величини та х0R має місце рівність Р(0)=0, а також P(axb)=F(b)-F(a), де F(x) – функція розподілу неперервної випадкової величини.

Означення. Кажуть, що неперервна випадкова величина F(x) розподільна з щільністю, якщо існує невід’ємна функція f(x)0, х0R, що F(x)=, при цьому f(x) називається щільністю ймовірності непевної випадкової величини , а її графік кривої – крива розподілу.

Властивості f(x):

  1.  f(x)0 (xR);
  2.  ;
  3.  F’(x)=f(x);
  4.  P(axb)= .

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

Формули для знаходження  цих характеристик наступні:

  1.  M=;
  2.  D=-(M)2;
  3.  =.
  4.  Випадкові вектори, розподіл функцій від випадкових аргументів.
  5.  Типи випадкових величин та їх  взаємозв’язок.
  6.   Граничні теореми теорії ймовірностей. Закон великих чисел.

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

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

-   перший був пов’язаний з динамікою поведінки середніх арифметичних

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

-   другій (центральні граничні теореми) - пов’язаний з теоремою Муавра – Лапласа (цей напрямок дозволив описати клас всіх розподілів, які можуть виступати в якості граничних для функцій розподілу сум незалежних випадкових величин, у випадку, коли кожним окремим доданком можна знехтувати).

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

Дана послідовність взаємно незалежних ВВ ξ1, ξ2,…, ξn…, які мають скінченні математичні сподівання  і дисперсії . Позначимо

.

Справедлива теорема (достатня умова Ліндерберга)

Теорема. Якщо послідовність взаємно незалежних ВВ ξ1, ξ2,…, ξn… для будь-якої сталої  задовольняє умові Ліндерберга

, то при  рівномірно по х

,

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

Наслідок. Якщо незалежні ВВ ξ1, ξ2,…, ξn… однаково розподілені і мають скінчену відмінну від 0 дисперсію, то при  рівномірно по х

.

  1.  Основні поняття та типи випадкових процесів.

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

Випадковий процес позначається X(t)=Xt(), , tT, де - простір елементарних подій.

Т – деяка числова множина.

Означення. При 0, Хt(0) називається реалізацією або траєкторією випадкового процесу.

При фіксованому t0, Xt0() – звичайна випадкова величина.

Відрізняють випадкові процеси з дискретними і непевними значеннями, з дискретним часом і непевним.

Випадковий процес вважається заданим, якщо для будь-якого набору параметра t, 0t1<t2<…<tn, tiТ, вказаний розподіл Ft1,…,tn(x1,…,xn)=P(X(t1))<x1X(t2)<…<xnX(tn), причому розподіли складових

Означення. Випадковий процес називається процесом із незалежними змінними, якщо для будь-якого набору  tt1<t2<…<tn випадкові величини X(t1),X(t2),…,X(tn) є незалежними.

У цьому випадку розподіл набуває вигляду  Ft1,…,tn(x1,…,xn)=Ft1(x1)Ft2(x2)…Ftn(xn).

Для випадкового процесу вводяться означення:

- математичне сподівання m(t)=MX(t), яке характеризує середні течії, навколо якої ґрунтується реалізація випадкового процесу;

- дисперсія 2=DX(t)=M(X(t)-m(t))2, яка характеризує розсіяння реалізації відносно течії випадкового процесу.

Зв’язок між випадковими величинами, які утворюють випадковий процесом характеризує кореляційна (автокореляційна) функція випадкового процесу. B(t,s)=M[X(t)-m(t))(X(s)-m(s)], а також нормована кореляційна формула (t,s)=.

Ці функції характеризують ступінь залежності випадкових величин випадкового процесу в моменти часу t і s.

Зауваження. Для процесів з незалежними значеннями B(t,s)=0, i (t,s)=0, ts.

  1.  Основні поняття та задачі математичної статистики. Вибіркове, параметричне та непараметричне оцінювання.

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

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

В математичній статистиці прийнято виділити два напрямки дослідження:

1. пов’язаний з оцінкою невідомих параметрів;

2. пов’язаний з перевіркою деяких апріорних припущень або статистичних гіпотез.

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

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

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

Основні поняття:

1. генеральна сукупність (вибіркова);

2. теоретична і емпірична функція розподілу; параметри та їх оцінки.

Означення. Припустимо, що маємо N об’єктів, кожному з яких притаманне певне значення числової характеристики . Сукупність цих N об’єктів називається генеральною сукупністю.

Таким чином генеральна сукупність – це N  чисел, серед яких можуть бути однакові.

Для того, щоб встановити параметри генеральної сукупності ми можемо провести n випробувань. Кожне випробування полягає в тому, що випадковим чином відбираємо один об’єкт генеральної сукупності і визначаємо його характеристику . Отриманий таким чином ряд чисел називається вибіркою об’єму n (x1,…,xn).

Вибірка повинна бути репрезентативною (представницькою), повинна відображати всі характеристики генеральної сукупності. Репрезентативність насамперед досягається за допомогою випадковості відбору. На практиці застосовують не випадкові методи відбору. Основними з них є:

1. механічний;

2. типовий;

3. серійний;

4. комбінований.

Також відрізняють схеми відбору: повторна і безповторна.

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

  1.  Чисельні методи
  2.  Елементи теорії метричних просторів. Принцип стискуючих відображень (теорема Банаха). Оцінка похибки методу послідовних наближень.
  3.  Наближене розв’язування нелінійних рівнянь. Умови існування та єдиності коренів. Локалізація коренів. Уточнення коренів. Методи простої ітерації, хорд, дотичних (Ньютона). Достатні умови збіжності.

 Відокремлення коренів нелінійних рівнянь

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

Нехай дано рівняння , де  – неперервна функція на інтервалі .

Коренем або розв’язком рівняння  називається будь-яке число , яке перетворює це рівняння в тотожність .

Рівняння може не мати коренів на , може мати один корінь або може мати декілька коренів. При наявності коренів виникає задача їх відокремлення.

Корінь рівняння називається відокремленим (ізольованим), якщо для нього визначено окіл, який не містить інших коренів цього рівняння.

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

Процес числового знаходження коренів нелінійного рівняння  складається з двох етапів:

1) відокремлення коренів;

2) обчислення коренів з наперед заданою точністю .

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

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

Відокремлення коренів проводять графічно чи аналітично.

Графічне відокремлення коренів.

Універсальним методом визначення інтервалів, на яких розміщені корені є побудова графіка функції  за допомогою ЕОМ. Точки перетину графіка з віссю OX дають значення коренів рівняння по яких наближено визначаємо інтервал ізоляції – числа .

Аналітичне відокремлення коренів.

Аналітична локалізація коренів нелінійного рівняння  базується на теоремі Больцано-Коші: Якщо неперервна на відрізку  функція  приймає на кінцях цього відрізка значення різних знаків, тобто , (1)

то всередині цього відрізка міститься хоча б один корінь рівняння .

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

На практиці аналітичний метод локалізації коренів нелінійного рівняння  використовують у такому вигляді:

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

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

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

Нехай  – точний корінь, а  – його наближене значення. Кажуть, що корінь  обчислено з наперед заданою точністю , якщо . Нехай, наприклад,  і , тоді числа a і b – наближенні значення кореня  відповідно із недостачею і надлишком з точністю . У цьому випадку за наближене значення  з точністю  можна взяти будь-яке число з відрізка .

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

На практиці уточнення наближених значень коренів нелінійних рівнянь проводять такими наближеними методами: метод ділення навпіл (який ще називають методом дихотомії або бісекції), метод хорд, метод Ньютона (який ще називають методом дотичних), метод простої ітерації, метод верхньої та нижньої релаксації та інші.

Метод ділення навпіл

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

Обчислення виконують за такою схемою.

Ділимо відрізок  пополам  і замінюємо його тією половиною, яка містить корінь:

якщо , то ;

якщо , то

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

Такий ітераційний процес збігається із швидкістю геометричної прогресії із знаменником , тобто  

Кількість ітерації, потрібних для виконання нерівності

є

Основний недолік методу – повільна збіжність.

Метод простої ітерації

Запишемо рівняння  у вигляді . Метод простої ітерації визначається формулою ,

де  - номер ітерації;  - початкове наближення.

Якщо послідовність  має границю , то ця границя є коренем рівняння .

Достатні умови збіжності методу ітерацій випливають з принципу стискаючих відображень:

  1.  якщо  визначена на  і відображає  в себе;
  2.  для неї виконується умова Ліпшиця: 

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

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

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

.

Метод Ньютона

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

Якщо у розвиненні рівняння  в околі точки

,де , ,  – точне значення кореня, відкинути останній доданок і замінити  на , то отримаємо рівняння вигляду .

Розв’язавши його відносно , дістанемо , , (4.1)

Формула (4.1) визначає метод Ньютона, який ще називають методом лінеаризації або методом дотичних. Як бачимо метод Ньютона є методом простої ітерації , де функція

. (4.2)

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

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

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

Для оцінки похибки припустимо, що .

Тоді за теоремою Лагранжа отримаємо  

або врахувавши, що  –  (4.3) З іншої сторони, за формулою Тейлора  , ,

звідки будемо мати (4.4)

Враховуючи (4.4), із (4.3) отримаємо  (4.5)

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

Оцінка (4.5) є апостеріорною, а тому зручною для застосування і свідчить про високу швидкість збіжності методу Ньютона. З формули (4.2) видно, що чим більше значення  в околі кореня, тим менша поправка додається до попереднього наближення. Тому, метод Ньютона зручно застосовувати тоді, коли в околі кореня графік функції  має значну крутість. Недоліком методу є складність вибору початкового наближення.

Метод січних

Недоліком методу Ньютона є те, що на кожній ітерації потрібно обчислювати не тільки значення функції , а й значення її похідної . Обчислення похідної  може бути значно складнішим від обчислення . У таких випадках похідну  замінюють її наближеним значенням . (4.6)

Підставивши значення  (4.6) у формулу методу Ньютона (4.1), знайдемо

,  . (4.7)

Формула (4.7) визначає метод січних.

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

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

Метод хорд

Метод хорд – один із поширених ітераційних методів. Його ще називають методом лінійного інтерполювання, методом пропорційних частин, методом хибного положення.

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

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

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

Для виведення формули методу хорд запишемо рівняння прямої, що проходить через точки  та : .

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

Значення  можна взяти за наступне наближення, тобто

.

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

Отже, метод хорд можна записати так:  ,

де

  1.  Арифметичні методи розвязування системи лінійних алгебраїчних рівнянь (СЛАР). Метод послідовного виключення невідомих Гауса та його модифікації.

Знаходження коренів систем лінійних алгебраїчних рівнянь (СЛАР) – одна з математичних задач, яка часто зустрічається як в інженерній, так і в науковій практиці.

Розглянемо СЛАР вигляду , де А – квадратна матриця розмірності , b – заданий вектор, х – шуканий вектор. Система  у розгорнутій (покомпонентній) формі має вигляд:

З лінійної алгебри відомо, що за умови , ця система має єдиний розв’язок, який можна знайти за правилом Крамера, проте застосування цього правила для розв’язування цієї системи є надзвичайно трудомістким.

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

Методи розв’язування СЛАР можна поділити на дві групи: точні й ітераційні.

Точними називаються такі методи, які дають змогу знайти точний розв’язок СЛАР за допомогою виконання скінченої кількості арифметичних операцій у припущенні, що всі обчислення виконуються точно (без заокруглень), а коефіцієнти системи і вільні члени – точні числа. Але на практиці всі обчислення виконуються з обмеженою кількістю десяткових розрядів, а ірраціональні коефіцієнти і вільні члени, якщо такі є, замінюються раціональними числами. Тому в процесі обчислень вдаються до округлень, а це означає, що розв’язки, які обчислюються за точними методами, фактично є наближеними числами з певними похибками (похибками округлень). До точних методів належать правило Крамера, метод Гаусса, метод квадратних коренів, метод прогонки тощо.

Ітераційними називають такі методи, які дають змогу знайти наближений розв’язок С,ЛАР із заздалегідь указаною точністю шляхом виконання скінченої кількості арифметичних операцій, хоч самі обчислення можуть проводитися і без округлень, а коефіцієнти системи і вільні члени бути точними числами. Точний розв’язок СЛАР за допомогою ітераційних методів можна знайти лише теоретично як границю збіжного нескінченного процесу. Розв’язуючи СЛАР ітераційними методами, крім похибок округлення, потрібно враховувати також похибку методу. До ітераційних належать метод ітерації, метод Якобі, метод Зейделя тощо.

Вираз  називається нев’язкою, і завжди може бути обчисленим. Нев’язка дає нам порядок точності знаходження коренів СЛАР.

Метод Гаусса для розв’язування СЛАР

Розглянемо метод розв’язування СЛАР

(1)

який вперше був опублікований німецьким математиком Гауссом.. Систему (1) запишемо у вигляді , де А – квадратна матриця розмірності , b – заданий вектор, х – шуканий вектор.

Основна ідея методу Гаусса полягає у зведенні почаккової системи рівнянь (1) до еквіавлентної їй системи з трикутною матрицею, що є прямим ходом методу виключення. зворотній хід. Далі, із одержаної системи невідомі знаходяться шляхом послідовної підстановки невідомих, це є зворотнім ходом.

Розглянемо цей алгоритм детальніше.На першому кроці систему (1) еквівалентними

перетвореннями зведемо до вигляду:    прямий хід

далі цю систему знову еквівалентними перетворенннями зводимо до вигляду:

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

(2)

Щоб виключити  і дістати систему (2), виконаємо над i-рядком таке перетворенння :

новий і-рядок = старий і-рядок - -рядок, де  і називається головним елементом ,а к-рядок – головним рядком.

Таким чином знайдемо послідовність матриць де

В загальному випадку для  виконуємо кроки виключення за формулами:

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

Перехід від  до  можна записати у матричному вигляді:

де нижня трикутна матриця

називається матрицею Фребеніуса.

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

Отже, ми довели систему  до , де , при R є верхньою трикутною матрицею, а , L – уніпотентною, тобто нижньою трикутною матрицею, з одиницями на головній діагоналі. Розвинення матриці А у вигляді  називається трикутним розвиненням Гаусса, або LR – розвиненням матриці А

Модифікації методу: Алгоритм методу виключення Гаусса, Алгоритм методу Гаусса з вибором головного елементу

  1.  Ітераційні методи розв’язування СЛАР. Метод простої ітерації; метод Зейделя. Достатні умови збіжності.

Ітераційні методи характеризуються тим, що розв’язок СЛАР знаходиться у вигляді границі деякої послідовності векторів, які будуються за однаковим ітераційним процесом. Перевагою ітераційних процесів є те, що при побудові наступного наближення враховується попереднє. Недоліком є те, що ітераційний процес має обмежену область застосування, може виявитися розбіжним для даної системи або збіжність буде дуже повільною, не дозволить досягти потрібної точності. Ефективність ітераційних методів визначається швидкістю збіжності послідовних наближень  до розв’язку . Член цієї послідовності  називається k-ою ітерацією, а kномером ітерації.

Ітераційний процес у канонічній формі для системи  (1) описується за допомогою схеми :

(2)

де додаються матриці  і початкове наближення .

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

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

Ітераційний метод називається збіжним, якщо для деякої норми має місце рівність .

Щоб зупинити обчислення, задають деяке число , яке є характеристикою похибки і обчислення припиняють, коли .

Вираз  називається нев’язкою, і завжди може бути обчисленим. Нев’язка дає нам порядок точності знаходження коренів СЛАР.

Для зручності формувань лінійний однокроковий ітераційний метод записують у канонічній формі:

(3)

де  – деякі числові параметри. Якщо матриця , то метод (3) називається явним.

Метод простої ітерації розв’язування СЛАР

Цей метод має вигляд(4) де  вибирається довільно. Метод простої ітерації є явною однокроковою стаціонарною схему із сталим параметром . У координатній формі (4) має вигляд де параметр .

Метод простої ітерації збігається коли .

Метод простої ітерації зручно застосовується до тих СЛАР, в яких діагональні коефіцієнти перевищують інші коефіцієнти невідомих.

Метод Зейделя

Досить поширений на практиці метод і застосовується в одній із двох форм :

(5)

або

(6)

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

для форми (5) і за формулами

для форми (6).

Метод Зейделя відповідає однокроковій стаціонарній схеми з .

Теорема :

Якщо , то метод Зейделя збігається. .

  1.  Інтерполяція функцій. Інтерполяційний многочлен Лагранжа. Оцінка залишкового члена у формі Лагранжа.

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

Задача інтерполювання ставиться таким чином: за заданим , знайти наближене значення функції  як значення в точці  узагальненого многочлена  такого, що . Многочлен , який задовольняє останню умову, називається інтерполяційним многочленом для функції  або інтерполюючою функцією. Точки  називають вузлами інтерполювання. Наближену заміну функції  многочленом  називають інтерполюванням або інтерполяцією, а формулу , за допомогою якої обчислюють значення функції  – інтерполяційною формулою.

Таким чином, щоб розв’язати задачу інтерполювання потрібно:

  1.  побудувати інтерполяційний многочлен;
  2.  обчислити його значення в точці .

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

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

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

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

Інтерполяційний многочлен у формі Лагранжа

Узагальнений інтерполяційний многочлен для функції  можна подати у вигляді

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

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

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

(1)

Інтерполяційний многочлен, записаний у вигляді (1) називається інтерполяційним многочленом у формі Лагранжа.

Тоді, .

Недоліком є те, що для обчислення  при фіксованому  потрібно виконати  арифметичних операцій.

  1.  Інтерполяція функцій на початку та в кінці таблиці. Інтерполяційні многочлени Ньютона-1 вперед та Ньютона-2 назад.
  2.  Апроксимація функцій многочленами найкращого наближення (МНН). Метод найменших квадратів для побудови МНН.
  3.  Чисельне інтегрування функцій. Квадратурні формули прямокутників, трапецій, Сімпсона. Оцінка похибки квадратурних формул.
  4.  Наближене розв’язування звичайних диференціальних рівнянь. Різницеві методи для задачі Коші для лінійних ЗДР: схема Ейлера, модифікована схема Ейлера, схема Ейлера-Коші.

Постановка задачі Коші.

Нехай на відрізку  потрібно знайти розв’язок диференціального рівняння n-того порядку  (1)

який у точці набуває заданих початкових значень  (2)

Ця задача називається задачею Коші для рівняння (1). Достатньою умовою існування та єдності її розв’язку є неперервність функції f по всіх аргументах і виконання умови Ліпшиця по змінних  

Оскільки більшість методів розв’язування задачі Коші для рівняння першого порядку

(3)

майже без змін переносяться на системи, то з метою спрощення викладок розглядатимемо методи розв’язання задачі Коші (3).

Розглянемо нелінійний оператор А, який діє за правилом

Тоді задачу Коші (3), розв’язок якої шукається на проміжку можна записати у вигляді нелінійного операторного рівняння .                                                  

Вихідними даними задачі (3), або те саме, що задачі  є початкове значення та права частина рівняння , тобто функція .

Задача (3), має бути коректно поставленою , тобто мають виконуватися умови :

  1.  вона має єдиний розв’язок;
  2.  цей розв’язок неперервно залежить від вихідних даних, тобто “малі” збурення вхідних даних викликають “малі” збурення розв’язку.

Умову (2) називають умовою стійкості . Достатньою умовою розв’язання рівняння (3) є неперервність функції  і виконання умови Ліпшиця по y.

Метод Ейлера.

Проінтегруємо рівняння (3)  (6)

Інтеграл у правій частині (6) замінюється тим чи іншим наближеним виразом.

Метод Ейлера полягає у тому, що при обчисленні по одному наближеному значенню  знаходять наступне значення  і інтеграл у рівнянні (6) замінюєтья добутком похідних підінтегральної функції на крок   (7)

Зображення методу Тейлора функції  в околі точки :

де . Якщо похідна обмежена, а крок  малий. То останній   доданок можна відкинути і наближено написати

Геометричний зміст методу Ейлера полягає в апроксимації розв’язку на відрізку  відрізком дотичної, проведеної до графіку розв’язку у точці .

Помилка при  показана у Вигляді відрізка .

Метод Ейлера дуже простий для реалізації на ЕОМ: на к – кроці обчислюється значення , яке потім підставляється у (7). Таким чином, всі необхідні операції зводяться до обчислення . Знайдений таким чином наближений розв’язок має перший порядок точності, оскільки він узгоджується з розвиненням у ряд Тейлора до членів порядку h включно.

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

Метод Ейлера - Коші.

У методі Ейлера – Коші ми знаходимо середній тангенс кута нахилу дотичної для двох точок  і  Остання точка – це точка, яка у методі йлера позначалася як . Геометрично процес знаходження точки  зображено на рисунку. За допоьогою метода Ейлера знаходиться точка , лежить на прямій .

У цій точці знову визначається тангенс кута нахилу дотичної . Знайдене середнє значення

Двох тангенсів дає пряму. Далі через точку проводимо пряму L паралельну . Точка у якій пряма L перетнться із прямою  і буде шуканою точкою .Тангенс кута нахилу прямої L становить:(8) де   (9)

Тоді рівняння лінії L запишеться у вигляді  тому .(10)співвідношення (8)-(10) описують метод Ейлера – Коші.

Функцію  розвинемо у ряд Тейлора:

Підставляючи  одержимо

Підставляючи цей результат у (8) дістанемо

Підставивши це у (10) матимемо

Отже, метод Ейлера-Коші є методом другого порядку.

Модифікований метод Ейлера.

Усереднимо точки іншим чином. Розглянемо рисунок, де через точку  проведено пряму  з тангенсом кута нахилу, що дорівнює .Візьмемо точку на пертині прямої з прямою . Координати цієї точки . Тангенс кута нахилу дотичної

(11)

де  (12)

В результаті одержимо пряму . Проведемо через точку  пряму L паралельну до L0. Перетин цієї прямої з прямою  дає шукану точку .Рівняння прямої L запишемо у вигляді  Тому             (13)

Співвідношення (11) - (13) описують  модифікований метод Ейлера. Аналогічно можна показати, що це є метод другого порядку.

  1.  Зведення крайових задач для лінійних ЗДР 2-го порядку до СЛАР. Метод сіток. Метод прогонки для тридіагональних СЛАР.

Метод сіток розв‘язування крайових задач.

Розглянемо таку крайову задачу

,       

,       (10)

 ,

, , , .

Використовуючи формулу (7) для другої похідної та формули (5) і (1) для першої похідної в граничній умові у точці a та формули (6) і (2) - для першої похідної в граничній умов у точці b на рівномірній сітці  дістанемо таку схему для розв‘язання задачі (10):

 ,

 ,     (11)

 .

Таким чином, ми отримали систему лінійних алгебраїчних рівнянь порядку n+1 з невідомими  , .

Тут  , .

Отже, за допомогою заміни похідних різницевими схемами ми звели крайову задачу (10) до розв‘язання системи лінійних алгебраїчних рівнянь (11).

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

Першу похідну можна апроксимувати так:

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

, (6) і т.д.

Другу похідну можна апроксимувати теж:

  1.  центральна друга похідна  ,      (7)
  2.  права друга різницева похідна  ,      (8)
  3.  ліва друга різницева похідна  ,      (9)

Можливі її інші формули апроксимації другої похідної.

  1.  Ріхницеві схеми для рівнянь із сталими коефіцієнтами.
  2.  Ріхницеві схеми для рівнянь із змінними коефіцієнтами.
  3.  Ріхницеві схеми для рівнянь еліптичного виду.
  4.  Економічні різницеві схеми для задач математичної фізики.
  5.  Проекційні та варіаційні методи розв’язуванняеліптичних рівнянь.
  6.  Чисельне розв’язування інтегральних рівнянь.

  1.  Інформаційні системи та бази даних
  2.  Інформаційні системи. Поняття файлових систем і систем з БД..
  3.  Архітектура баз даних та їх типи. Моделі даних.
  4.  Реляційна модель даних. Властивості відношень. Операції реляційної алгебри.
  5.  Нормалізація відношень. І та ІІ нормальні форми. Функціональні залежності.
  6.  ІІІ нормальна форма. Нормальна форма Бойса – Кодда.
  7.  Основні оператори. мови SQL стандарту ISO.
  8.  Системне програмування
  9.  Функції та структура операційної системи. Завантаження операційної системи.

Операційна система (ОС) – це програма, яка виконує функції посередника між користувачем і комп’ютером.

ОС, виконує роль посередника і служить двом цілям:

1 ефективно використовує комп’ютерні ресурси;

2 створює умови для ефективної роботи користувач

У якості ресурсів комп’ютера зазвичай розглядають:

1 час роботи процесора;

2 адресний простір основної пам’яті;

3 засоби введення/виведення;

4 файли, які зберігаються у зовнішній пам’яті

На мал. 3.2. і мал. 3.3. зображені основні компоненти ОС, як системи розподілу ресурсів.

Таким чином, основні компоненти ОС:

1 керування процесами (розподіляє ресурс – процесорний час);

2 керування пам’яттю (розподіляє ресурс – адресний простір);

3 керування пристроями (розподіляє ресурси – обладнання введення/виведення);

4 керування даними (розподіляє ресурс – дані або файли).

Функціонування комп’ютера після вмикання живлення починається із запуску програми початкового завантаження – Boot Track. Програма Boot Track ініціалізує основні апаратні блоки комп’ютера і регістри процесора (CPU), накопичувач пам’яті, контролери периферійного обладнання. Потім завантажується ядро ОС, тобто Operating System Kernel. Подальше функціонування ОС здійснюється як реакція на події, які відбуваються у комп’ютері. Настання тієї або іншої події сигналізується перериваннями – Interrupt. Джерелами переривань можуть бути як аппаратура (HardWare), так і програми (SoftWare).

Аппаратура “повідомляє” про переривання асинхронно (у будь-який момент часу) шляхом пересилання в CPU через спільну шину сигналів переривань. Програма “повідомляє” про переривання шляхом виконання операції System Call. Приклади подій, які викликають переривання:

1 спроба ділення на нуль;

2 запит на системне обслуговування;

3 завершення операції введення/виведення;

4 неправильне звертання до пам’яті.

Кожне переривання обробляється відповідно обробником переривань (Interrupt handler), який входить до складу ОС.

Головні функції механізму переривань – це:

1 розпізнавання або класифікація переривань;

2 передача керування відповідно обробнику переривань;

3 коректне повернення до перерваної програми.

Перехід від перерваної програми до обробника і назад повинен виконуватись якнайшвидше. Одним із швидких методів є використання таблиці, яка містить перелік всіх дозволених для комп’ютера переривань і адреси відповідних обробників. Така таблиця називається вектором переривання (Interrupt vector) і зберігається на початку адресного простору основної пам’яті (UNIX/MS DOS).

Для коректного повернення до перерваної програми перед передачою керування обробнику переривань, вміст регістрів процесора запам’ятовується або в пам’яті з прямим доступом, або у системному стеку – System Stack.

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

  1.  Розподіл та управління ресурсами. Управління процесором.

Управління процесами Процес - це програмний модуль, який виконується в CPU. Операційна система контролює наступну діяльність, пов'язану з процесами:

1. створення і видалення процесів

2. планування процесів

3. синхронізація процесів

4. комунікація процесів

5. розв’язування тупикових ситуацій

Поняття про процес. Стан процесу. Не треба змішувати поняття процес і програма. Програма - це план дій, а процес - це сама дія. Поняття процес включає:

1. програмний код

2. дані

3. вміст стека

4. вміст адресного та інших регістрів CPU.

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

Розрізнюють наступні стани процесу (мал.3.4.):

1. новий (new, процес щойно створений)

2. виконуваний (running, команди програми виконуються в CPU)

3. очікуваний (waiting, процес чекає завершення деякої події, частіше за все операції введення - виведення)

4. готовий (readly, процес чекає звільнення CPU)

5. завершений (terminated процес завершив свою роботу)

  1.  Управління пам’яттю. Невіртуальна та віртуальна пам’ять. Базові принципи організації невіртуальної та віртуальної пам’яті

Метод Multiprogramming with а Variable number of Tasks передбачає розділення пам'яті на розділи і використання завантажувальних модулів в переміщуваних адресах, однак, межі розділів не фіксуються.

Як випливає із малюнка, у початковій фазі відсутня фрагментація, пов’язана з тим, що розмір чергового процесу менший розміру, займаного цим процесом розділу. На цій фазі причиною фрагментації є невідповідність розміру чергового процесу і ділянки пам'яті, яка залишилася.  По мірі завершення роботи програми звільняються окремі розділи. У тому випадку, коли звільняються суміжні розділи, межі між ними видаляються і розділи об'єднуються. Мал7.

Мультипрограмування з змінними розділами та ущільненням пам’яті Зрозуміло, що метод Multiprogramming with а Variable number of Tasks породжує в пам'яті безліч малих фрагментів, кожний з яких може бути недостатній для розміщення чергового процесу, однак сумарний розмір фрагментів перевищує розмір цього процесу.

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

На практиці реалізація ущільнення пам'яті пов'язана з ускладненням операційної системи і має наступні недоліки:

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

2. під час ущільнення всі прикладні програми переводяться в стан "очікування", що приводить до неможливості виконання програм у реальному масштабі часу. Мал8.

Основні стратегії заповнення вільного розділу Розглянуті методи мультипрограмування передбачають наявність вхідної черги/черг до розділів основної пам'яті.

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

1. стратегія найбільш відповідного (best fit strategy) вибирає процес, якому у звільненому розділі, найтісніше (виграш у пам'яті).

2. стратегія першого відповідного (first fit strategy) вибирає перший процес, який може розмістити у звільненому розділі.

3. стратегія найменш відповідного (last fit strategy) вибирає процес, якому у звільненому розділі, найвільніше (у цьому випадку фрагмент, який залишається часто достатній для розміщення ще одного процесу).

Сторінкова організація пам’яті Сторінкова організація пам'яті (paging) відноситься до методів несуміжного розміщення процесів в основній пам'яті.

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

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

Кожна адреса, яка генерується процесором, складається з двох частин: P - номер сторінки (page number) і D - зміщення в межах сторінки (of set). Номер сторінки може використовуватися як індекс для таблиці сторінок (page table). Мал9.

Таблиця сторінок містить початкові адреси f всіх сторінкових рамок, в яких розміщена програма. Фізична адреса визначається шляхом складання початкової адреси сторінкової рамки f і зміщення D. Мал10.

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

Для прискорення обчислення фізичного адреси операцію додавання замінюють операцією конкатенації.мал11.

На малюнку заштриховані незаповнені нульові розряди. Для того, щоб операція конкатенації була можлива, необхідно, щоб базові адреси сторінкових рамок розташовувалися тільки в старших розрядах (2n+1), а наступні - тільки молодших розрядах (20 , 2 1, 2 2 ).

Наприклад, при n=9 базові адреси сторінкових рамок - це наступний ряд: 512, 1024, 1536. Отже, розмір сторінкової рамки дорівнює 512 байт.

У сучасних операційних системах типовий розмір сторінки становить 2 Кб або 4 Кб.

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

Апаратна підтримка сторінкової організації пам’яті Перетворення логічної адреси в фізичні здійснюється для кожної адреси, генерованої процесором, тому часто для прискорення цього процесу застосовуються. (мал12.) апаратні методи. На малюнку  приведена схема, яка ілюструє метод, що використовує асоціативні регістри (associative registers).

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

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

Захист сторінкової пам'яті базується на контролі рівня доступу до кожної сторінки, можливі наступні рівні доступу:

1. тільки читання

2. і читання і запис

3. тільки виконання

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

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

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

Базовий метод сегментної організації пам'яті мал13. Завичай сегменти формуються компілятором, а на етапі завантаження їм присвоюються ідентифікуючі номери. Таким чином, логічна адреса при сегментній організації пам'яті складається з двох частин: S і d, де S - номер сегмента, а d - зміщення в межах сегмента. Трансформація логічної адреси у фізичний здійснюється за допомогою таблиці сегментів (segment table).

Кількість рядків таблиці сегментів дорівнює кількості сегментів програми: S, limit, base. Limit - розмір сегмента, base - початкова адреса сегмента в пам'яті.

Номер сегмента S використовується як індекс для таблиці сегментів. За допомогою таблиці сегментів визначається його початкова адреса base в основній пам'яті. Значення limit, використовується для захисту пам'яті. Зміщення d повинно задовольняти нерівності 0<d<limit. У разі виходу зміщення за межі сегмента робота програми припиняється. Фізична адреса визначається як сума початкової адреси base і зміщення d. У тому випадку, коли таблиця сегментів має значні розміри, вона розташовується в основній пам'яті, а її початкова адреса і довжина зберігаються в спеціальних регістрах STBR (segment table base register), STLR (segment table length register). Для прискорення трансформації логічної адреси у фізичну операція додавання часто замінюється операцією конкатенації (для цього необхідно, щоб початкові адреси сегментів були кратні деякому числу 2n ). Таблиця сегментів (або її частина) розташовується в асоціативній пам'яті.

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

Розділення сегмента між декількома процесами мал14. Оскільки сегмент є логічно завершеним програмним модулем, він може використовуватися різними процесами. Сегмент називається розподілюваним, коли його початкова адреса і розмір вказані у двох і більш таблицях сегментів. Наприклад, два процеси можуть використати підпрограму Sqrt, яка зберігається у вигляді однієї фізичної копії. На малюнку (вище) приведений приклад, який ілюструє використання розподілюваного текстового редактора.

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

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

Сегментація і сторінкування використовується в операційних системах OS/2 для управління комп'ютерами.

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

Сторін кування по запиту (DEMAND PAGING). Віртуальна пам'ять частіше за все реалізовується на базі сторінкової організації пам'яті, суміщеній зі своппінгом сторінок.

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

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

2. у процесі виконання нова сторінка не переміщається в основну пам'ять доти,  поки в ній не виникла необхідність.

Для обліку розподілу сторінок між зовнішньою і основною пам'яттю кожний рядок таблиці сторінок доповнюється бітом місцезнаходження сторінки Valid/invalid bit. Мал15.

У тому випадку, коли процесор намагається використати сторінку, помічену значенням invalid, виникає подія, названа сторінкова недостатність (paging fault).

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

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

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

2. якщо значення біта invalid, то процес переривається і управління передається операційній системі для обробки події сторінкова недостатність.

3. розшукується необхідна сторінка у повторній пам'яті і вільна сторінкова рамка в основній.

4. необхідна сторінка завантажується у вибрану сторінкову рамку.

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

6. управління передається перерваному процесу.мал16.

Зауваження 1: метод сторінкування по запиту дозволяє почати виконання процесу навіть у тому випадку, коли жодна сторінка цього процесу не завантажена в основну пам'ять.

Зауваження 2: повторна пам'ять, яка використовується при сторінкуванні за запитом - це високошвидкісний дисковий пристрій, часто званий swap - обладнанням (device), а частина використовуваного дискового простору - swap - простір (swap space).

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

Метод заміщення сторінок означає, що в основній пам'яті вибирається найменш важлива/використовувана сторінка, називається сторінка - жертва (victim page), яка тимчасово переміщається в swap page, а на її місце завантажується сторінка, яка викликається сторінковою недостатністю.

Обробка сторінкової недостатності з урахуванням заміщення здійснюється по наступному алгоритму:

1. визначається місцезнаходження сторінки шляхом аналізу біта місцезнаходження;

2. якщо значення біта invalid, то розшукується вільна сторінкова рамка;

2.1. якщо є вільна сторінкова рамка, то вона використовується;

2.2. якщо вільної сторінкової рамки немає, то використовується алгоритм заміщення, який вибирає сторінку - жертву.

2.3. сторінка - жертва переміщається в swap space і редагується таблиця сторінок;

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

Управління передається перерваному процесу. Приведений алгоритм заміщення вимагає двосторінкових переміщень.

1. сторінка - жертва переміщається у swap space.

2. необхідна сторінка переміщається у звільнену сторінкову рамку.

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

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

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

1. алгоритм розподілу сторінкових рамок (from allocation algorithm).

2. алгоритм заміщення сторінок (page replacement algorithm).

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

Алгоритм заміщення сторінок вирішує, яку із сторінок вибрати як жертву.

FIFO. Найбільш простим алгоритмом заміщення сторінок є алгоритм FIFO. Цей алгоритм асоціює з кожною сторінкою час, коли ця сторінка була вміщена в пам'ять. Для заміщення вибирається найбільш стара сторінка.

Облік часу необов'язковий, коли всі сторінки в пам'яті пов'язані в FIFO-чергу, а кожна сторінка, яка вміщується в пам'ять додається у хвіст черги. Мал17. Алгоритм враховує тільки час знаходження сторінки в пам'яті, але не враховує ступінь використання сторінки. Наприклад, перші сторінки програми можуть містити змінні, використовувані протягом роботи всієї програми. Це приводить до негайного повернення до щойно заміщеної сторінки.

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

LRU - алгоритм (LEAST RECENTLY USED)Алгоритм вибирає для заміщення ту сторінку, на яку не було посилання протягом найбільш довгого періоду часу. Least recently used асоціює з кожною сторінкою час останнього використання цієї сторінки. Для заміщення вибирається та сторінка, яка довше за всіх не використовувалася. Цей алгоритм найчастіше використовується у системах сторінкування за запитом. Зазвичай застосовується два підходи при впровадженні цього алгоритму.

1. підхід на основі логічного годинника (лічильника).

2. підхід на основі стека номерів сторінок.

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

2. стек номерів сторінок зберігає номери сторінок, впорядкованих відповідно до історії їх використання, на вершині стека розташовується щойно використана сторінка, а на дні least recently used сторінка. Як тільки здійснюється посилання на сторінку, вона переміщається на вершину стека, а номери всіх сторінок зсуваються вниз.

  1.  Управління файловою системою. Файлова система DOS, UNIX, WINDOWS 2000.

Базові поняття При розгляді файлів використовуються наступні поняття.

  •  Поле.
  •  Запис.
  •  Файл.
  •  База даних.

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

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

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

База даних (database) є набором зв'язаних між собою даних. До найбільш істотних аспектів бази даних можна віднести те, що відношення між даними виражені явно, а сама база даних спроектована спеціально для використання великою кількістю різних додатків. Зазвичай існує окрема система керування базою даних (СУБД), незалежна від операційної системи, але, проте, вона майже завжди використовує деякі програми керування файлами.

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

  •  Вибрати_Усі. Вибір всіх записів з файлу. Ця операція необхідна тим додаткам, що обробляють всю інформацію, яка міститься у файлі, цілком. Наприклад, додаток, що здійснює аналіз інформації у файлі, повинен вибрати для цього всі записи. Цій операції часто відповідає термін послідовна обробка, оскільки доступ до всіх записів здійснюється в послідовному порядку.
  •  Вибрати_0дин. Вибір тільки одного запису. Використовується діалоговими додатками, орієнтованими на виконання транзакцій.
  •  Вибрати_Наступний. Вибір запису, що є "наступним" у деякій логічній послідовності стосовно останнього раніше обраного запису. Ця операція буде необхідна, наприклад, додаткам із заповненням форм. Її можуть використовувати і додатки, що виконують пошук.
  •  Вибрати_Попередній. Подібна тільки що розглянутої операції, однак у цьому випадку вибирається запис, що є "попередньої" стосовно доступного в даний момент запису.
  •  Уставити_0дин. Вставка запису у файл. Може бути необхідна, якщо новий запис поміщається у визначену позицію для збереження логіки зв'язків між записами файлу.
  •  Видалити_0дин. Видалення існуючого запису. Для збереження логіки зв'язків між записами файлу може виникнути необхідність у відновленні деяких зв'язків або інших структур даних.
  •  Оновити_0дин. Вибір запису, відновлення одного або більш його полів і перезапис оновленого запису назад у файл. Ця операція також може зажадати виконання додаткових дій для збереження послідовності файлу. Якщо довжина запису змінилась, то процедура відновлення стає більш складною.
  •  Вибрати_Декілька. Вибір деякої кількості записів. Виконується, наприклад, коли додатку або користувачу необхідно вибрати записи, які задовольняють визначеному встановленому набору критеріїв.

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

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

  •  Відповідність вимогам керування даними і вимогам з боку користувачів, що включають можливість збереження даних і виконанні розглянутих раніше операцій з ними.
  •  Гарантування коректності даних, що містяться у файлі.
  •  Оптимізація продуктивності, як з погляду системи (пропускна здатність), так і з погляду користувача (час відповіді).
  •  Підтримка вводу/виводу для різних типів пристроїв збереження інформації.
  •  Мінімізація або виключення можливих втрат або ушкоджень даних.
  •  Забезпечення стандартизованого набору підпрограм інтерфейсу вводу/виводу.
  •  Забезпечення підтримки колективного використання декількома користувачами багатокористувацької системи.

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

  1.  Створювати, видаляти, читати і змінювати файли.
  2.  Мати контрольований доступ до файлів інших користувачів.
  3.  Керувати доступом до своїх файлів.
  4.  Реструктуризувати файли таким способом, який найбільше підходить для розв’язування задач, що поставлені перед ним.
  5.  Переміщати дані між файлами.
  6.  Резервувати і відновлювати файли у випадку ушкодження.
  7.  Мати доступ до файлів по символьних іменах.

Файлова система Windows 2000 Windows 2000 (W2K) підтримує кілька файлових систем, включаючи FAT, що підтримується Windows 95, VS-DOS і OS/2. Однак розробники W2K спроектували нову файлову систему, W2K File System (NTFS - дана файлова система успішно застосовувалася в Windows NT, відкіля і перейшла в W2K), що призначена для задоволення високих вимог робочих станцій і серверів. Прикладами додатків такого рівня можуть служити:

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

Ключові можливості NTFS NTFS є гнучкою і могутньою файловою системою, яка як ми побачимо, побудована на простій і елегантній моделі. До найбільш достойних уваги особливостей NTFS відносяться наступні.

• Здатність відновлення даних. Першою в списку вимог до нової файлової системи W2K була здатність відновлення даних при повній відмові системи і збоях дисків. У таких випадках NTFS здатна реконструювати дискові томи і повернути їх до погодженого стану. Це досягається за допомогою використання моделі обробки транзакцій для операцій обміну у файловій системі; кожен значний обмін розглядається як атомарна дія, що або виконується цілком, або не виконується зовсім. Крім того, NTFS використовує надлишкове збереження критичних даних файлової системи.

• Безпека. Для забезпечення безпеки NTFS використовує об'єктну модель W2K. Відкритий файл реалізується як файловий об'єкт із дескриптором, що визначає атрибути безпеки.

• Диски і файли великих обсягів. NTFS підтримує дуже великі диски і файли більш ефективно в порівнянні з іншими файловими системами, включаючи FAT.

• Множинні потоки даних. Вміст файлу розглядається як потік байтів. У NTFS можна визначити кілька потоків даних для одного файлу. Прикладом використання цієї особливості служить використання W2K віддаленими системами Macintosh для збереження й отримання файлів. У комп'ютерах Macintosh кожен файл складається з двох компонентів: даних файлу і гілки ресурсу, яка містить інформацію про файл. NTFS розглядає ці компоненти як два потоки даних.

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

Том NTFS і файлова структура NTFS використовує наступні концепції дискового збереження.

• Сектор. Найменша одиниця фізичного збереження на диску. Розмір даних у байтах є ступенем двійки і майже завжди дорівнює 512 байт.

• Кластер. Один чи кілька послідовних секторів на одній доріжці. Розмір кластера в секторах є ступенем двійки.

• Том. Логічний розділ диска, який складається з деякої кількості кластерів і використовуваний файловою системою для розподілу простору. У будь-який момент часу том складається з інформації файлової системи, набору файлів і нерозподіленого простору, що залишився в томі, який може бути виділено файлам. Том може займати як весь диск, так і його частину або охоплювати кілька дисків. При використанні RAID 5 тім складається зі смуг, що охоплюють кілька дисків. Максимальний розмір тому NTFS складає 264 байт.

Кластер є фундаментальною одиницею розміщення у файловій системі NTFS, що не розпізнає сектори. Припустимо, наприклад, що розмір кожного сектора складає 512 байт і. що система набудована так, що в одному кластері містяться по двох сектора (один кластер = 1 Кбайт). При створенні користувачем файлу розміром 1600 байт файлу приділяються два кластери. Якщо згодом користувач обновляє файл і він збільшується до 3200 байт, то йому виділяються ще два кластери. Кластери, виділювані файлу, не обов'язково повинні утворювати безупинний блок; у NTFS допускається фрагментація файлу на диску. В даний час максимальний розмір файлу, підтримуваний NTFS, складає 232 кластерів, що еквівалентно максимум 248 байт.

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

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

Таблиця 13.3. Розділи NTFS і розміри кластерів

Розмір тому

Кількість секторів у кластері

Розмір кластера

( 512 Мбайт

512 Мбайт – 1 Гбайт

1 Гбайт – 2 Гбайт

2 Гбайт – 4 Гбайт

4 Гбайт – 8 Гбайт

8 Гбайт – 16 Гбайт

16 Гбайт – 32 Гбайт

> 32 Гбайт

1

2

4

8

16

32

64

128

512 Кбайт

1 Кбайт

2 Кбайт

4 Кбайт

8 Кбайт

16 Кбайт

32 Кбайт

64 Кбайт

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

Рис. 13.2. Схема тому NTFS

На мал. 13.2 показана схема тому NTFS, що складається з чотирьох областей. Перші кілька секторів будь-якого тому займає завантажувальний сектор розділу (незважаючи на назву, розмір цієї області може бути до 16 секторів), який містить інформацію про схему тому і структурах файлової системи, а також початкова завантажувальна інформація і код завантаження. За цією областю слідує головна файлова таблиця (master file table - MFT), що містить інформацію про усі файли і папки (каталоги) цього тому NTFS, а також інформацію про вільний простір. По суті, MFT є списком усього вмісту тому NTFS, організований у вигляді множини рядків у структурі реляційної бази даних.

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

  •  MFT2. Дзеркальне відображення перших трьох рядків MFT, використовуваних для гарантованого доступу до MFT у випадку збою одного сектора.
  •  Системний журнал. Список кроків транзакцій, використовуваний при відновленні даних у NTFS.
  •  Бітова карта кластерів. Представлення тому, що указує використовувані кластери.
  •  Таблиця визначення атрибутів. Визначає типи атрибутів, підтримуваних у цьому томі, і показує, чи можуть вони бути проіндексовані, а також чи можуть вони бути відновлені під час системної операції відновлення.

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

Кожен запис MFT складається з набору атрибутів, які служать для визначення характеристик файлу (чи папки), а також для визначення вмісту файлу. У табл. 13.4 перераховані атрибути, що можуть знаходитися в рядку MFT (обов'язкові атрибути виділені темним фоном).

Таблиця 13.4. Типи атрибутів файлів і каталогів у Windows NTFS

Тип атрибуту

Опис

Стандартна інформація

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

Список атрибутів

Список атрибутів, що складають файл, і посилання на інший запис MFT, у якому розміщені атрибути. Використовується, коли всі атрибути не поміщаються в один запис MFT

Ім'я файлу

Файл (чи каталог) повинний мати одне або декілька імен

Дескриптор безпеки

Визначає власника файлу і користувачів, яким дозволений доступ до файлу

Дані

Вміст файлу. Файл містить один неіменований атрибут даних за замовчуванням, і може мати один або декілька іменованих атрибутів даних

Кореневий індекс

Використовується для реалізації папок

Розміщення індексу

Використовується для реалізації папок

Інформація про том

Включає інформацію, яка відноситься до тому, наприклад версія й ім'я тому

Бітова карта

Карта, яка представляє записи, використовувані MFT або каталогом

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

• Диспетчер введення/виведення. Включає драйвер NTFS, який обробляє основні функції NTFS - відкриття і закриття файлу, читання, запис. Крім того, може використовуватися програмний модуль RAID (FTDISK).

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

• Диспетчер кеш-пам'яті. Відповідає за кешування читання і запису файлів для поліпшення продуктивності. Диспетчер кеша оптимізує дисковий введення/виведення шляхом використання методів відкладеного запису і відкладеного підтвердження.

• Диспетчер віртуальної пам'яті. NTFS звертається до кешованих файлів шляхом відображення файлових посилань у посилання віртуальної пам'яті і читання і записи віртуальної пам'яті.

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

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

Загалом ці етапи такі:

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

2. NTFS модифікує том (у кеш-пам'яті).

3. Диспетчер кеш-пам'яті скидає системний журнал на диск.

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

  1.  Розподіл пам’яті ПЕОМ. Базова система вводу – виводу. Область даних BIOS. Переривання. Таблиця векторів переривань.

  1.  Організація виводу на монітор (прямий доступ до відео ОЗУ, засоби ОС та BIOS).
  2.  Клавіатура. Організація вводу з клавіатури. Буфер клавіатури.
  3.  Послідовний та паралельний порти. Доступ до послідовного та паралельного портів засобами ОС та BIOS.
  4.  Зовнішні накопичувачі. Організація віртуального диску. Робота з файлами та файловою системою засобами ОС та BIOS.
  5.  Програмування
  6.  Етапи розробки прикладних програм.

1. Постановка задачі.

2. Опис математичної моделі.

3. Розв’язок математичної моделі.

4. Побудова алгоритму розв’язку.

5.

6. Програмна реалізація.

7. Відлагодження програми. (Способи: верифікація, доведення правильності)

8. Документування(коментарі, описи)

9. Промислова експлуатація.

  1.  Поняття алгоритму. Види алгоритмів. Властивості алгоритмів. Способи реалізації алгоритмів.

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

Види: Детерміновані, недетерміновані(наступний крок не визначений однозначно наперед).

Реалізація:

  •  Послідовна обробка даних;
  •  Повторювана обробка (ітерація(цикли), рекурсія).
  •  Паралельна обробка;
  •  Структурне розгалуження при допомозі співпроцесора;
  •  Довільна обробка.

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

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

  точність - кожна команда алгоритму має визначити однозначну дію виконавця;

  зрозумілість - алгоритм, складений для конкретного виконавця, має включати тільки ті команди, які входять у його систему команд;

  скінченність - виконання алгоритму має завершитися за скінченну кількість кроків;

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

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

  1.  постановки задачі;
  2.  наявними програмними ресурсами;
  3.  вимогами по швидкодії, використанням ресурсів ЕОМ.

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

  1.  Мови програмування та їх класифікація.

Мова програмування – це знакова система представлення алгоритму для подальшої трансляції мов машинних кодів для виконання процесів.

Мова має алфавіт та синтаксис.

Мови поділяються на:

  •  Мови низького рівня;
  •  Мови середнього рівня;
  •  Мови високого рівня;

Інший спосіб поділу:

  •  Імперативні (процедурні(Паскаль, С), ОО(С++, Делфі), візуальні)
  •  Декларативні (предикатні( Пролог), функціональні (Лісп)).
  1.  Типізація даних в мовах програмування. Скалярні та структуровані типи даних.

Скалярні / прості / стандартні типи даних:

  •  Цілі або цілочисельні типи
  •  Дійсні типи
  •  Логічні типи
  •  Символьний тип - CHAR.
  •  Перелічувальний тип
  •  Інтервальний тип

Структуровані типи даних:

  •  Регулярні (Масиви, рядки, множини)
  •  Комбіновані (записи, структури, об’єднання)
  •  Файлові (типізовані, текстові, безтипові)
  •  Вказівні або покажчики
  •  Процедурні або функціональні
  •  Класи і об’єкти.

BOOLEAN (булевий тип). Цей тип має всього два значення: FALSE (хибна), TRUE (істина).

В пам’яті логічний тип займає 1 байт.

Символьний тип - CHAR.  Всього є 256 символів, що кодуються байтовими значеннями від 0 до 255. Перші 128 символів, що відповідають від 0 до 127 є так званою основною частиною таблиці ASCII.  Вона містить 32 командних символи від 0 до 31. Ці символи не мають зображення і використовуються для передачі команд в системі ЕОМ. Вони вводяться за допомогою комбінацій клавіш. Входять: 52 англійські букви, 10 арабських цифр і 34 символи розділових знаків. Останні 128 символи утворюють альтернативну частину таблиці, яка містить символи національних алфавітів та псевдографіки.

Скалярні типи користувача:

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

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

Порядкові типи даних:

Із шести розглянутих скалярних типів п’ять мають такі спільні властивості:

Кількість елементів типу є фіксована і визначена наперед.

Всі значення впорядковані за зростанням.

За їх природою між двома сусідніми немає жодного проміжного.

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

Структуровані типи даних:

Регулярні типи – масиви.  Масиви – структури даних, які є об’єднанням в одне ціле деякої фіксованої кількості однотипних елементів. Оголошуються масиви за допомогою службового слова array, після якого вказується розмір масиву, кількість елементів, а також тип самих елементів масиву.

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

В ранніх версіях Pascal рядки навіть оголошувалися як масиви( упорядковані масиви символів).

Регулярний тип – множини. Множини і тип даних теж відносяться до регулярних складених типів. Це означає, що елементи таких структур даних будуть однотипні значення (цілі числа, символи, перелічувальні типи). На відмінну від масивів, де кількість елементів є фіксованою і незміною, множини можуть змінювати свій склад, проте кількість елементів не може перевищувати деякого фіксованого значення. І масиви, і рядки можуть мати декілька однакових елементів, у множині всі елементи різні.

Комбіновані структури даних.

Записи. Масиви, рядки, множини давали складені структури даних, елементи яких були одного і того ж типу. Кількість елементів в них могла б бути різною. В масивах фіксованою, в рядках і множинах могла б змінюватися, але тип був би спільним. Часто виникає проблема у формування структур даних, елементи яких мають різний тип. Для цього були створені записи..

Записи з варіантами. Часто бази даних повинні містити інформацію, структура якої залежить від значень окремих полів. Для реалізації таких комбінованих типів використовуються записи із варіантними частинами.

  1.  Скалярні типи даних та операції над ними.

Скалярні / прості / стандартні типи даних:

  1.  Цілі або цілочисельні типи

В Pascal є 5 типів цілих чисел. Поділ на ці типи пов’язаний із діапазоном допустимих значень і розміром комірок пам’яті.

Тип

Діапазон

Розмір в байтах

byte

0..255

1

shoting

-128..127

1

integer

-32768..32767

2

word

0..65535

2

longint

-2147483648..2147483647

4

Над цілими числами виконуються 4 операції:
ціле + ціле = ціле
ціле * ціле = ціле
ціле – ціле = ціле
ціле / ціле = дійсне

Також використовуються 2 операції:
Div, mod – результат цілий.
Необхідно відзначити, що, при виході значень даних цілого типу за вказаний діапазон, помилки виконання програми не виникає, але результат при цьому буде неправильний. Наприклад, при виконанні додавання чисел 32767+1 отримаємо результат - -32768.

  1.  Дійсні типи

B Pascal є 5 типів дійсних чисел. Поділ на ці типи визначається розміром у пам’яті, а отже, діапазоном допустимих значень.

Тип

Діапазон

Розмір в байтах

real

2.9*E-39..1.7*E38

11

single

1.5*Е-45..3.4*Е38

7

double

5.0*Е-324..1.7*Е308

15

extended

3.4*Е-4932..1.1*Е4932

19

comp

-2*Е63..2*Е63-1

19

Над дійсними числами використовують +, -, *, /, операції порівняння.

В програмі дійсні числа можуть задаватися у двох формах: з фіксованою десятковою крапкою та з плаваючою

У випадку фіксованої крапки запис числа має чотири частини.
[знак] ціле. ціле.
Плаваюча крапка.
[знак] мантиса Е [знак] порядок.
Мантиса є фактично записом числа з фіксованою крапкою без знака. Положення десяткової крапки визначається порядком в записі числа.

По замовчуванню мантиса числа вибирається в межах 1<=мант <10.

  1.  Логічні типи

BOOLEAN (булевий тип).

Цей тип має всього два значення:
FALSE (хибна), TRUE (істина).
В пам’яті логічний тип займає 1 байт.

False<True.

Над логічними величинами можна виконувати логічні операції.

X

Y

or

and

xor

true

true

true

true

false

false

false

false

false

false

true

false

true

false

true

false

true

true

false

true

  1.  Символьний тип - CHAR.

використовують всі символи стандарту ASCII (American Standard Code for Information Interchange).

Всього є 256 символів, що кодуються байтовими значеннями від 0 до 255.

Перші 128 символів, що відповідають від 0 до 127 є так званою основною частиною таблиці ASCII.

Вона містить 32 командних символи від 0 до 31. Ці символи не мають зображення і використовуються для передачі команд в системі ЕОМ. Вони вводяться за допомогою комбінацій клавіш.

Входять: 52 англійські букви, 10 арабських цифр і 34 символи розділових знаків.

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

Символи в Pascal можуть записуватися або явно, за допомогою пари апострофів (‘a’, ‘G’), або через його код (#64 (A)). Код символа може задаватися в 10-вій і в 16-вій формах.

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

Над символьними типами виконуються операції приведення символів, що дозволяють по коду визначити символ, або навпаки.

CHR (<код>) – визначення символа за кодом;

ORD (<символ>) – визначення коду символа.

5.Прелічуваний.

6. Інтервальний

  1.  Способи структурування даних: масиви, рядки, множини, записи, файли.

Масиви – структури даних, які є об’єднанням в одне ціле деякої фіксованої кількості однотипних елементів. Оголошуються масиви за допомогою службового слова array, після якого вказується розмір масиву, кількість елементів, а також тип самих елементів масиву.
TYPE<ідентифікатор типу >= ARRAY[<діапазон індексів>,<діапазон індексів >,…] OF<тип елементів > ;

В якості діапазонів індексів можуть викликатися інтервали одного із дискретних типів, крім longint.

Кількість діапазонів визначає розмірність масиву:

1 діапазон – одновимірний масив; 2 діапазони – двовимірний ( таблиці, матриці);
n діапазонів – n-вимірний.

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

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

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

Структура даних, елементи якої є символами у Pascal є рядки символів. По способу організації і розміщення у пам’яті подібні до масивів. Їх відносять до однієї групи складених типів – регулярних.

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

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

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

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

При роботі із окремими елементами рядка слід пам’ятати, що цей елемент матиме типу char і для окремих стандартних підпрограм, що працюють з рядками він буде незастосовний.

Зауваження Рядок з одного символу і окремий символ типу char не одне і теж.

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

Об’єднання (конкатенація). Конкатенація – приєднання одного рядка в кінець іншого.

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

Оголошення множини, при доповненні стандартних слів set of, після яких вказується ідентифікатор елементів множини. В якості базових типів можуть бути лише порядкові типи і кількістю елементів до 256. це цілі byte, shorting, символи char, логічні boolean.

Масиви, рядки, множини давали складені структури даних, елементи яких були одного і того ж типу. Кількість елементів в них могла б бути різною. В масивах фіксованою, в рядках і множинах могла б змінюватися, але тип був би спільним. Часто виникає проблема у формування структур даних, елементи яких мають різний тип.

Під величини в пам’яті відводиться, розмір якого дорівнює сумі розмірів кожного поля.

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

Файлові змінні  Розглянуті раніше способи структурування даних мають суттєвий недолік: після завершення роботи програми всі дані пропадають в оперативній пам’яті, крім цього обмеження розміру статичної частини оперативної пам’яті, де зберігаються всі змінні, які обмежені в програмі ( менше 64 кбайт), накладається обмеження на кількість структурованих даних.

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

Файли – пойменовані ділянки пам’яті, які містять деякі дані.

Традиційно файли зберігаються на дисках – дискові файли. Файли можуть розміщуватися в оперативній пам’яті на віртуальних дисках.

В програмі файли представляються спеціальними змінними – файловими. Ця змінна є свого роду буфером між конкретним файлом на диску, з яким вона зв’язана, і програмою.

Одна і та ж змінна може бути зв’язана із різними файлами, але не одночасно.

В залежності від способу структурування даних в Pascal відрізняють три види файлів і файлових змінних:

  •  Типізовані.
  •  Текстові.
  •  Безтипові.

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

Наприклад. Файл дійсних чисел є послідовністю елементів із шести байт, що відповідають дійсним числам.

Файл цілих чисел – послідовність двобайтових чисел.

Файл записів – послідовність структур, що відповідають певному комбінованому типу. Наприклад 321 байт.

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

Текстові файли можна вважати файлами ASCII-форматами. Особливістю є те, що послідовність розбивається на рядки спеціальними комбінаціями символів (end, old, line).

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

Встановлюючи та завершальні операції над файлами

Перед використанням операції над файлом, він повинен бути відкритим.

Читання, запис, до запис в кінець. Після завершення операції із файлом для звільнення для файлової змінної його потрібно закрити.

Вид та тип файла визначається типом файлової змінної, що представляє файл.

  1.  Оператори мов програмування: порожній; присвоєння; вводу-виводу; складений; умовний; оператори циклу.

  Оператор присвоєння присвоює змінній значення виразу, в якості якого може використовуватися і константа, і змінна, і результат обрахування функції, і група операцій. Оператор має вигляд: <змінна>:=<вираз>;

Змінна – величина, значення якої змінюється в процесі виконання програми.

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

Тип результату виразу повинен співпадати із типом змінної або вужчим за нього.

Виконання цього оператора здійснюється cправа наліво: спочатку обчислюється результат виразу, здійснюється перевірка відповідності типів, здійснюється занесення в ділянку пам’яті, де розміщена змінна відповідного значення.

  Складений оператор. Якщо потрібно деяку групу команд інтерпретувати як одну команду, тобто об’єднати їх в певному контексті, то використовують складені оператори.
BEGIN<оператор1> ;<оператор2>... ; END;

Вони є послідовністю операторів, що обмежуються операторними дужками. Вкінці кожного оператора ставиться крапка з комою. Перед еnd – не обов’язково.

Саме завдяки складеним операторам вдається скласти програму без використання goto.

  Пустий оператор. Програма виду begin end є синтаксично правильною. Розділ операторів містить один оператор – пустий (він нічого не виконує). Наявність пустого оператора в мові викликана деякими різними причинами, які пов’язані з використанням безумовного переходу goto.

Наявність крапки з комою перед end означає, що перед ним ще є один пустий оператор. Він потрібний в таких випадках: якщо має здійснюватися безумовний перехід по мітці на кінець вкладеного оператора, то ця мітка повинна відмічати пустий оператор, а не слово end.
<мітка> : <пустий оператор> END;

  Оператори вводу-виводу. В мові програмування Turbo Pascal ввід-вивід здійснюється насправді не операторами, а стандартними підпрограмами - процедурами вводу-виводу, якщо вважати виклик підпрограми як оператор виклику підпрограми, то в цьому розумінні можна вважати відповідні процедури операторами. Під пристроєм вводу-виводу розуміється сукупність наступних компонентів ЕОМ: клавіатура, монітор, порти для під'єднання цих пристроїв.

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

Для реалізації розгалуження використовують оператор розгалуження.
IF <логічний вираз> THEN <оператор 1> ELSE <оператор 2>;

Логічний вираз може набувати одного із значень true або false. Якщо результат true, то виконується оператор 1, якщо false – оператор 2.

В якості операторів 1,2 виконується один оператор, якщо він дійсно один, або складений оператор об’єднаний операторними дужками begin, end.

  Оператори циклу.

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

FOR <параметр>:=<початкове значення> TO <кінцеве значення> DO <оператор тіла циклу>;

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

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

Тіло циклу складається з 1 оператора, якщо він 1, або є складеним оператором в операторних дужках.

Цей оператор циклу ще називають оператором циклу з параметром for to, він передбачає повторення із збільшенням параметру. Оскільки в Turbo Pascal не можна керувати кроком зміни параметра, то для реалізації повторення із зменшенням параметра використовують інший варіант циклу for downto.

FOR<параметр> : = <початкове значення> DOWNTO <кінцеве значення> DO <тіло циклу>;

Після виконання кожного етапу циклу параметр зменшується на 1 одиницю типу.

Зауваження. У випадку необхідності вийти з тіла циклу достроково, тобто до досягнення параметру кінцевого значення не бажано користуватися оператором безумовного переходу, а також аналітичним йому підпрограм типу exit, halt(1).

Для виконання виходу краще змінити значення параметру в тілі циклу.

  •  Оператор циклу з передумовою. Якщо кількість повторень деякої послідовності команд алгоритму не є визначеною наперед, або повторення повинні припинитися у різних випадках, то оператор циклу з параметром не завжди дозволяє виконати це. Також можливі ситуації, коли алгоритм взагалі не оперує якимось параметром, а повторення продовжується до певної логічної умови. В таких випадках використовується інший варіант циклу. Фактично їх два. Один із них називається циклом з передумовою.
    WHILE <логічний вираз> DO <тіло циклу> ;

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

Очевидно, що тіло циклу повинно містити якісь дії, що приводять до зміни логічного виразу від true до false.

  •  Оператор циклу з післяумовою. Цикл з передумовою передбачає спочатку перевірку, а потім виконується. Деколи потрібно навпаки, спочатку виконати дію, а потім перевірити результат. Якщо результат незадовільняє, то повторити відповідні дії.
    REPEAT <тіло циклу> UNTIL <логічний вираз> ;

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

Не потрібно об’єднувати тіло циклу операторними дужками.

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

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

CASE<параметр> OF

<значення1> : <оператор1>;

<значення2> : <оператор2>;

...
<значення n> : <оператор n>

END
ELSE <оператор n+1> ;

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

Значення 1, 2... – деякі можливі значення відповідного порядкового типу, яких може набувати параметр. В залежності від значень параметра виконується один з операторів.

Якщо реальне значення параметра не співпадає ні з жодним значенням, то виконується альтернативна частина else. Оскільки вона не обов’язкова, то її відсутність означає не виконання жодної дії.

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

  1.  Підпрограми процедури і функції. Механізм передачі параметрів у підпрограмах. Формальні і фактичні параметри. Локальні і глобальні змінні.

Структурне програмування передбачає представлення програм у вигляді послідовності викликів підпрограм. В свою чергу останні теж можуть структуруватися на елементарні підпрограми.

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

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

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

В Pascal є два види підпрограм:

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

Механізм передачі параметрів

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

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

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

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

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

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

  1.  Файловий тип даних. Типізовані, текстові, безтипові файли. Файли прямого та послідовного доступу.

  1.  Вказівний тип даних. Динамічні змінні. Динамічні структури даних – списки.

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

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

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

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

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

Об'єкт, на який вказує вказівник, розміщується поза зв'язаного з програмою сегменту даних в динамічно розподіленій області пам'яті. Кожний з таких об'єктів може займати по 64 Кб. Сам вказівник розміщується в сегменті даних і займає два слова.

Значеннями вказівників є чотирибайтні числа, проте це не є числа типу longint. Адреса являє собою комбінацію із 2-х 2-байтних цілих чисел. Одне із цих чисел є адресою початку сегменту в пам'яті, друге число – зміщення відповідної комірки пам'яті від початку сегменту.

Початково оперативна пам'ять ЕОМ вимірювалася десятками Кбайт, тому всі програми, які виконувалися були обмежені за розміром.

З середини 80-х теоретично обґрунтовано і практично реалізовано використання 1 Мб пам'яті, при цьому постала проблема неможливості подальшого розширення її.

Через пару років використовували, крім основної пам'яті (1 Мб) – додаткову та розширену пам'ять, проте базова пам'ять залишається в межах 1 Мб і саме в ній починають виконуватися більшість програмних робіт.

Всі комірки пронумеровані від нуля до деякого кінцевого значення, що в 16-вій системі координат .

Звичайно при програмуванні не зручно користуватися адресами, що визначаються числом, розміром 2,5 байта.

Звуження до 2 байт дало б пам'ять 65536, а розширення до 3-х дало б пам'ять більшу ніж можна було б зробити на той час (більше ніж 4 мільярди – 4 Гб). Тому для адресації 1 Мб пам'яті вирішили умовно розділити її на окремі сегменти, причому сегменти могли перекривати один одного і розмір міг бути різним, але не більше 65536, це зроблено тому, що в межах сегменту можна користуватися для адреси 2-хбайтними числами.

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

Тепер для збереження адреси початку сегменту нема потреби використовувати п’ять 16-вих цифр, а лише чотири, а останній 0 завжди зберігається в пам'яті. Таким чином, для збереження повної адреси байта у пам'яті, використовується 2 2-хбайтних числа: адреса сегменту із 4-х цифр та зміщення байту в межах сегменту. Повна адреса обчислюється як сума
XXXX0 адреса
+XXXX зміщення
................................
ZZZZZ повна адреса.

Наприклад Пам'ять – вулиця з деякою кількістю рядків 0 – 9999. замість того, щоб користуватися 4-значними числами, квартири умовно розміщуються в будинках по 100 квартир з нумерацією від 0 до 99. повний номер квартири визначається за формулою .
1234=12*100+34.
35 квартира з номером 34 у 13 будинку з номером 12.

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

Хоча всі вказівники - це адреси, проте вказівники на різні базові типи є несумісними.

Застосування вказівників дозволило реалізувати особливий вид змінних – динамічних.

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

Статичні змінні - це всі змінні, що оголошені в розділі var незалежно від типу. Ці змінні розміщуються в спеціальному сегменті пам'яті, що називають статичною пам’яттю або програмним стеком (не більше 64 Кб). Ці змінні слідують в порядку оголошення у програмі. Вони з'являються на початку виконання програми і стек звільняється при завершені програми.

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

Динамічні змінні розміщуються в особливій частині оперативної пам'яті, що називається динамічною пам’яттю, або Heap-областю, або кучею. Під кучу відводиться вся вільна на момент виконання програми пам'ять. Враховуючи, що перших 360 Кб базової пам'яті займає ОП, то максимальний розмір буде 640 Кб.

Реально всі програми, які виконуються паралельно із Pascal-програмою теж частково використовують оперативну пам'ять.

Всі динамічні змінні створюються виключно спеціальними командами, так само вони і знищуються.

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

  1.  Файли розміщуються в зовнішній пам'яті, а динамічні структури в оперативній.
  2.  Типізовані файли фактично є файлами прямого доступу, що означає довільний доступ до елементів. В динамічних структурах доступ до елементів виключно послідовний.

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

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

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

В залежності від кількості вказівних полів в кожному елементі списку, розрізняють однозв’язні списки (один вказівник) n-зв’язні списки (n вказівників) .

Крім такого поділу по зв’язності, списки бувають лінійними, деревами, графами та ін.

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

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

  1.  Модульний принцип організації програм. Структура модуля. Видимість об’єктів модулів. Роздільна компіляція модулів.

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

В ранніх компіляторах мови Turbo Pascal з'явилася перша можливість розділення програм на окремі модулі, при цьому в модулях зосереджувалися окремі компоненти мови, що пов'язувалися спільними властивостями.

Ці модулі окремо компілювалися і були доступними для всіх програм; це були свого роду бібліотеки інструментів мови програмування.

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

З розвитком мов програмування з'явилися бібліотеки динамічної компоновки.

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

Результатами компіляції є файл, компоненти якого готові до виконання. Такі файли мають розширення *.tpu (Turbo Pascal Unit). Всі модулі, що використовуються однією програмою або іншими модулями повинні бути оголошені
USES <ім'я модуля>;

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

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

Компіляція модуля повинна здійснюватися не у пам'яті, а на диск у вигляді *.TPU-файла. Це можна здійснити, вибравши відповідний пункт меню інтегрованої оболонки та підпункт Destination disk (по замовчуванню Best nation memory). Після цього компіляція буде здійснюватися на диск у вигляді типового файла.

Компільований модуль може бути підключений до будь-якої програми, при цьому він має бути в тому самому каталозі звідки запускається інтегрована оболонка turbo.exe, або в підпункті directories.

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

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

  Заголовок, починається службовим словом unit (модуль), після якого обов'язково ім'я модуля
UNIT <ім'я модуля>;

На відмінну від програм, заголовок модуля є обов’язковим. Ім'я модуля повинно співпадати з іменем відповідного *.pas-файлу, що містить текст модуля. Ім'я модуля не перевищує 8 букв.

  Інтерфейс на частина.

В розділі інтерфейс оголошуються всі компоненти модуля, структура яких і самі вони мають бути „видимими” зовнішнім програмам, що використовують цей модуль.

В інтерфейсі можуть оголошуватися: uses- специфікація всіх модулів, що використовуються даним модулем; константи; типи; мітки; змінні; заголовки підпрограм. Всі перелічені компоненти будуть доступними, тобто „видимими” іншим програмам.

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

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

  Розділ реалізації. В реалізації описуються всі компоненти мови, які мають бути невидимі зовні.

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

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

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

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

Розділ ініціалізації обмежується операторними дужками. Якщо модуль не містить жодної ініціалізації змінних, то слово begin може бути відсутнім.

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

Видимість ідентифікаторів у модулях

Часто виникає ситуація, коли деякий модуль А використовується в програмі Р, в свою чергу модуль А використовує ресурси іншого модуля В, а той в свою чергу користується модулем С, крім цього кожен з модулів С, В, А і сама програма Р можуть містити оголошення деяких навіть різних компонентів, але з одним іменем. Якщо має місце таке вкладене використання модулів, то як правильно оголосити uses- специфікацію в кожному модулі і програмі, а також як отримати доступ до однойменних об’єктів різних рівнів. Для цього потрібно користуватись такими правилами:

  1.  Якщо програма явно користується ресурсами модуля А (не явно, тобто через ресурси модуля А) ресурсами модуля В. Модуль А явно використовує модуль В і неявно (тобто через модуль В) використовує модуль С і т. д. То в uses- специфікації потрібно вказувати всі модулі, які використовуються явно або неявно, причому у порядку, який є зворотним до порядку вкладення модулів. Таким чином матимемо оголошення:
  2.  Якщо в декількох модулях і програмах є однойменні об’єкти, то доступним вважається той з об’єктів, який, або оголошений в поточному модулі, або у першому по-порядку в uses- специфікації з право наліво, якщо у поточному модулі чи програмі його оголошення відсутнє.
  3.  При вкладеному включені модулів з однойменними об'єктами можна отримати доступ до будь-якого з них при доповнені складеного ідентифікатора.
  4.  При включені вкдадених модулів потрібно уникати взаємних звертань між декількома модулями.
  5.  Об’єктно-орієнтоване програмування. Поняття класу, об’єкта.

Об'єктно-орієнтоване програмування (ООП) - це новий підхід до програмування. По мірі розвитку обчислювальної техніки і ускладнення вирішувальних задач виникли різні моделі програмування. Перші компілятори підтримували процедурну модель програмування, в основі якої лежить використання функцій. Використовуючи процедурну модель програмування, програмісти могли писати програми до декількох тисяч рядків довжиною. Наступний етап розвитку зв'язаний з переходом до структурної моделі програмування. Зміст структурного програмування полягає в представлені програми у вигляді сукупності взаємопов'язаних процедур і тих даних, якими ці процедури оперують. При цьому широко використовуються програмні блоки і допускається тільки мінімальне використання оператора GOTO. Супровід таких програм простіший, чим процедурно-орієнтованих. Використовуючи структурне програмування, середній програміст може створювати і супроводити програми до декількох десятків тисяч рядків.

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

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

  1.  Об’єктно-орієнтоване програмування. Інкапсуляція. Наслідування. Поліморфізм.

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

Для реалізації цих двох основоположних концепцій в мові С++ використовуються класи. Термін клас визначає тип об'єктів. При цьому кожний представник класу називається об'єктом. Кожний об'єкт завжди має свій, унікальний стан, визначений поточним значенням його даних-членів. Функціональне призначення класу визначається можливостями дії над об'єктами класу, які задаються його функціями-членами (методами). В кожному класі розподіляється пам'ять для зберігання даних, і встановлюються допустимі операції для кожного об'єкту даних даного типу. Створення об'єктів ланого класу здійснюється спеіальною функцією-членом, яка називається конструктором, а знищення - іншою спеціальною функцією-членом, яка називається деструктором. Клас дозволє робити недоступними внутріщні дані, предсталяючи їх як відкриті (public), закриті (private) і захищені (protected). Клас встановлює чітко визначений інтерфейс для взаємодії об'єктів цього типу з решта світом. Отриманими об'єктами можна управляти за допомогою повідомлень (запитів), які представляють собою просто виклики функцій-членів.

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

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

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

  1.  Методи розробки алгоритмів та програм.
  •  Метод повного перебору усіх можливих варіантів;
  •  Метод розділяй і володарюй;
  •  Метод послідовних наближень;
  •  Метод найшвидшого (градієнтного) спуску;
  •  Метод динамічного програмування;
  •  Метод пошуку в глибину і ширину;
  •  Метод моделювання.
  1.  Алгоритми пошуку елемента в масиві та підпослідовності в послідовності.

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

  шуканий елемент знайдений в деякій позиції i, тобто a[i]=x;

  весь масив переглянутий і шуканий елемент відсутній. Таким чином, алгоритм лінійного пошуку можна записати у вигляді послідовності команд :

i:=1;
while (i<=N)and(a[i]<>x) do i:=i+1;

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

Виникає питання, чи можливо пошук пришвидшити? Єдиний вихід - спростити умову в заголовку цикла, оскільки вона складається із двох логічних множників. Потрібно сформулювати просту умову, яка буде еквівалентною вихідній. Це можна зробити, якщо гарантувати, що співпадіння з шуканими ключем завжди буде. Тому помістимо вкінець масиву додатковий елемент - "барєр" із шуканим значенням x. Звичайно, при цьому необхідно попередньо розширити на один елемент масив a та діапазон допустимих значень індекса :

a:array [1..N+1] of basetype

Алгоритм в цьому випадку матиме вигляд :

i:=1;
a[N+1]:=x;
while a[i]<>x do i:=i+1;

В обох випадках алгоритму істинність умови i=N+1 свідчить про відсутність шуканого елемента в масиві.

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

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

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

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

Нехай масив a є впорядкованим по зростанню, тобто ai+1іai, i=1,N-1.

Розглядуваний алгоритм базується на таких принципах :

  1.  вибирається довільно деякий елемент, наприклад am;
  2.  проводиться порівняння am з аргументом пошуку x;
  3.  якщо значення співпадають, то пошук припиняється, якщо am<x, то відкидаються з розгляду всі елементи масиву до a m включно, якщо a m>x, то відкидаються з розгляду всі елементи масиву після am включно.

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

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

L:=1; R:=N; f:=true;
while (L<=R) and f do
begin
m:=k; {k -
довільне значення між L і R}
if a[m]=x then f:=false else
if a[m]<x then L:=m+1 else R:=m-1
end;

Очевидно, що вибір m може бути довільним. Однак найкраще - відкидати на кожному кроці, незалежно від результату порівняння, якомога більше елементів. Оптимальним є вибір серединного елемента в розглядуваній частині, оскільки завжди рівноімовірно відкидатиметься половина масиву. В результаті максимальна кількість порівнянь округлює число log(N) до найближчого цілого. Це значно краще від лінійного пошуку (середня кількість порівнянь - N/2).

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

if a[m]<x then L:=m+1 else
if a[m]>x then R:=m-1 else f:=false;

Однак, можна ще покращити ефективність, якщо спростити умову припинення алгоритму. Для цього необхідно відмовитися від бажання припинення пошуку при фіксації співпадання. Тоді пошук продовжуватиметься доти, доки досліджувана частина масиву не стягнеться до одного елемента, який і буде шуканим:

L:=1; R:=N;
while L<R do
begin
m:=(L+R) div 2;
if a[m]<x then L:=m+1 else R:=m
end;

Умова припинення циклу L>=R досягається. Адже для цілочисельного серединного значення m справедлива нерівність L<=m<R, якщо попередньо виконувалася умова L<R. Отже, або L збільшується при присвоєнні йому значення m+1, або R зменшується при присвоєнні йому значення m. Таким чином, різниця R-L на кожному кроці зменшується, і при досягненні нульового значення (L=R) повторення циклу припиняється.

Варто зауважити, що виконання умови L=R ще не гарантує знаходження потрібного ключа. Потрібно враховувати, що елемент a[R] в порівнянні ніколи участі не бере.Тому необхідна додаткова перевірка після циклу на рівність a[R]=x.

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

  1.  Алгоритми сортування.

Сортування слід розуміти як процес перегрупування заданої множини об’єктів в деякому конкретному порядку. Ціль сортування - полегшити наступний пошук елементів в такій відсортованій множині.

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

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

Сортування масивів

Нехай дано масив N елементів деякого абстрактного типу basetype : 

a : array [1..N] of basetype.

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

Основна умова : обраний метод сортування масивів повинен економно використовувати доступну пам’ять. Це означає, що перестановки, які приводять елементи в порядок, повинні виконуватися “на тому ж місці”. Тобто методи, в яких елементи масиву a передаються в результуючий масив b, не мають практичної цінності.

Алгоритми сортування окрім критерію економії пам’яті будуть класифікуватися по швидкості, тобто по часу їх роботи. Оскільки на різних типах ЕОМ одні і тіж методи показуватимуть відмінні результати, то в якості міри ефективності алгоритму можуть бути прийняті числа : C - кількість необхідних порівнянь ключів; M - кількість перестановок елементів. Очевидно, що ці числа є функціями від кількості елементів в масиві N.Згідно із введеними критеріями швидкодії алгоритми сортування поділяють на два типи - прямі та швидкі.

Прямі методи зручні для пояснення і розбору основних рис більшості сортувань, легко програмуються і відлагоджуються, а самі програми - короткі, що теж важливо для економії пам’яті. В основі їх лежить повторення N етапів обробки масиву із зменшенням на кожному з них кількості порівнюваних елементів. Ефективність даних алгоритмів є величиною порядку O(N2). Такі методи зручно використовувати на так званих “коротких” масивах.

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

Методи сортування “на тому ж місці” у відповідності із визначаючими їх принципами розбиваються на три основні категорії :

сортування включенням;

сортування вибором;

сортування обміном.

Прямі Методи Сортування Масивів Сортування Прямим Включенням

В основі розглядуваного методу лежить пошук для чергового елемента масиву відповідного місця у відсортованій частині із наступним включенням його в знайдену позицію. Таким чином елементи масиву умовно діляться на дві групи - вже “готову” послідовність a 1 , a 2 , ..., a i та вихідну послідовність. На кожному етапі, починаючи з i=2 та збільшуючи i кожен раз на 1, із вихідної послідовності вибирається один елемент і вставляється в потрібне місце у вже впорядковану послідовність. Очевидно, що початково ліва послідовність буде “готовою”, оскільки одноелементний масив завжди впорядкований. Цей алгоритм можна записати у вигляді послідовності команд :

for i:=2 to N do

 begin

  x:=a[i];

  включення x на потрібне місце серед a[1], ..., a[i]

 end;

Процес просіювання (пошуку потрібного місця для ключення елемента x ) може принитися при виконанні однієї із двох умов :

1) знайдено елемент a j з ключем, меншим ніж ключ у x ;

2) досягнутий лівий кінець “готової” послідовності.

Таким чином програмна реалізація методу прямого включення матиме вигляд процедури :

 Procedure Straight_Insertion;

Var

 i, j : integer; x : basetype;

Begin

 for i:=2 to N do

  begin

   x:=a[i]; a[0]:=x; j:=i;

   while x<a[j-1] do

    begin

     a[j]:=a[j-1];

     j:=j-1

    end;

   a[j]:=x

  end

End;

Використання додаткового елемента в масиві - “барєраa[0]=x забезпечує гарантоване припинення процесу просіювання. Це дозволяє зменшити кількість логічних умов в заголовку цикла while до однієї, а кількість логічних операцій від 2i-1 до i на кожному етапі. Звичайно, при цьому необхідно попередньо розширити на один елемент масив a та діапазон допустимих значень індекса. На жаль, таке покращення ефективності по кількості порівнянь не зменшує об’єму перестановок елементів.

сортування бінарним включенням

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

Procedure Binary_Insertion;

 Var

 i, j, m, L, R : integer; x : basetype;

Begin

 for i:=2 to N do

  begin

   x:=a[i]; L:=1; R:=i;

   while L<R do

    begin

     m:=(L+R) div 2;

     if a[m]<=x then L:=m+1 else R:=m

    end;

   for j:=i downto R+1 do

     a[j]:=a[j-1];

   a[R]:=x

  end

End;

Сортування прямим вибором

На відміну від включення, коли для чергового елемента відшукувалося відповідне місце в “готовій” послідовності, в основу цього методу покладено вибір відповідного елемента для певної позиції в масиві. Цей прийом базується на таких принципах :

1) на i-ому етапі серед елементів a i , a i+1 , ..., a N вибирається елемент з найменшим ключем a min ; 2) проводиться обмін місцями a min та a i .

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

Такий алгоритм можна записати у вигляді послідовності команд :

 for i:=1 to N-1 do

 begin

  k:=номер найменшого ключа серед a[i], ..., a[N];

  обмін місцями  a[k] та a[i]

 end;

А програмна реалізація методу прямого вибору матиме вигляд процедури :

 Procedure Straight_Selection;

Var

 i, j, k : integer; x : basetype;

Begin

 for i:=1 to N-1 do

  begin

   x:=a[i]; k:=i;

   for j:=i+1 to N do

    if a[j]<x then begin x:=a[j]; k:=j end;

   x:=a[k]; a[k]:=a[i]; a[i]:=x

  end

End;

Сортування прямим обміном

Даний метод базується на повторенні етапів порівняння сусідніх ключів при русі вздовж масиву. Якщо наступний елемент виявиться меншим від попереднього, то відбувається обмін (звідси і назва методу). Таким чином, при русі зправа наліво за один етап найменший ключ переноситься на початок масиву. Зрозуміло, що кожен наступний прохід можна закінчувати після позиції знайденого на попередньому етапі мінімального елемента, оскільки всі елементи перед ним вже впорядковані. Розглядуваний процес дещо нагадує виштовхування силою Архімеда бульбашки повітря у воді. Тому цей алгоритм ще називають “бульбашковим” сортуванням.

Програмна реалізація методу прямого обміну або “бульбашки” матиме вигляд процедури :

 Procedure Buble_Sort;

Var

 i, j : integer; x : basetype;

Begin

 for i:=2 to N do

  for j:=N downto i do

   if a[j-1]>a[j] then begin x:=a[j]; a[j]:=a[j-1]; a[j-1]:=x end

End;

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

 Procedure Stone_Sort;

Var

 i, j : integer; x : basetype;

 Begin

 for i:=1 to N-1 do

  for j:=1 to N-i do

   if a[j]>a[j+1] then begin x:=a[j]; a[j]:=a[j+1]; a[j+1]:=x end

 End;

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

1) фіксувати, чи були перестановки в процесі деякого етапу. Якщо ні, то - кінець алгоритму ;

2) фіксувати крім факту обміну ще і положення (індекс) останнього обміну. Очевидно, що всі елементи перед ним або після нього відповідно для сортування “бульбашкою” або “камінцем” будуть впорядковані ;

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

Читачу пропонується самостійно модифікувати наведені вище процедури з врахуванням цих покращень.

Швидкі методи сортування масивів

Сортування включенням із зменшуваними відстаннями - Алгоритм шелла (1959)

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

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

1) на першому етапі окремо групуються і сортуються елементи, розміщені на відстані N/2 . Це є впорядкування N/2 підмасиві по 2 елементи, яке називатимемо N/2-сортування .

2) на другому етапі виконується впорядку вання N/4 підмасивів по 4 елементи на відстані N/4 - N/4-сортування і т.д.

На останньому етапі виконується одинарне сортування (впорядкування на відстані 1). Наприклад :

  44  55  12  42  94  18  06  67

етап I       4-сортування

  44  18  06  42  94  55  12  67

етап II       2-сортування

  06  18  12  42  44  55  94  67

етап III       1-сортування

  06  12  18  42  44  55  67  94

Виникає питання, чи використання багатьох процесів сортування із залученням всіх елементів не збільшить кількість операцій, тобто складність алгоритму? Але на кожному проході або впорядковується відносно мало елементів (початкові етапи), або елементи вже досить добре впорядковані і вимагається відносно мало перестановок (кінцеві етапи). Кожне i-те сортування об’єднує дві групи, вже впорядковані 2i-тим сортуванням. Очевидно, що відстань між елементами груп можна зменшувати по-різному, головне, щоб остання була одиничною. Останній прохід в найгіршому випадку і виконує основну роботу. Варто зауважити, що такий довільний підхід при зменшенні відстаней не погіршує результату і у випадку кількості елементів N, що не є степенем двійки.

Нехай виконується t етапів. Відстані між елементами в окремих групах на кожному етапі позначимо : h1 , h2 , ..., h t , де h t=1, h i+1<h i , i=1, 2, ..., t-1. Таким чином розглядаються h-ті сортування. Кожне h-те сортування можна реалізувати будь-яким із прямих методів. Зокрема, вибір включення оправданий кращою в порівнянні з іншими алгоритмами ефективністю по перестановках ключів. Однак, чи варто для спрощення умови припинення пошуку місця включення чергового елемента користуватися методом бар’єрів? Оскільки кожне h-те сортування потребує свого власного бар’єра, то прийдеться розширити масив не на одну компоненту a0 , а на h1 компонент. На першому етапі - це практично половина всіх елементів. У випадку “довгих” масивів прийдеться порушити правило сортування “на своєму місці”. Тому не варто заради економії однієї логічної операції на кожному етапі впорядкування жертвувати такими об’ємами пам’яті.

Кількість етапів сортування t як і відстані на кожному з них можна вибирати довільно. Зокрема, це може бути кількість цілочисельних поділів числа N на 2, тобто t=[log(N)]. В якості прикладу пропонується процедура сортування методом Шелла для масиву із 16 елементів :

 Procedure Shell_Sort;

Const t=4;

Var

 m, i, j, k : integer;

 h : array [1..t] of integer;

 x : basetype;

Begin

 h[1]:=8; h[2]:=4; h[3]:=2; h[4]:=1;

 for m:=1 to t do

  begin

   k:=h[m];

   for i:=k+1 to N do

    begin

     x:=a[i]; j:=i-k;

     while (x<a[j]) and (j>0) do

      begin

       a[j+k]:=a[j]; j:=j-k

      end;

     a[j+k]:=x

    end

  end

End;

Сортування обміном на великих відстанях - Алгоритм quick sort

Основна причина повільної роботи алгоритму прямого обміну полягає в тому, що всі порівняння і перестановки елементів в послідовності a 1 , a 2 , ..., a N відбуваються для пар із сусідніх елементів. При такому способі потрібно відносно більше часу, щоб поставити деякий ключ, який знаходиться не на своєму місці, в потрібну позицію у сортованій послідовності. Природньо попробувати пришвидшити цей процес, порівнюючи пари елементів, що знаходяться далеко один від одного в масиві. К. Хоор розробив алгоритм Quick Sort із середнім часом роботи порядку O(N*lnN).

Припустимо, що перший елемент масиву, що сортується, є хорошим наближенням елемента, який вкінці опиниться на своєму місці у відсортованій послідовності. Приймемо його значення в якості ведучого елемента, відносно якого ключі будуть мінятися місцями. Для зручності реалізації алгоритму використаємо два вказівники I, J, перший з яких вестиме відлік вздовж розглядуваної частини масиву зліва, а другий - справа. Початково їх значення будуть відповідно I=1, J=N. Таким чином ведучим елементом буде значення a[I]. Перестановки ключів проводяться за такими принципами :

1) порівнюються елементи a[I] та a[J]; якщо a[I]a[J], то здійснюється крок вліво J:=J-1 і порівняння повторюється; зменшення J продовжується доти, поки не виконається умова a[I]> a[J];

2) якщо при порівнянні елементів досягнута умова a[I]> a[J], то проводиться обмін місцями кючів a[I] та a[J] і здійснюється крок вправо I:=I+1; таким чином ведучий елемент перейшов в позицію J; порівняння ключів із збільшенням I