Презентація на тему:
ВВЕДЕННЯ. СТРУКТУРА І ЗАДАЧІ КУРСУ. МІСЦЕ ДИСЦИПЛІНИ СЕРЕД ІНФОРМАЦІЙНИХ ДОСЛІДЖЕНЬ. АЛГОРИТМИ ТА ЇХ РОЛЬ В ІНФОРМАТИЦІ. ВЛАСТИВОСТІ І ПРИНЦИПИ АНАЛІЗУ.

Тема 1. ВВЕДЕННЯ. СТРУКТУРА І ЗАДАЧІ КУРСУ. МІСЦЕ ДИСЦИПЛІНИ СЕРЕД ІНФОРМАЦІЙНИХ ДОСЛІДЖЕНЬ. АЛГОРИТМИ ТА ЇХ РОЛЬ В ІНФОРМАТИЦІ. ВЛАСТИВОСТІ І ПРИНЦИПИ АНАЛІЗУ. А чи існує алгоритм любові…?? (риторичне запитання)

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

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

Алгоритм – одне з головних понять сучасної науки. З настанням ери інформатики – його можна віднести до найважливіших факторів цивілізації. Сучасна система поглядів на інформатику й інформацію ґрунтується на тому, що інформація є новим, надзвичайно коштовним ресурсом людства поряд з іншими, давно відомими, наприклад, енергетичними, природними, людськими. Причому цей ресурс, на відміну від інших перерахованих, не зменшується, а навпаки - росте. Це ресурс - що розширюється. Можна сміливо стверджувати, що тепер положення держави у світі визначається не тільки якістю продукту, що виробляється, кількістю енергії, що видобувається, а й обсягом і якістю інформації, що освоюється. На одній з наукових конференцій ( 1984 р.) по інформатиці, академік Самарський зобразив на слайді інформатику у вигляді красуні, що несеться по науковому океані на трьох китах. Імена тих китів: Модель, Алгоритм, Програма.

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

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

Евклід Ευκλείδης Дата народжения: III ст. до н. е. Наукові інтереси: математик

Слово алгоритм, як затверджують історики математики, з'явилося 12 століть назад і означало не термін, а ім'я. Узбецький математик Аль-Хорезмі, вчений, якому математика зобов'язана багатьма відкриттями, - був відомий європейським математикам як Алгоризмі. А повне його ім'я Абу Абд Аллах Мухаммед ібн Муса аль-Хорезмі ( близько 825 р. ) - у перекладі буквально - Батько Абдулли, Мухаммед, син Муси, уродженець Хорезмі. Його книга - «Китаб аль-джебр Валь-мукабала». Саме із трактату Аль-Хорезмі по арифметиці почалося знайомство Європи з алгоритмами - строгими процедурами для виконання арифметичних операцій. Тобто алгоритм, вірніше як алгоризм, - розумілося як керівництво до дії для рішення завдань.

Подальший розвиток математики затвердив ту думку, що рішення будь-якої проблеми повинне бути алгоритмічним. Декарт, Лейбниц, Гільберт, особливо останній стимулював алгоритмічні дослідження, запропонувавши в 1900 році на міжнародному математичному конгресі свої знамениті 23 проблеми. Для уточнення поняття алгоритм були поширені 2 точки зору : 1. Всі проблеми є алгоритмічно вирішеними. Просто ще не існують знання для їхньої побудови. 2. Існують класи завдань, для рішення яких взагалі не існує алгоритмів. Це дуже сильне твердження, тому що воно поширюється на все майбутнє.

Рене Дека рт (фр. René Descartes; лат. Renatus Cartesius — Картезий; 31 марта 1596, Лаэ (провинция Турень), ныне Декарт (департамент Эндр и Луара) — 11 февраля 1650, Стокгольм) — французский математик, философ, физик и физиолог, Готфрид Вильгельм фон Лейбниц (нем. Gottfried Wilhelm von Leibniz; 21 июня (1 июля) 1646, Лейпциг, Германия — 14 ноября 1716, Ганновер, Германия) — немецкий (саксонский) философ, математик, юрист, дипломат. Дави д Ги льберт (нем. David Hilbert; 23 января 1862 — 14 февраля 1943) — выдающийся немецкий математик-универсал, внёс значительный вклад в развитие многих математических разделов. В 1910—1920-е годы (после смерти Анри Пуанкаре) был признанным мировым лидером математиков.

