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

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




Назва1. введення. Структура І задачі курсу. Місце дисципліни серед інформаційних досліджень. Алгоритми та їх роль в інформатиці. Властивості І принципи аналізу
Дата30.09.2012
Розмір445 b.
ТипДокументи


Тема 1. ВВЕДЕННЯ. СТРУКТУРА І ЗАДАЧІ КУРСУ. МІСЦЕ ДИСЦИПЛІНИ СЕРЕД ІНФОРМАЦІЙНИХ ДОСЛІДЖЕНЬ. АЛГОРИТМИ ТА ЇХ РОЛЬ В ІНФОРМАТИЦІ. ВЛАСТИВОСТІ І ПРИНЦИПИ АНАЛІЗУ.

  • А чи існує алгоритм любові…??

  • (риторичне запитання)


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

  • Автори огляду основних досягнень теорії алгоритмів стверджують:

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





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

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



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

  • На одній з наукових конференцій ( 1984 р.) по інформатиці, академік Самарський зобразив на слайді інформатику у вигляді красуні, що несеться по науковому океані на трьох китах. Імена тих китів: Модель, Алгоритм, Програма.



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

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



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





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



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

  • Для уточнення поняття алгоритм були поширені 2 точки зору :

  • 1. Всі проблеми є алгоритмічно вирішеними. Просто ще не існують знання для їхньої побудови.

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





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

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

  • В 1950 роки істотний внесок у теорію алгоритмів внесли роботи Колмогорова й Маркова.





  • До 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 с.



Схожі:

1. введення. Структура І задачі курсу. Місце дисципліни серед інформаційних досліджень. Алгоритми та їх роль в інформатиці. Властивості І принципи аналізу iconНапрям: 0907 Радіотехніка Спеціальність
Вступ. Предмет, мета та задачі курсу, його місце та роль у підготовці радіоінженера з експлуатації засобів доглядової техніки. Роль...
1. введення. Структура І задачі курсу. Місце дисципліни серед інформаційних досліджень. Алгоритми та їх роль в інформатиці. Властивості І принципи аналізу iconНапрям: 0907 Радіотехніка Спеціальність: 
Предмет, мета та задачі курсу, його місце та роль у підготовці радіоінженера з експлуатації засобів доглядової техніки. Роль доглядових...
1. введення. Структура І задачі курсу. Місце дисципліни серед інформаційних досліджень. Алгоритми та їх роль в інформатиці. Властивості І принципи аналізу iconПрограма з хімії для вступників на освітньо-кваліфікаційний рівень
Предмет І задачі хімії, Місце хімії серед природничих наук. Явища фізичні та хімічні. Екологічні проблеми хімії. Роль хімії в охороні...
1. введення. Структура І задачі курсу. Місце дисципліни серед інформаційних досліджень. Алгоритми та їх роль в інформатиці. Властивості І принципи аналізу iconХарків хнамг 2012 удк 004 : 910 : 528 (075) ббк шипулін В. Д
У посібнику представлені основні концепції І принципи аналізу географічних інформаційних систем (гіс). Розглянуті основи геопросторового...
1. введення. Структура І задачі курсу. Місце дисципліни серед інформаційних досліджень. Алгоритми та їх роль в інформатиці. Властивості І принципи аналізу iconПрограма фахового іспиту з хімії для вступників на освітньо-кваліфікаційний рівень
Предмет І задачі хімії. Місце хімії серед природничих наук. Явища фізичні та хімічні. Екологічні проблеми хімії. Роль хімії в охороні...
1. введення. Структура І задачі курсу. Місце дисципліни серед інформаційних досліджень. Алгоритми та їх роль в інформатиці. Властивості І принципи аналізу iconМіністерство освіти та науки україни сумський державний університет
Цілі та задачі дисципліни. Її місце в навчальному плані та роль у підготовці спеціаліста
1. введення. Структура І задачі курсу. Місце дисципліни серед інформаційних досліджень. Алгоритми та їх роль в інформатиці. Властивості І принципи аналізу iconСум ду
Поняття економічного аналізу господарської діяльності. Роль економічного аналізу в системі управління підприємством. Завдання аналізу...
1. введення. Структура І задачі курсу. Місце дисципліни серед інформаційних досліджень. Алгоритми та їх роль в інформатиці. Властивості І принципи аналізу iconНапрям: 0907 Радіотехніка Спеціальність
Предмет, мета та задачі курсу, його місце та роль у підготовці радіоінженерів з експлуатації радіонавігаційних систем аеропортів
1. введення. Структура І задачі курсу. Місце дисципліни серед інформаційних досліджень. Алгоритми та їх роль в інформатиці. Властивості І принципи аналізу iconДиференційований залік для студентів 2 курсу стоматологічного факультету загальні питання
Гігієна як наука, її місце в роботі лікаря-стоматолога. Мета, задачі і методи досліджень. Закони гігієни. Розвиток гігієни в Україні....
1. введення. Структура І задачі курсу. Місце дисципліни серед інформаційних досліджень. Алгоритми та їх роль в інформатиці. Властивості І принципи аналізу iconНапрям: 0907 Радіотехніка Спеціальність: 
...
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©zavantag.com 2000-2013
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи