Конспект з основ інформатики

Конспект з основ інформатикий

Правильна алгоритмічна конструкція

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

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

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

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

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

На практиці найбільш поширеним є такі способи представленняалгоритмів:

ü  Словесно-формульний спосіб (запис на природній мові).Вын являє собоюопис послідовних етапів обробки даних. Алгоритм задається вдовільному викладі природною мовою;

ü  Словесний спосіб не має широкого поширення, тому що такі описи:

·         строго не формалiзуються,;

·         страждають багатослівність записів;

·         допускають неоднозначність тлумачення окремих приписів.

ü  Графічний спосіб (з використанням графічних примітивів, блок-схем);

Для розробки структури програми зручніше користуватися записомалгоритму у вигляді блок-схеми (в англомовній літературі використовується термінflow-chart). Для зображення основних алгоритмічних структур і блоків наблок-схемах використовують спеціальні графічні символи. Вони наведені намалюнку:

Початок/кінець алгоритм

Блок обчислень

Початок (заголовок) циклу

Перевірка умов

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

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

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

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

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

Теорема Бома-Джакопіні

    

 Для того щоб скласти блок-схему довільного алгоритму, достатньо трьох

конструкцій: складеного оператора типу BEGIN_END, оператора

розгалуження типу IF_THEN_ELSE та оператора циклу типу WHILE_DO:

Сутність алгоритмів «зверху-вниз»

Розглянемо розбір зверху-вниз (пророкує розбір) для граматики G.

Головне завдання пророкує розбору - визначення правила виведення, яке потрібно застосувати до нетерміналу. Процес пророкує розбору з точки зору побудови дерева розбору проілюстрований на рис. 4.1Фрагменти недобудованого дерева відповідають сентенціальних формам. Спочатку дерево складається тільки з однієї вершини, відповідної аксіомі S. У цей момент по першому символу вхідного ланцюжка пророкує аналізатор має визначити правило S -> X1X2 ... ; Яке має бути застосоване до S. Потім необхідно визначити правило, яке має бути застосоване до X1, і т.д., до тих пір, поки в процесі такої побудови сентенціальний форми, відповідної лівому висновку, не буде застосовано правило Y -> a ...: Цей процес потім застосовується для наступного самого лівого нетермінального

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

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

Таблиця аналізу - це двовимірний масив M [A; a], де A - нетермінал, і a - термінал або символ $. Значенням M [A; a] може бути деяке правило граматики чи елемент "помилка".

Магазин може містити послідовність символів граматики з $ на дні. У початковий момент магазин містить тільки початковий символ граматики на верхівці і $ на дні.

Аналізатор працює таким чином. Спочатку аналізатор знаходиться в конфігурації, в якій магазин містить S $, на вхідних стрічці w $ (w - аналізована ланцюжок), вихідна стрічка порожня. На кожному такті аналізатор розглядає X - символ на верхівці магазину і a - поточний вхідний символ. Ці два символи визначають дії аналізатора. Є такі можливості:

1.      Якщо X = a = $, аналізатор зупиняється, повідомляє про успішне закінчення розбору і видає вміст вихідний стрічки.

2.      Якщо, аналізатор видаляє X з магазину і просуває покажчик входу на наступний вхідний символ.

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

4.      Якщо X - нетермінал, аналізатор заглядає в таблицю M [X; a].

Можливі два випадки:

1)      Значенням M [X; a] є правило для X. В цьому випадку аналізатор замінює X на верхівці магазину на праву частину даного правила, а саме правило поміщає на вихідну стрічку.

2)    Покажчик входу не пересувається.Значенням M [X; a] є "помилка". В цьому випадку аналізатор зупиняється і повідомляє про те, що вхідні ланцюжок не належить мові

Класифікація мов програмування

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

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

Описи алгоритмів мовою програмування називають програмами.

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

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

Всі існуючи мови програмування можна поділити на дві групи:

·         мови низького рівня;

·         мови високого рівня.

До мов низького рівня належать мови асемблера (від англ. to assemble - складати, компонувати). У мові асемблера використовуються символьні позначення команд, які легко зрозуміти і запам'ятати. Замість послідовностей двійкових кодів команд записуються їх символьні позначення, а замість двійкових адрес даних, які використовуються під час виконання програми, - символьні імена цих даних. Іноді мову асемблера називають мнемокодом або автокодом.

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

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

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

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

Розрізняють два типи трансляторів:

·         компілятори

·         інтерпретатори

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

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

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

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

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

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

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

Парадигми програмування

Паради́гма програмува́ння — основні принципи програмування (не плутати з розробкою програм), або, парадигмне програмування.

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

Основні парадигми програмування:

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

ü  Модульне програмування — парадигма програмування, основна ідея полягає в:

·        реалізації обчислювальних процесів у вигляді окремих програмних одиниць - модулів;

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

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

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

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

