Алгоритми. Властивості алгоритмів. Мови програмування
Алгоритми. Властивості алгоритмів. Мови програмування - Лекція, розділ Інформатика, Поняття інформації, загальна характеристика процесів збору, передачі, обробки та накопичення інформації План Лекції: Алгоритм, Численні та Логічні Алгоритми. Свій.
Алгоритм, чисельні та логічні алгоритми. властивості алгоритмів, дискретність, визначеність, зрозумілість, результативність. Форми запису алгоритму, блок-схем, основні елементи блок схем. Базові структури алгоритмів, лінійні, циклічні алгоритми, що розгалужуються. Дані та його типи. Логічні засади алгоритмізації. Мови програмування, еволюція, класифікація. Мови програмування високого та низького рівня. Компілювані мови. Інтерпретовані мови. Об'єктно-орієнтовані мови. Модульний принцип програмування Принципи проектування програм згори донизу і знизу догори. Системи програмування, схема розробки прикладних програм серед системи програмування, трансляція (компіляція), здійсненний код.
Короткий конспект лекції
| Програмування передує найважливіший етап - постановка завдання. Далі слідує формалізація, розробка математичних і фізичних моделей, виведення розрахункових формул. |
Програміст повинен чітко представляти явище чи формули, які він алгоритмізує. Складання алгоритму полягає у логічному описі процесу розв'язання задачі та вимагає знання елементів математичної логіки.
Мова програмування - мова, що використовується для написання комп'ютерних програм і що складається зі словника та сукупності правил (синтаксису), які застосовуються при написанні команд, що виконуються процесором. Мови програмування за стилем написання вихідного коду класифікуються на процедурні (складаються процедури, що містять набіркоманд) та декларативні (визначається сукупність фактів та взаємозв'язків, що дозволяють запитувати результати). Мови програмування за рівнем вихідного коду класифікуються мовами високого та мовами низького рівня.
Мови програмування низького рівня: Машинна мова та асемблер
Мови програмування високого рівня представляють спеціальний набір інструкцій, що використовують ключові слова та синтаксис, схожий на англійську мову. Visual Basic, Visual Fortran, Cobol, Delphi, C++.
Текст програми мовою програмування називається вихідним кодом, а кінцева програма в машинних кодах - об'єктним кодом. Для отримання об'єктного коду використовують транслятори.
Трансляториподіляються на два типи: інтерпретатори та компілятори.
Інтерпретаторпереводить у машинний код і виконує черговий оператор програми, що використовується для мови програмування Basic.
Компіляторпереводить у машинний код вихідний текст програми цілком, використовується мов програмування Pascal, З та інших.
Гідність компіляторів - швидкодія та автономність одержуваних програм. Гідність інтерпретаторів — їх компактність, можливість зупинити будь-якої миті виконання програми, виконати різні перетворення даних та продовжити роботу програми.
Компілятор - програма, яка зчитує вихідний код, перевіряє його синтаксис, перетворює на машинний код (транслює ) і встановлює зв'язки з підпрограмами (компілює). У процесі компіляції виконуються лексичний, синтаксичний, семантичний аналіз, генерація та оптимізація проміжного коду, генерація внутрішнього уявлення.
Лексичний аналіз– виявляються окремі складові тексту програми та визначається їхтип. Наприклад, назви операторів, імена змінних, роздільники (дужки, розділові знаки і т.д.). Лексеми замінюються кодом їхнього типу. Контрольне використання неприпустимих символів.
Синтаксичний аналіз- визначається синтаксична правильність лексем, наприклад, парність дужок.
Семантичний аналіз– виявляються порушення правил написання програми, наприклад, опис типів імен перед їх використанням, дублювання опису імен, узгодження типів формальних та фактичних параметрів тощо.
Генерація та оптимізація проміжного коду– переклад тексту програми в мову асемблера та усунення "зайвого" коду.
В результаті роботи компілятора виходить файл, що виконується – додаток.
Інтерпретатор - програма, яка зчитує вихідний код операторами, відразу транслює їх виконує. Таким чином, в результаті роботи інтерпретатора файл, що виконується, не формується.
Виконуваний файл - програма, готова до запуску на комп'ютері (зазвичай файл з розширенням .exe).
Програмування- процес, що включає стадії проектування, кодування, налагодження, тестування та документування програми.
- Проектування програми – визначення вхідних даних, процедур обробки даних та вихідних даних.
- Кодування програми – запис програми мовою програмування відповідно до алгоритму завдання.
- Тестування програми – перевірка результатів виконання програми для різних варіантів вихідних даних, що включають крайні значення діапазону даних, експериментально апробовані дані, розрахунки за аналітичними або спрощеними залежностями та розрахунки з використанням інших програм.
- Налагодження програми - виявлення та виправлення синтаксичнихпомилок, помилок на етапі виконання (переповнення розрядної сітки, поділ на нуль, вилучення кореня з негативного числа і т.д.) та логічних помилок у програмі.
Процесналагодженняпрограми починається з виявлення:
- синтаксичних помилок у тексті (невірно записаних операторів),
- помилок під час виконання програми (неприпустимі математичні дії, операції з числами, що перевищують граничні значення),
- алгоритмічних помилок (неправильно складений чи запрограмований алгоритм).
- Документування програми - створення докладного посібника за програмою: опис даних, що вводяться і виводяться, тестові приклади розрахунку.
Алгоpитм- заздалегідь заданий зрозумілий і точний розпорядження можливому виконавцю вчинити певну послідовність дій для отримання розв'язання задачі за кінцеве число кроків
Слово "алгоритм" походить від латинської форми написання імені арабського математика Аль Хорезмі. Відомо, що він народився до 800 р., а помер після 847 р., жив і працював у Багдаді – великому науковому центрі та впливовій столиці Стародавнього Сходу. Аль Хорезмі використовував індійську позиційну систему числення з нулем і сформував правила чотирьох арифметичних процесів над багатозначними числами.
Форми запису алгоритмів: графічний запис (блок-схеми); словесна запис (псевдокоди); мова програмування.
Дискретність - розбиття алгоритму на ряд окремих закінчених дій – кроків
Визначеність (детермінованість) - однозначні вказівки, застосування алгоритму до одних і тих самих вихідних даних має призводити до одного і того ж результату
Зрозумілість - однозначне розуміння та виконання кожного кроку алгоритму його виконавцем
Результативність -обов'язкове одержання результату за кінцеве число кроків
Масовість - означає, що алгоритм розв'язання задачі розробляється в загальному вигляді, тобто. він має бути застосований для деякого класу однотипних завдань, що відрізняються лише вихідними даними
Алгоритми можна як деякі структури, які з окремих базових (тобто. основних) елементів.
| Графічна запис алгоритму представляється як блок-схемы. Конфігурація та розміри блоків, а також порядок графічного оформлення блок-схем регламентовані ГОСТ 19002-80 та ГОСТ 19003-80 "Схеми алгоритмів та програм". Приклад блок-схеми: |
Логічна структура будь-якого алгоритму може бути представлена комбінацією трьох базових структур:дотримання, розгалуження, цикл. Характерною особливістю базових структур є наявність у них одного входу та одного виходу
Теорема Дейкстра. Алгоритм будь-якої складності можна реалізувати, використовуючи лише три конструкції: прямування (лінійні), вибору (розгалуження) та повторення (циклічні).
Модульне програмування- це організація програми як сукупності незалежних блоків, званих модулями, структура та поведінка яких підпорядковуються певним правилам.
Концепцію модульного програмування можна сформулювати у вигляді кількох понять та положень:
1) великі завдання розбиваються на ряд дрібніших, функціонально самостійних підзадач - модулів, які пов'язані між собою тільки за вхідними та вихідними даними;
2) модуль є «чорний ящик» з одним входом і одним виходом. Це дозволяє безболісно виробляти модернізацію програми в процесі її експлуатації, полегшує її супровід, а також дозволяє розробляти частини програмного забезпечення.проекту різними мовами програмування;
3) у кожному модулі повинні здійснюватися ясні завдання. Процес декомпозиції потрібно продовжувати доти, доки буде ясного розуміння призначення всіх модулів та його оптимального поєднання;
4) вихідний текст модуля повинен мати заголовок та інтерфейсну частину, де відображаються призначення модуля та всі його зовнішні зв'язки;
5) в ході розробки модулів програми слід передбачати спеціальні блоки операцій, які враховують реакцію на можливі помилки даних або в діях користувача.
Велике значення в концепції модульного програмування надається організації управляючих та інформаційних зв'язків між модулями програми, які спільно вирішують одну або кілька великих завдань.
Сихідний підхіддо розробки програмних систем. Відповідно до цього методом створення програми починається зверху, тобто. з розробки найголовнішого, генерального алгоритму. Так як на верхньому рівні зазвичай ще не зрозумілі деталі реалізації тієї чи іншої частини програми, ці частини слід замінити тимчасовими заглушками .
Висхідний підхіддо розробки програм. У цьому випадку здійснюється послідовна побудова програми з елементів, що вже є, починаючи з примітивів, що надаються обраною мовою програмування. Цей процес закінчується отриманням готової програми. На кожному етапі з наявних елементів будуються потужніші елементи. Ці елементи будуть використовуватися на наступному етапі для побудови ще більш потужних елементів, і так далі, доки не будуть отримані елементи, з яких можна безпосередньо скласти необхідну програму.
При конструюванні нових алгоритмів зазвичай домінує низхідний метод. При адаптації програм до дещозміненим вимогам перевага найчастіше надається висхідному методу. Обидва ці методи дозволяють розробляти структуровані програми.
Питання на цю тему:
1. Що таке алгоритм?
2. Що таке блок-схема?
3. Перерахуйте правила побудови алгоритмів мовою блок-схем.
4. Опишіть базові керуючі конструкції алгоритмів.
5. Перерахуйте основні методи сучасної технології проектування алгоритмів.
Література на тему:
1. Інформатика. Загальний курс/За ред. В.І. Колесникова. - 2-ге вид. - М.: Дашков та К; Наука-Прес, 2008. – 400 с.
2. Ігошин В.І. Математична логіка та теорія алгоритмів: Уч. сел. – М.: Академія, 2004. – 448с.
3. Мікрюков В.Ю. Алгоритмізація та програмування: Навч. сел.- Ростов н/Д: Фенікс, 2007.