Алгоритмізація та програмування

Размещено на http://www.allbest.ru/

Алгоритмізація та програмування



Лекція 1

План

Вступ

1. Програмування - що це? Наука, мистецтво, ремесло

2. Мислення і властивості програміста

3. Загальні завдання курсу

4. Технології, методи і підходи до програмування

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

6. Завдання та мови для їх рішення

Вступ

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

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

Перший запропоную я сам:

- Слухати уважно

Які можете запропонувати ви? *** (Обговорення)

- Приходити вчасно

- Правило «Говорить один» (або викладач, або один студент)

- Правило «Підніми руку» (якщо є що сказати)

- Правило «Запиши сам» (лекція не диктується, а будується у формі бесіди, кожен сам веде свої записи, і обов'язково робить помітки у важливих місцях)

1. Програмування - що це? Наука, мистецтво, ремесло

Як би ви могли відповісти на це питання?

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

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

Синергія

У цьому і полягає найважче питання - знайти як це зробити. Кожна людина індивідуальна. Як знайти ключик до Вашому особистому розумінню, до мозку кожного з вас? Це не тільки моє питання як викладача, це перш за все ваше запитання, бо ви в цьому зацікавлені не менше, а може й більше мого.

Є таке чудове грецьке слово «синергія», воно означає «співпраця, Печерській лаврі», коли двоє працюють на один результат і без зусиль тієї чи іншої сторони цей результат не може бути досягнутий. Саме це і є наш навчальний процес - Печерській лаврі викладача і студента. Знаєте іноді коли людина приходить вчиться у нього виникає бажання сісти, розслабитися, розвалиться на стільці і сказати «Ну давайте, вчіть мене - я готовий». Нічого не вийде. Без нашого спільного праці, нічого н вийде. Я працюю + ви працюєте = результат. І ніяк інакше.

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

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

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

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

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

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

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

2. Мислення і властивості програміста

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

Перший ми вже знаємо:

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

Алгоритмічне мислення (здатність вирішувати завдання за допомогою чітко визначеної послідовності дій, набору конкретних кроків) Створення правильного алгоритму - це більша половина справи у вирішенні задачі. *** (Що є алгоритмом?) Алгоритм - це послідовність дій зрозумілих виконавцеві і однозначно призводять до бажаного результату. Тобто, алгоритм це деякий рецепт. Наприклад, рецепт коктейлю, Якщо ви виконуєте рецепт в точності ви отримує певний коктейль, якщо я виконую цей рецепт в точності я з великою часткою ймовірності отримаю той-же коктейль. Таким чином, цей рецепт не залежить від виконавця і приводить до результату. Здатність придумувати правильні «рецепти» алгоритми є однією з найважливіших особливостей мислення програміста, без якої він не буде здатний вирішити поставлених завдань.

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

Алгоритм як перейти дорогу.

1. Підійти до дороги.

2. Якщо червоний колір, чекати зелений.

3. Зелений - перейти.

Системне мислення (здатність отримувати знання «розкладати по поличках» і встановлювати зв'язки між наявними знаннями, для отримання цілісної системи)

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

Абстрактне мислення (один з видів людського мислення, який полягає в утворенні абстрактних понять і оперуванні ними.). У житті ми в основному маємо справу з конкретними речами, які бачили або про яких чули - це предмети які нас оточують. У нашій голові ми мислимо за допомогою категорій, які властиві цим предметам, наприклад «на столі лежить шматок білої крейди». *** (Які предмети тут використані) Предмети «стіл, крейда» *** (Як вони співвідносяться?) Співвідносяться через вплив «лежати на», у крейди є властивість «білий». Такий стиль мислення називається предметним. Абстрактне мислення протилежно предметному, при цьому необхідно мислити категоріями які не мають реального відображення в нашому світі. Щось на зразок математики «a> b-3», абстрактні поняття *** (Які?) «A, b» співвідносяться *** (як?) Як «менше». У програмуванні, як і в математиці також часто необхідно виконувати дії над деякими абстрактними сутностями, тобто змінними, масивами, структурами, списками. Задачу однак, полегшує, то що, часто ці сутності якимось чином відображають предмети реального світу, наприклад змінна, яка зберігає значення процентної ставки в банку, або масив який показує скільки кілометрів пробіг спортсмен на кожному тренуванні.

Якщо говорити про особливості програмістів, то виходячи з педагогічної практики можна виділити наступне:

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

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

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

3. Програмісти - дуже, наполегливілюди. Доробити програму до робочого стану - потрібно бути дуже впертим.

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

Хотілося б завершити ці роздуми жартом: «є 10 типів людей - які розуміють двійкову систему і які не розуміють ...»

3.Загальні завдання курсу

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

У завдання входить вивчення:

- Основних понять використовуваних програмістами і програмами;

змінна, масив, компіляція, тип даних, відладчик і т.п.

- Принципів побудови алгоритмів;

принципи фон Неймана, структурне програмування, Ч

- Знань про основні алгоритмічні конструкції, які використовуються при розробці програм;

ланцюжок, розгалуження, цикл, їх блок-схеми і вирази

- Відомостей про синтаксис мов програмування (як взагалі, так і С зокрема);

правила побудови ідентифікатров, ключові слова, органзіція введення-виведення

- Отримання уявлення і навичок вирішення типових програмістських задач;

завдання на сортування, на обмін змінних, використання процедур

- Базових математичних принципів, використовуваних у програмуванні;

двійковий код, кон'юнкція (І), диз'юнкція (АБО).

- Основних відомостей про парадигмах програмування;

- Понять про документування програм;

роль коментарів, автодокументирування, грамотне програмування

- Способів налагодження, тестування і доказів правильності (або навпаки правдоподібності) програм;

Рівень інженера має включати:

1. Фізику

2. РТ процеси

3. Складові елемента

4. Прилади

Байт - це знак, який складається з 8 бит, для кодування знаків.(156 букв).

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

Конфігурації та різновиди її машин

Математик Джон Фон Неймон у 1945році вияснив склад конфігурації, побудував першу обчислювальну машину, і обґрунтував склад та архітектуру, модифікації архітектури.

Принципи:

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

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

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

4. Використовується двійкова система числення програми та данних комп'ютера.

Частина друга.

4. Технології, методи і підходи до програмування

Парадигма програмування - це сукупність ідей і понять, які визначають стиль написання програм. Парадигмою Томас Кун в книзі «Структура наукових революцій», називає «усталені системи наукових поглядів, в рамках яких ведуться дослідження».

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

Однак у програмуванні парадигми не є взаємовиключними. Більш того нерідко «вдосконалення мистецтва окремого програміста вимагає, щоб він розширював свій репертуар парадигм» (Роберт Флойд).

Імперативне програмування

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

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

Щоб спростити програмування, монтажування мов було розроблено. Ці замінені функціями машинного коду з мнемоніки і адреса пам'яті з символічної етикетки. Асамблея мова програмування вважається низьким рівнем парадигми хоча це парадигма «другого покоління».

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

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

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

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

C - Розроблено близько 1970 року в BellLabs

COBOL (CommonBusinessOrientedLanguage) - використовує такі терміни, як файл, переміщати і копіювати.

FORTRAN (FormulaTranslation) - з використанням математичної термінології мови, вона була розроблена в основному для наукових і інженерних задач.

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

BASIC (BeginnersAllpurposeSymbolicInstructionCode) - була розроблена, щоб включити більше людей, щоб писали програми.

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

ООП

Об'ємктно-орієнтомване програмувамння (ООП) -- одна з парадигм програмування, яка розглядає програму як множину «об'єктів», що взаємодіють між собою. В ній використано декілька технологій від попередніх парадигм, зокрема успадкування, модульність, поліморфізм таінкапсуляцію. Попри те, що ця парадигма з'явилась в 1960-тих роках, вона не мала широкого застосування до 1990-тих. Сьогодні багато мов програмування (зокрема, Java, C#, C++, Python, PHP, Ruby та Objective-C, ActionScript 3) підтримують ООП.

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

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

Грамотнепрограмування

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

ЦікавимрізновидомєДП - концепція, методологіяпрограмуванняідокументування. Іноді це словосполучення помилково перекладають як літературне програмування. Термін і саму концепцію розробив Дональд Кнут в 1981 році при розробці системи комп'ютерної верстки TeX.

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

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

Сутність підходу

ДП є цілісний мета-підхід до написання програм, тобто «парадигма», застосовна на мета-рівні до будьякої (процедурної, функціональної, декларативної, об'єктно-орієнтованої) машинній програмі на будь-якому машинному мовою;

ДП є система макро, створювана з фраз на людській мові, які стають «метамовою» над конкретним мовою програмування. Користування цими фразами подібно поясненню алгоритмів на «псевдокоді», але в разі ГП вони стають точними «новими операторами» метамови;

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

технічно ДП робиться за допомогою утиліти, яка однією командою запускає препроцесор, розкриває всі макро і «сплутувалися», «заплутує» («tangle») логічний виклад в машинний код, який потім можна компіювати або запускати як зазвичай. Інша команда «сплітає» («weave») з цього загального для програми і пояснень файлу сформатував документацію (для друку, веба і т. д.).

Іншими словами, програма мислиться не як ієрархія, top-down або bottom-up, але як «взаимозависимая мережу концепцій» (звідси назва першої системи ДП - «Web») і створюється як «потік думки», що проходить по цій мережі в зв'язному, логичном вигляді, що зовні робить форму опису схожою на літературне есе. Програміст, таким чином, відмовляється від прив'язки до написаним машиною порядку.

Декларативне програмування

Імперативні мови програмування протиставляються функціональним і логічним мов програмування. Функціональні мови, наприклад, Haskell, не являють собою послідовність інструкцій і не мають глобального стану. Логічні мови програмування, такі як Prolog, зазвичай визначають що треба обчислити, а не як це треба робити.

Структурне програмування -- методологія програмування запропонована в 1970-х роках голландським науковцем Дейкстрою (Edsger Wybe Dijkstra), була розроблена та доповнена Ніклаусом Віртом.

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

· послідовне виконання - виконання операцій в тому порядку, в якому вони записані в тексті програми

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

· цикл - виконання операції доти доки виконується задана умова (умова продовження циклу)

Кожна конструкція являє собою блок із одним входом і одним або кількома виходами.

Блок Слідування передбачає лінійне виконання операторів програми.

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

· if (єдиний вибір)

· if...else (подвійний вибір)

· switch або case (множинний вибір)

Усі три структури при бажанні можна звести до однієї типу if.

Блок Повторення реалізується одним із трьох способів:

· структура while

· структура do/while

· структура for

Усі три структури можна звести до структури while.

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

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

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

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

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

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

Найвідомішим мовою логічного програмування є Prolog.

Першим мовою [джерело не вказано 871 день] логічного програмування була мова Planner, в якому була закладена можливість автоматичного виведення результату з даних і заданих правил перебору варіантів (сукупність яких називалася планом). Planner використовувався для того, щоб знизити вимоги до обчислювальних ресурсів (за допомогою методу backtracking) і забезпечити можливість виводу фактів, без активного використання стека. Потім була розроблена мова Prolog, який не вимагав плану перебору варіантів і був, в цьому сенсі, спрощенням мови Planner.

Від мови Planner також відбулися логічні мови програмування QA-4, Popler, Conniver і QLISP. Мови програмування Mercury, Visual Prolog, Oz і Fril відбулися вже від мови Prolog. На базі мови Planner було розроблено також декілька альтернативних мов логічного програмування, не заснованих на методі пошуку з поверненнями (backtracking), наприклад, Ether (див. огляд Шапіро [1989]).

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

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

Якщо B1 і ... і Вп, то Hлікує наслідки, як мета-скорочення процедур:, щоб показати / H вирішити, показати / B1 і вирішити ... і Вп.Наприклад, це відноситься до імплікації:Якщо ви натиснете на кнопку сигналу тривоги,то ви попередити водія про поїзд можливих надзвичайних як процедура:Щоб попередити водія про поїзд можливих надзвичайних ситуацій,натисніть на кнопку сигналу тривоги.Відзначимо, що це узгоджується з інтерпретацією ВНК конструктивної логіки, де наслідки можуть бути інтерпретовані як рішення задачі H даного рішення B1 ... Bn. Тим не менш, визначальною рисою логічного програмування є те, що множини формул можна розглядати як програми та пошук доказівможуть бути надані обчислювальний сенс. Це досягається шляхом обмеження логіки на "хороших" фрагмента таких як Хорна або спадкової формули Harrop. Див Д. Міллер і співавтор., 1991.



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

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

У відповідності з цією методологією

Будь-яка програма являє собою структуру, побудовану з трьох типів базових конструкцій:

· послідовне виконання - однократне виконання операцій в тому порядку, в якому вони записані в тексті програми;

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

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

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

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

Розробка програми ведеться крок за кроком, методом «зверху вниз».

Спочатку пишеться текст основної програми, в якому, замість кожного зв'язкового логічного фрагмента тексту, вставляється виклик підпрограми, яка буде виконувати цей фрагмент. Замість справжніх, працюючих підпрограм, в програму вставляються «заглушки», які нічого не роблять. Отримана програма перевіряється та налагоджується. Після того, як програміст переконається, що підпрограми викликаються в правильній послідовності (тобто загальна структура програми вірна), підпрограми-заглушки послідовно замінюються на реально працюючі, причому розробка кожної підпрограми ведеться тим же методом, що і основної програми. Розробка закінчується тоді, коли не залишиться жодної «затички», яка не була б видалена. Така послідовність гарантує, що на кожному етапі розробки програміст одночасно має справу з доступним для огляду і зрозумілим йому безліччю фрагментів, і може бути впевнений, що загальна структура всіх більш високих рівнів програми вірна. При супроводженні та внесення змін у програму з'ясовується, в які саме процедури потрібно внести зміни, і вони вносяться, не зачіпаючи частини програми, безпосередньо не пов'язані з ними. Це дозволяє гарантувати, що при внесенні змін та виправленні помилок не вийде з ладу якась частина програми, що знаходиться в даний момент поза зоною уваги програміста.

Теорема про структурне програмування:

Ця теорема була сформульована італійськими математиками К.Бомом і Дж.Якопіні в 1966 році і говорить нам про те, як можна уникнути використання оператора переходу goto.

Яку схему алгоритму можна представити у вигляді композиції вкладених блоків begin і end, умовних операторів if, then, else, циклів з передумо

Історія

Методологія структурного програмування з'явилася як наслідок зростання складності розв'язуваних на комп'ютерах завдань, і відповідного ускладнення програмного забезпечення. У 70-ті роки XX століття обсяги і складність програм досягли такого рівня, що «інтуїтивна» (неструктурована, або «рефлекторна») розробка програм, яка була нормою в більш ранній час, перестала задовольняти потребам практики. Програми ставали занадто складними, щоб їх можна було нормально супроводжувати, тому потрібна була якась систематизація процесу розробки та структури програм.

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

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

6. Завдання та мови для їх вирішення

Практика.

Завдання на переливання, перевіз. Логічні завдання.

Рішення логічних і логіко-арифметичних завдань



Лекція 2. Поняття, властивості, види запису алгоритмів

Що таке алгоритм?

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

встати

одягнутись

вмитися

поснідати

вийти з дому

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

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

Назва "алгоритм" походить від латинської форми імені видатного середньоазіатського математика Мухаммеда ібн Муса ал-Хорезмі (Alhorithmi), який жив у 783-850 рр.. У своїй книзі "Про індійський рахунок" він виклав правила запису натуральних чисел за допомогою арабських цифр і правила дій над ними "стовпчиком", знайомі тепер кожному школяреві. У XII столітті ця книга була перекладена на латинь і набула широкого поширення в Європі.

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

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

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

закип'ятити чайник

зробити бутерброд

з'їсти бутерброд з чаєм

вимити посуд

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

Виконавці

Що таке виконавець?

Виконавці часто зустрічаються в казках. В одній з них Іван-Царевич говорить хатинки-На-Курячих-ніжки: "Хатинка, хатинка! Встань до лісу задом, до мене передом! ". При цьому команда повинна бути задана дуже точно, щоб виконавець її зрозумів. У казці "Алі-Баба і сорок розбійників" чарівна двері відкривалися по команді "Сезам, відкрийся!". Жадібний Касим, таємно проник у печеру, забув цю фразу і не зміг вийти з печери.

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

* Виконавець - це той, хто вміє розуміти і виконувати деякі команди.

Виконавця хаpактеpизующих:

* сpеда;

* cистема команд;

* відмови.

* Середа виконавця - це предмети, які оточують виконавця і з якими він працює.

* Список (або система) Команд Виконавця (СКІ) - набір команд, зрозумілих виконавцеві. Виконавець може виконати тільки ті команди, які входять в його СКІ.

Після виклику команди виконавець вчиняє відповідне елементарне

дію.

Виконавцями можуть бути

* люди: учень, робітник, вчитель, бригада;

* тварини: дресирована собака (санітар, розшукова, мисливський), кішка;

* машини: верстати, роботи, комп'ютери;

Зазвичай виконавець нічого не знає про мету алгоpітма. Він виконує всі отримані

команди, не задаючи питань "чому" і "навіщо".

Людина як виконавець відрізняється від всіх інших виконавців кількома ознаками, наприклад:

Розуміє команди в різних варіантах (наприклад "Сядь!", "Сідай!", "Сядь!").

Виконуючи команди, «додумує» їх з урахуванням свого досвіду.

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

В інформатиці універсальним виконавцем алгоритмів є комп'ютер.

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

* Алгоритм - це точно визначений план дій виконавця, спрямований на вирішення якогось завдання. В алгоритм можна включати тільки ті команди, які є в СКІ виконавця.

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

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

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

Помилки при роботі виконавців

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

"НЕ РОЗУМІЮ" (синтаксичні)	Заданої команди немає в списку команд виконавця, і він її не зрозумів. Ймовірно, ми помилилися в запису тексту команди.
"НЕ МОЖУ" (відмови)	Виконавець зрозумів команду, але не може її виконати. Наприклад, роботу дана команда "вперед", а попереду стоїть стінка, і він не може йти. Або собаці скомандували "Сидіти!", А вона вже сидить.
ЛОГІЧНІПОМИЛКИ	Виконавець зрозумів команду і виконав її, але результат не той, що ми очікували. Причина цього - наша помилка в складанні завдання (алгоритму).

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

Як ввести нового виконавця?

* задати середовище виконавця;

* скласти СКІ:

* визначити, як передаються команди виконавцю (голосом, жестом, письмово, по рації або якось інакше);

* визначити, як виконавець виконує команди;

* визначити, в яких випадках виникає помилка "НЕ МОЖУ".

Старовинні задачі

Переправа. Селянину треба переправити через річку вовка, козу і капусту. Але крім людини човен вміщує лише або вовка, або козу, або капусту. Залишити на березі без нагляду вовка з козою чи козу з капустою не можна (З'їдять!). Як селянинові переправити свій вантаж?

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

Фальшиві монети. З 9 монет однакової гідності одна фальшива (легша). Як її знайти за два зважування за допомогою чашкових ваг без гир?

3 Посудини. У першу посудину входить 8 л, у другу - 5 л, в третю - 3 л. Першу посудину наповнено водою, а інші дві порожні. Як за допомогою цих посудин відміряти 1 л води?

У якій формі записуються алгоритми?

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

* словесна (запис на природній мові);

* графічна (зображення з графічних символів);

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

* програмна (тексти на мовах програмування).



Що таке словесний спосіб запису алгоритмів?

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

Наприклад. Записати алгоритм знаходження найбільшого спільного дільника (НСД)

двох натуральних чисел (алгоритм Евкліда).

Алгоритм може бути наступним:

1. задати два числа;

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

3. визначити більше з чисел;

4. замінити більше з чисел різницею більшого і меншого з чисел;

5. повторити алгоритм з кроку 2.

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

Словесний спосіб не має широкого розповсюдження, оскільки такі описи:

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

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

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

Що таке графічний спосіб запису алгоритмів?

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

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

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



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

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

Блок "рішення" використовується для позначення переходів управління по умові. У кожному блоці "рішення" повинні бути вказані питання, умова або порівняння, які він визначає.

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

Наприклад, алгоритм Евкліда можна представити в такій формі:

Що таке псевдокод?

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

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

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

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

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

Якими властивостями володіють алгоpітми?

Основні властивості алгоритмів наступні (приклад - кулінарний рецепт):

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

2. Дискpетність (переривчастість, роздільність) - алгоpітм повинен пpедставляти пpоцесс pішення завдання як послідовне виконання пpосто (або pаніше визначених) кроків (етапів).

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

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

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

Практичне Заняття 1

Алгоритмізація жіттєвої сітуації.

Приготування їжі, виконання побутового Завдання, Перехід через дорогу ТОЩО.

Практична Перевірка властивостей алгоритмом (результативність, дискретність, однозначність, скінченність).

Лінійні алгоритми.

Обрахунок площі, об'єму, значення функції і т.д.

Що таке "Виконавець алгоритму"?

Практика.

Найпростіщі завдання на алгоритмізацію. Складання лінійних блок-схем (Begin1, Begin7)

Робота з системами числення. Індивідуальні завдання.

Begin8, Begin11, Begin12, Begin20, Begin23, Begin25 (Абрамян М.Е. "Programming taskbook")

1-й місяць "Основні алгоритмічні структури"



Лекція 3. "Формальне представлення алгоритмічних структур, ч.1"

Базові алгоритмічні структури

Що таке базові алгоритмічні структури?

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

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

слідування, розгалуження, цикл.

Характерною особливістю базових структур є наявність у них одного входу і одного виходу.

1. Базова структура "слідування". утворюється послідовністю

дій, наступних одне за іншим:

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

закип'ятити воду

сполоснути заварювальний чайник гарячою водою

насипати заварку

залити заварку окропом

закрити чайник чим-небудь теплим

почекати 5 хвилин

... тепер можна пити чай

Лінійний алгоритм переходу через дорогу:

1. Підійти до пішохідного переходу

2. Переконатися що немає машин праворуч

3. Перейти половину дороги

4. Переконатися що немає машин зліва

5. Перейти половину дороги

Що буде якщо на дорозі є світлофор?

2. Базова структура "розгалуження". Забезпечує в залежності від результату

перевірки умови (так чи ні) вибір одного з альтернативних шляхів роботи алгоритму.

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

* якщо-то;

* якщо-то-інакше;

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

1. підійти до пішохідного переходу

якщо є світлофор, то

{

2. чекати зеленого світла

3. перейти вулицю

}

інакше

{

4. Переконатися що немає машин праворуч

5. Перейти половину дороги

6. Переконатися що немає машин ліворуч

7. Перейти половину дороги

}

Розпишемо 4 і 6 кроки детальніше.

1. підійти до пішохідного переходу

якщо є світлофор, то

{

2. чекати зеленого світла

3. перейти вулицю

}

інакше

{

4. подивитися праворуч.

Якщо машин немає, то

{

5. перейти половину дороги,

}

інакше,

{

6. чекати, поки вони проїдуть,

7. перейти половину дороги.

}

8. подивитися ліворуч,

Якщо машин немає, то

{

9. перейти дорогу до кінця,

}

інакше,

{

10. чекати, поки вони проїдуть,

11. перейти дорогу до кінця.

} }

Завдання по темі:

Розділ Boolean: 1, 2, 6, 9,16, 18, ??20

Базова структура "цикл"

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



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

Размещено на http://www.allbest.ru/

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

Перехід через дорогу з використанням циклу:

1. підійти до пішохідного переходу

якщо є світлофор, то

{

Поки (немає зеленого світла)

{

2. стояти

}

3. перейти вулицю

}

інакше

{

4. подивитися праворуч.

Якщо машин немає, то

{

5. перейти половину дороги,

}

інакше,

{

Поки (тобто машини)

{

6. стояти

}

7. перейти половину дороги.

}

8. подивитися ліворуч,

Якщо машин немає, то

{

9. перейтидорогу до кінця,

}

інакше,

{

Поки (тобто машини)

{

10. стояти

}

11. перейти дорогу до кінця.

}

}

Програми

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

...