Початком відліку сучасної теорії алгоритмів можна вважати роботу німецького математика Курта Гьоделя (1931 рік - теорема про неповноту символьних логік), у якій було показано, що деякі математичні проблеми не можуть бути вирішені алгоритмами визначеного класу. Проблематика роботи Гьоделя пов'язана з тим, чи збігається використаний їм клас алгоритмів із класом усіх (в інтуїтивному змісті) алгоритмів. Ця робота дала поштовх до пошуку й аналізу різних формалізацій поняття алгоритму. Перші фундаментальні роботи з теорії алгоритмів були опубліковані незалежно в 1936 році роком Аланом Т’юрингом, Алоізом Черчем і Емілем Постом. Запропоновані ними машина Т’юринга, машина Поста й лямбда-вирахування Черча були еквівалентними формалізмами алгоритму. Сформульовані ними тези (Поста й Черча-Т’юринга) стверджували еквівалентність запропонованих ними формальних систем і інтуїтивного поняття алгоритму. Важливим розвитком цих робіт стало формулювання й доказ алгоритмічно нерозв'язних проблем. В 1950 роки істотний внесок у теорію алгоритмів внесли роботи Колмогорова й Маркова.

Андрéй Николáевич Колмогóров (12 (25) апреля 1903, Тамбов — 20 октября 1987, Москва) — выдающийся советский математик, доктор физико-математических наук, профессор Московского Государственного Университета (1931), академик Академии Наук СССР (1939). Колмогоров — один из основоположников современной теории вероятностей, им получены фундаментальные результаты в топологии, математической логике, теории турбулентности, теории сложности алгоритмов и ряде других областей математики и её приложений. Андре й Андре евич Ма рков ( 9 (22 сентября) 1903, Санкт-Петербург — 11 октября 1979, Москва) — советский математик, Основные труды по теории динамических систем, топологии, топологической алгебре, теории алгоритмов и конструктивной математике. Курт Фри дрих Гёдель (нем. Kurt Friedrich Gödel, 1906—1978) — австрийский логик, математик и философ математики, наиболее известный сформулированной и доказанной им теоремой о неполноте. Пост, Эмиль Леон (англ. Post Emil Leon, 11 февраля 1897, Августов (Польша) — 21 апреля 1954, Нью-Йорк) — американский математик и логик; один из основателей многозначной логики (1921); основные труды по математической логике: алгебра Поста, классы Поста функций алгебры логики; предложил абстрактную вычислительную машину — машину Поста. Алонзо Чёрч (англ. Alonzo Church; 14 июня 1903, Вашингтон, США — 11 августа 1995, Хадсон, Огайо, США) — американский математик и логик, внесший вклад в основы информатики. А лан Матисон Тью ринг (англ. Alan Mathison Turing; 23 июня 1912 — 7 июня 1954) — английский математик, логик, криптограф, изобретатель машины Тьюринга.

До 1960-70 років набрали чинності наступні напрямки в теорії алгоритмів: класична теорія алгоритмів (формулювання завдань у термінах формальних мов, поняття задачі вирішення, введення класів складності, формулювання в 1965 році Едмондсом проблеми P=NP?, відкриття класу NP-Повних завдань і його дослідження)[1]; теорія асимптотичного аналізу алгоритмів (поняття складності й трудомісткості алгоритму, критерії оцінки алгоритмів, методи одержання асимптотичних оцінок, зокрема для рекурсивних алгоритмів, асимптотичний аналіз трудомісткості або часу виконання), у розвиток якої внесли істотний вклад Кнут, Ахо, Хопкрофт, Ульман, Карп[2,4]; теорія практичного аналізу обчислювальних алгоритмів (одержання явних функцій трудомісткості, інтервальний аналіз функцій, практичні критерії якості алгоритмів, методика вибору раціональних алгоритмів), основними роботами в цьому напрямку, мабуть, варто вважати фундаментальні праці[1,2].

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