ü  Суб'єктно (Істотно)-орієнтоване програмування (англ. subject - oriented programming, SOP; надалі СОП) - метод побудови об'єктно-орієнтованих систем, як композиції суб'єктів.

·          У цілому СОП включає:

·         Розбиття системи на суб'єкти;

·         Написання правил для їх правильної композиції.

ü Функціонально-орієнтоване програмування — загальна парадигма компонування програм у ряд програмних продуктів.

Технології програмування

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

Структурне програмування.

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

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

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

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

Єволюція технологій програмування

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

       Програми для перших обчислювальних машин створювались, як правило, в машинних кодах або на асемблері і були схожі на витвір мистецтва, бо повинні були поміститись у мініатюрному за сучасними поняттями об’ємі пам’яті. Пошуки помилки в програмі можна було, мабуть, порівняти з муками Тантала. Програмісти були схожі на “вищу касту” серед нормальних людей, бо вони єдині були здатні на спілкування з обчислювальною технікою. Цей етап програмування називають “стихійним програмуванням”. Створення нових алгоритмічних мов програмування, таких як FORTRAN та ALGOL, дещо покращило, але не змінило в корені ситуацію. Революційний винахід засобів, що підтримували можливість використання підпрограм, привів до підвищення складності програм. Були створені цілі бібліотеки службових та розрахункових програм, які можна було використовувати в

різних програмних системах. Дані в програмах зберігались, як правило, в глобальних областях, які спільно використовувались різними підпрограмами. В 60-х роках минулого вже століття вибухнув так званий кризис програмування. Вираженням його стали програмні проекти, які встигали морально застаріти ще на рівні розробки, і перевищували всі можливі терміни в часі та вартості. Бідою більшості програмних проектів ставали численні помилки, пошуки та виправлення яких займали до 90% часу, відведеного на розробку. Багато з них так і не були завершені. Причиною такого положення речей стала відсутність ретельно продуманих технологій або методів програмування.

     Глибокий та ретельний аналіз причин даного кризису привів до створення робочої групи з методології програмування при Міжнародній федерації по обробці інформації. До її складу увійшло багато відомих програмістів, наприклад, Н. Вірт, П. Наур, Ч.Хоар, У. Дал, Е. Дейкстра. Їх спільні зусилля привели до оформлення нової технології (інколи кажуть –

парадігми) програмування – структурного програмування [3, 4, 9, 12, 15].

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

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

     Сучасні технології програмування базуються на принципах об’єктно-орієнтованого програмування, завдяки якому складні програмні проекти реалізуються у вигляді сукупності об’єктів певної ієрархії. Їх взаємодія встановлюється шляхом передачі повідомлень між об’єктами. На підтримку нової технології програмування були створені нові мови, наприклад C++, Java, Modula. Організація програм на засадах інкапсуляції, успадкування, поліморфізму дозволила значно підвищити рівень програмних проектів.

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

компонентному підході

Мови програмування

     Власне перші мови програмування з'явилися задовго до появи перших комп'ютерів. Ще в 19-му столітті існували "програмовані" ткацькі верстати та піаніно-програвачі, спосіб програмування нагадує так звані предметно-орієнтовані мови програмування. На початку 20-го століття починають використовуватись перфокарти, та механічна обробка даних. В 1930 -1940 рр. виникає лямбда-числення та машина Тюринга, які застосовували математичну абстракцію для опису алгоритмів. Лямбда-числення згодом здійснило вплив на проектування мов програмування.

     В 1940 роках створюються перші електричні, двійкові комп'ютери. Вважається, що першу мову програмування високого рівня — Планкалькюль (нім. Plankalkül) розробив німець Конрад Цузе в період 1943 -1945 році, але в той час вона не була реалізована і не одержала уваги. Реалізацією мови зайнялися і здійснили лише в 1998-2000 роках[5].

      Першою широковживаною компільованою мовою став розроблений групою Джона Бекуса Фортран, анонсований у 1954 році і випущений у 1957 для IBM 704. Основним призначенням Фортрану були швидкі наукові обчислення, оголошувалося що швидкодія згенерованого компілятором коду майже не відрізянтиметься від машинного коду написаного вручну. Уже у квітні 1958 близько половини програм для IBM 704 були написані на Фортрані. Випущений у 1958 році Фортран II дозволяв незалежну компіляцію підпрограм, що дозволило створювати більші програми, оскільки низька надійність IBM 704 не дозволяла скомпілювати без збоїв велику програму (понад 300—400 рядків) одразу. Розроблений у 1960—1962 роках Фортран IV був однією з найпоширеніших мов того часу і лишався стандартною версією Фортрану до появи у 1978 році Фортрану 77.

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

        У кінці 1950-их почали розроблятися різні мови програмування. У 1958 році декілька значних груп комп'ютерних користувачів у США, включаючи SHARE — групу науковців-користувачів IBM і USE (UNIVAC Scientific Exchange, група науковців-користувачів UNIVAC) запропонували ACM заснувати робочу групу зі створення універсальної мови програмування. Також ще у 1955 році німецьке Товариство прикладної математики і механіки (GAMM) заснувало комітет зі створення універсальної мови програмування. У кінці травня 1958 року було проведено зустріч у Цюриху між ACM і GAMM, на матеріалах якої у грудні опубліковано ALGOL 58 Report. На його основі було створено 3 значні реалізації — MAD (1961), NELIAC (1963), JOVIAL (1963). З них лише JOVIAL отримав поширення, ставши на чверть століття офіційною мовою програмування у Військово-морських силах США. SHARE і IBM почали створення власної реалізації ALGOL, але припинили, врахувавши витрати на створення і просування Фортрану.

     Впродовж 1959 року ALGOL 58 широко обговорювався, була запропонована нотація для опису синтаксису мов програмування — форма Бекуса-Наура. У 1960 проведено чергову зустріч і опубліковано ALGOL 60 Report. ALGOL вплинув на багато мов програмування і став стандарною мовою для публікації алгоритмів, але через ряд причин не одержав широкого поширення — він був заскладним, і не було реалізацій, які підтримували його повністю, відсутність стандартного введення-виведення привела до появи різних несумісних реалізацій, деякі неоднозначності опису мови так і не були розв'язані. Також широкого вжитку уже набув Фортран, і IBM не підтримала ALGOL.

     У 1959 році була проведена зустріч у Пентагоні для створення мови CBL (Common Business Language), засновано комітет з його створення, і у 1960 опубліковано початкову специфікацію COBOL 60, який невдовзі став першою мовою прийнятою у Міністерстві оборони США. У 1968 році COBOL було стандартизовано ANSI.

     У 1964 році було створено спрощену мову BASIC (Beginners All-purpose Symbolic Instruction Code) для навчання програмуванню студентів, які переважно спеціалізувалися у вільних мистецтвах, а не технічних науках.

