Тема 1: Теория на алгоритмите 1
Алгоритмите през вековете
Изтегляне 245 Kb.
|
Свързани:
My Christmas vacation essay Hristo Yonchev, Create New Doc 09-11-2023 21.49, Êóðñîâ ïðîåêò ¹1, Êóðñîâ ïðîåêò ¹1 2, Êóðñîâ ïðîåêò ¹1 3, Реферат ХИВ
- Навигация на страницата:
- Анализ на алгоритмите
- Изчислимост
Алгоритмите през вековете300 г. пр. н. е. Евклид предлага алгоритъм, който намира най-големия общ делител на две естествени числа m и n: 1) Ако стойността на m е по-малка от тази на n, разменяме стойностите им. 2) На m даваме нова стойност: остатъка от делението на m с n. 3) Ако m е различно от 0, преминаваме към стъпка 1), като използваме новите стойности на m и n. 4) Резултатът (най-големият общ делител на двете числа) е равен на n. 250 г. пр. н. е. Простите числа, както и методите за тяхното намиране, са в основата на най-старите изчислителни задачи. Алгоритъмът на Ератостен, известен като решетото на Ератостен, датира още от 250 г. пр. н. е. Оттогава, до днес (с малки изключения), в методите за търсене на прости числа не е постигнат съществен напредък. Наскоро обаче беше направен пробив при сходна задача: намерен беше ефективен алгоритъм за проверка дали дадено число е просто. 780-850 г. Както вече споменахме, това е периодът, през който Abu Ja'far Mohammed Ben Musa al-Khwarizmi публикува "Hisab al-jabr w'al-muqabala". 1424 г. Годината, през която Ghiyath al-Din Jamshid Mas'ud al-Kashi изчислява с точност 16 знака след десетичната запетая. Анализ на алгоритмите1845 г. Гейбриел Лейм (Gabriel Lame) показва, че алгоритъмът на Евклид извършва брой деления, не повече от 5 пъти броя на десетичните цифри на по-малкото число. 1910 г. Поклингтън дефинира сложност на алгоритъм като полином, зависещ от броя на цифрите в двоичното кодиране на обработваните данни. Изчислимост1900 г. Дейвид Хилберт поставя въпроса за намирането на процедура за решаване на диофантови уравнения (полиноми с цели коефициенти) и по този начин полага основите на по-късно появилите се формални дефиниции за изчислимост. 1920-30 г. Пост предлага прост унарен модел за изчисления, известен като машина на Пост. 1930 г. Алонсо Чърч представя ламбда-смятането. 1936 г. Алън Тюринг публикува статия, където представя машината на Тюринг — формален модел за изчислимост, който освен това е физически осъществим. (Всъщност почти осъществим, тъй като формалният модел изисква неограничен размер на паметта.) Последната дата се смята за рождена на съвременния компютър. От средата на XX век (по обясними причини) теоретичната компютърна информатика започва да се развива с изключително бързи темпове, за да достигне днешния си вид. Разработени сатехники и алгоритми за решаване на широка гама от алгоритмични задачи. Те откриват пътя към истински ефективното мислене при проектиране и решаване на алгоритмични проблеми, както и при преценяване и сравняване между различни алтернативи. Изтегляне 245 Kb. Сподели с приятели:
|