«Алгоритм — это конечный набор правил, который определяет последовательность операций для решения конкретного множества задач и обладает пятью важными чертами: конечность, определённость, ввод, вывод, эффективность». (Д. Э. Кнут) «Алгоритм — это всякая система вычислений, выполняемых по строго определённым правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи». (А. Колмогоров) «Алгоритм — это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату». (А. Марков) «Алгоритм — точное предписание о выполнении в определенном порядке некоторой системы операций, ведущих к решению всех задач данного типа». (Философский словарь / Под ред. - М.М. Розенталя) «Алгоритм — строго детерминированная последовательность действий, описывающая процесс преобразования объекта из начального состояния в конечное, записанная с помощью понятных исполнителю команд». (Николай Дмитриевич Угринович) «Алгоритм — это последовательность действий, направленных на получение определённого результата за конечное число шагов». (ROXANstudio) «Алгоритм — это строго определённая последовательность действий, направленная на достижение определённых целей за конечное число шагов». (Привалов Егор Николаевич) «Алгоритм есть формализованная последовательность действий (событий). Алгоритм может быть записан словами и изображён схематически. Практически любое неслучайное повторяемое действие поддаётся описанию через алгоритм». ([grey_olli]) «Алгоритм — однозначно, доступно и кратко (условные понятия — названия этапа) описанная последовательность процедур для воспроизводства процесса с обусловленным задачей алгоритма результатом при заданных начальных условиях. Универсальность (или специализация) алгоритма определяется применимостью и надёжностью данного алгоритма для решения нестандартных задач». «Алгоритм — это понятные и точные предписания исполнителю совершить конечное число шагов, направленных на решение поставленной задачи». «Алгоритм — это система операторов, взятых из множества операторов некоторого исполнителя, которая полностью определяет некоторый класс алгоритмических процессов, то есть процессов, которые: дискретны; детерминированы; потенциально конечны; преобразовывают некоторые конструктивные объекты. Между операторами алгоритма и операциями (элементарными действиями) алгоритмического процесса в общем случае существует гомоморфное соответствие. Поэтому алгоритм следует также считать моделью алгоритмического процесса». (А. Копаев) «Алгоритм - это некоторый конечный набор рассчитаных на определённого исполнителя операций в результате выполнения которых через определённое число шагов может быть достигнута поставленная цель или решена задача определённого типа». «Алгоритм — это последовательность действий, либо приводящая к решению задачи, либо поясняющая почему это решение получить нельзя».

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

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

Розвиток теорії алгоритмів зіштовхується із труднощами, викликаними тим, що алгоритми самі по собі об'єкти досить специфічного типу й мають властивість, нетипову для математичних об'єктів, а саме семантичну властивість « мати сенс». Щодо цього теорія алгоритмів подібна до математичної логіки, чиї теореми й формули також мають сенс. Зміст терма або формули «вказівний» : терм указує на (тобто позначає ) річ, а формула – на факт. Зміст алгоритму «наказовий» : алгоритм повинен бути виконаний. Таким чином, теорія, що вивчає алгоритми, може трактуватися як свого роду лінгвістика наказових пропозицій. Математики ще не звикли звертатися належним чином з лінгвістичними об'єктами, що несуть на собі зміст. Тому при створенні адекватної теорії алгоритмів напрямну роль повинна грати семантика, чисто математичних підхід для цієї мети недостатній ( якщо вважати, що чисто математичний підхід не повинен використовувати – як технічне поняття – поняття змісту) . У теорію алгоритмів входить на однакових правах з поняттям алгоритму, ще й поняття числення. Подібно термам, формулам і алгоритмам, числення також є носіями змісту: однак зміст їх не вказівний і не наказовий, а вирішальний. Тому теорію алгоритмів, як дисципліну, що склалася до теперішнього часу, було б вірніше йменувати теорією алгоритмів і числення [4].

При використанні алгоритмів для рішення практичних завдань ми зіштовхуємося із проблемою раціонального вибору алгоритму рішення завдання. Рішення проблеми вибору пов'язане з побудовою системи порівняльних оцінок, що у свою чергу істотно опирається на формальну модель алгоритму. Узагальнюючи результати різних розділів теорії алгоритмів можна виділити наступні цілі й співвіднесені з ними завдання, розв'язувані в теорії алгоритмів [ 1-10]: формалізація поняття «алгоритм» і дослідження формальних алгоритмічних систем; формальний доказ алгоритмічної нерозв'язності ряду завдань; класифікація завдань, визначення й дослідження класів складності; асимптотичний аналіз складності алгоритмів; дослідження й аналіз рекурсивних алгоритмів; одержання явних функцій трудомісткості з метою порівняльного аналізу алгоритмів; розробка критеріїв порівняльної оцінки якості алгоритмів.

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

1. Т.Кормен, Ч. Лейзерсон, Р.Риверст, К.Штайн Алгоритмы: построение и анализ.-М.: Вильямс, 2005.-1296 с. 2. Д.Кнут Искусство программирования, в 3-х томах, -М.: Вильямс, 2000. 3. Р.Седжвик Фундаментальне алгоритмы на С++.- Киев:Диасофт, 2001.-688 с. 4. В.А. Успенський, А.Л. Семенов Теория алгоритмов: основные открытия и приложения.- М.: Наука, 1987.- 245 с. 5. А.Ахо, Д.Хопкрофт, Д.Ульман Структуры даннях и алгоритмы.-М.:Вільямс, 2003.-384 с. 6. Дж. А. Андерсон Дискретная математика и комбинаторика: Пер. С англ..- М.:Вильямс, 2003.-960 с. 7. М.Ф. Бондаренко, Н.В.Білоус, А.Г. Руткас Комп’ютерна дискретна математика.-Харків: Компанія СМІТ, 2004.-480 с. 8. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов.-М.: ФИЗМАТЛИТ, 2004.-256 с. 9. Н.Вирт Алгоритмы и структуры данных.-М.: Мир,1989.-360 с.