Тоді як науковці переважно використовували Фортран, а бізнес — COBOL, у 1963 році в IBM вирішили створити універсальні платформу IBM/360 і мову програмування. У стислі терміни до 1965 року було розроблено мову PL/I, яка поєднувала можливості Фортран, ALGOL і COBOL, і виявилась заскладною, хоча і була у широкому вжитку у 1970-их у наукових і бізнес задачах, також її підмножини (PL/C, PL/CS) використовувалися для навчання програмуванню.

На початку 1960-их було створено перші мови із динамічною типізацією — APL і SNOBOL.

SIMULA 67 була першою об'єктно-орієнтованою мовою програмування.

У 1965 році Ніклаус Вірт і Тоні Хоар запронували комітету з розвитку мови ALGOL свою версію, яку згодом назвали ALGOL-W і застосовували для навчання в деяких університетах. Пропозиція була відхилена через незначну кількість змін, на користь значно складнішого ALGOL 68. У ALGOL 68 з'явилися визначення структур данних і динамічні масиви. ALGOL 68 став першою мовою із формальною специфікацією, яка однак була складною для розуміння.

У 1971 році Вірт опублікував опис мови Pascal, яка у 70-их стала загальновживаною для навчання студентів.

У 1972 році Деніс Річі розробив у Bell Labs мову C. Тоді ж у Марселі створено інтерпретатор мови Пролог - першої і найвідомішої мови логічного програмування. Алан Кей у Xerox PARC розробив першу широко вживану об'єктно-орієнтовану мову — Smalltalk.

у 1973 Робін Мілнер в Единбурзькому університеті створив ML.

У 1975 році в Массачусетському технологічному інституті описано спрощений діалект мови Лісп — Scheme.

У 1976 випущено мову для статистичного програмування S, на базі якої в 1993 році створено R.

У 1977 році випущено Bourne shell.

У 1975 Міністерство оборони США утворило міжнародну групу для створення нової мови програмування для власних потреб, конкурс у 1979 виграла мова Ада.

У 1981 випущено dBASE II.

У 1984 році з метою об'єднання різних діалектів Ліспу створено Common Lisp. Випущено MATLAB

У 1985 році Б'ярн Страуструп опублікував реалізацію мови C++. Тоді ж випущено AWK.

У 1986 році опублікована мова Objective-C і створено Erlang. Тоді ж Borland і Apple незалежно створили об'єктно-орієнтоване розширення мови Pascal - Object Pascal.

У 1987 році створено Perl.

У 1990 році опубліковано Standard ML і Haskell.

У 1991 році створено Visual Basic і опубліковано Python.

У 1992 випущено Oracle 7 з підтримкою PL/SQL

У 1993 році створено Lua.

У 1995 році Sun Microsystems випустила Java, Netscape — JavaScript, тоді ж створено PHP і Ruby.

У 1996 році створено OCaml.

У 2001 році створено C#.

У 2002 році створено F#. У 2003 році створено Scala.