“Lingvistikaning ba’zi bir misollari. Algoritimlarni loyhalash va tahlil qilish
![algoritm o‘zi 9-asr matematikasi nomidan kelib chiqqan Muhoammad ibn Muso al-
Xuvrizmi, kimning nisba (uni kimligini aniqlash) Xorazm) lotinlashtirildi
Algoritmi sifatida. Algoritmning zamonaviy konsepsiyasiga aylanadigan
narsalarning qisman rasmiylashtirilishi echishga urinishlar bilan boshlandi
Entscheidungsproblem (qaror muammosi) tomonidan qo‘yilgan Devid Xilbert
1928 yilda. Keyinchalik rasmiylashtirishlar "samarali hisoblash" yoki "samarali
usul". Ushbu rasmiylashtirishlarga quyidagilar kiradi Gödel–Herbrand–Kleyen
rekursiv funksiyalar 1930, 1934 va 1935 yillarda, Alonzo cherkovi"s lambda hisobi
1936 yil, Emil Post"s Formulyasiya 1 1936 yil va Alan Turing"s Turing
mashinalari 1936–37 va 1939 yillar."Algoritm" so‘zi nisba lotinlashtirishda, uning
geografik kelib chiqishini va Fors tili matematik Muhammad ibn Muso al-
Xorazmiy ga algoritm. Al-Xorazmiy (Arablashgan Fors tili 780–850) matematik,
astronom, geograf, va olim Donolik uyi yilda Bag‘dod, uning ismi "tug‘ilgan"
degan ma’noni anglatadi Xorazm’tarkibiga kirgan mintaqa Buyuk Eron va hozirda
O‘zbekiston.
Taxminan 825 yilda al-Xorazmiy an Arab tili traktat Hind-arab raqamlar
tizimiga tarjima qilingan Lotin 12 asr davomida. Qo‘lyozma jumla bilan
boshlanadi Diksit Algorizmi (’Al-Xorazmiy shunday aytgan’), bu erda "Algorizm"
tarjimon bo‘lgan Lotinlashtirish Al-Xorazmiy nomidan.[21] Al-Xorazmiy O‘rta
asrlarning oxirlarida Evropada eng ko‘p o‘qilgan matematik, birinchi navbatda
uning boshqa bir kitobi orqali Algebra. Oxirgi o‘rta asr lotin tilida, algoritm,
Inglizcha ’algoritm’, uning ismining buzilishi shunchaki "o‘nlik sanoq sistemasi"
ni anglatardi.[23] XV asrda yunoncha Rryumθ (arifmos), ’raqam’ (qarz
’arifmetik’), lotincha so‘z o‘zgartirilgan algoritmva tegishli "algoritm" inglizcha
atamasi birinchi marta 17-asrda tasdiqlangan; zamonaviy ma’no 19-asrda paydo
bo‘lgan.Ingliz tilida u dastlab taxminan 1230 yilda, keyin esa ishlatilgan Chaucyer
1391 yilda. Ingliz tili frantsuzcha atamani qabul qildi, ammo 19-asr oxirigacha
"algoritm" zamonaviy ingliz tilidagi ma’noga ega bo‘ldi.So‘zning yana bir erta
ishlatilishi - 1240 yildan boshlab, qo‘llanmada Karmen de Algorismo tomonidan
tuzilgan Aleksandr de Viledu. Bu bilan boshlanadi:Hayec algorismus ars prayesens
dicitur, qua bilan / Talibus Indorum fruimur bis quinquye figuris.bu quyidagiga
tarjima qilinadi:Algoritm - bu hozirgi paytda biz hind figuralarini ishlatadigan
san’at, ularning soni beshdan ikki marta.She’r bir necha yuz satrdan iborat bo‘lib,
yangi uslubdagi hind zarlari bilan hisoblash san’atini umumlashtiradi (Tali
Indorum) yoki hind raqamlari"Algoritm" ta’rifi bo‘yicha turli xil qarashlarni
batafsil taqdim etish uchun qarang Algoritm tavsiflari.Norasmiy ta’rif
"operasiyalar ketma-ketligini aniq belgilaydigan qoidalar to‘plami" bo‘lishi
mumkin, barcha kompyuter dasturlarini (shu jumladan raqamli hisob-kitoblarni](https://docx.uz/documents/9ffe84a6-7474-4cc3-8643-629e5cfd00d4/page_7.png?v=1)
![amalga oshirmaydigan dasturlarni) o‘z ichiga oladi va (masalan) har qanday
belgilangan byurokratik prosedura yoki oshpaz kitobi reseptUmuman olganda,
dastur oxir-oqibat to‘xtab qolgandagina algoritm bo‘ladi[30] - Garchi; .. bo‘lsa
ham cheksiz ilmoqlar ba’zan kerakli bo‘lishi mumkin.Algoritmning prototipik
misoli Evklid algoritmi, bu ikkita butun sonning maksimal umumiy bo‘luvchisini
aniqlash uchun ishlatiladi; misol (boshqalar ham bor) tomonidan tasvirlangan oqim
sxemasi yuqorida va keyingi qismda misol sifatida.Boolos, Jeffri va 1974, 1999
quyidagi iqtibosda "algoritm" so‘zining norasmiy ma’nosini taklif eting:Hech bir
inson etarlicha tez, etarlicha uzoq yoki etarlicha kichik yozolmaydi ("cheksiz va
kichikroq cheksiz ... siz molekulalar, atomlar, elektronlar ustida yozishga urinib
ko‘rgan bo‘lar edingiz). ularning nomlarini bir nechta yozuvlarda birin ketin yozish
orqali o‘rnatiladi. Ammo odamlar ma’lum darajada cheksiz to‘plamlar holatida bir
xil darajada foydali narsa qilishlari mumkin: Ular berishi mumkin ni aniqlash
bo‘yicha aniq ko‘rsatmalar n to‘plamning uchinchi a’zosi, o‘zboshimchalik bilan
cheklangan uchun n. Bunday ko‘rsatmalar aniq bir shaklda berilishi kerak ularning
ortidan hisoblash mashinasi kelishi mumkin edi, yoki tomonidan belgilar bo‘yicha
juda oddiy operasiyalarni bajarishga qodir bo‘lgan odam.
An "son-sanoqsiz cheksiz to‘plam" uning elementlari butun sonlar bilan bitta-bitta
yozishmalarga kiritilishi mumkin bo‘lgan narsadir. Shunday qilib, Boolos va Jefri
algoritm an-dan butun sonlarni "yaratadigan" jarayon uchun ko‘rsatmalarni
nazarda tutishini aytmoqdalar o‘zboshimchalik bilan nazariy jihatdan
o‘zboshimchalik bilan katta bo‘lishi mumkin bo‘lgan "kirish" tamsayılari yoki
butun sonlari. Masalan, algoritm algebraik tenglama bo‘lishi mumkin y = m + n
(ya’ni ikkita o‘zboshimchalik bilan "kirish o‘zgaruvchilari" m va n mahsulot ishlab
chiqaradigan y), ammo turli mualliflarning tushunchani aniqlashga urinishlari
shundan dalolat beradiki, bu so‘z bundan ham ko‘proq narsani anglatadi
(qo‘shimcha misol uchun):Aniq ko‘rsatmalar ("kompyuter" tushunadigan tilda)
tez, samarali, "yaxshi" uchun "kompyuter" ning "harakatlari" ni ko‘rsatadigan
jarayon (kerakli ichki ma’lumotlar va imkoniyatlar bilan jihozlangan mashina yoki
odam) o‘zboshimchalik bilan kiritilgan tamsayılar / belgilarni topish, dekodlash va
keyin ishlov berish m va n, belgilar + va = … Va "samarali "oqilona" vaqtda ishlab
chiqarish, chiqish-butun son y belgilangan joyda va belgilangan
formatda.Tushunchasi algoritm tushunchasini aniqlash uchun ham ishlatiladi
aniqlik- tushuntirish uchun markaziy tushunchadir rasmiy tizimlar ning kichik
to‘plamidan boshlab vujudga keladi aksiomalar va qoidalar. Yilda mantiq,
algoritmni bajarishni talab qiladigan vaqtni o‘lchash mumkin emas, chunki u
odatiy jismoniy o‘lchov bilan bog‘liq emas. Davom etayotgan ishni tavsiflovchi
bunday noaniqliklardan, ta’rifining mavjud emasligi kelib chiqadi algoritm bu](https://docx.uz/documents/9ffe84a6-7474-4cc3-8643-629e5cfd00d4/page_8.png?v=1)
![atamaning aniq (qandaydir ma’noda) va mavhum ishlatilishiga mos
keladi.Algoritmlar kompyuterlarning ma’lumotlarni qayta ishlashida muhim
ahamiyatga ega. Ko‘pgina kompyuter dasturlarida ishchilarning ish haqini
hisoblash yoki o‘quvchilarning hisobot kartalarini bosib chiqarish kabi belgilangan
vazifani bajarish uchun kompyuter bajarishi kerak bo‘lgan aniq ko‘rsatmalarni -
aniq tartibda batafsil bayon qiluvchi algoritmlar mavjud. Shunday qilib, algoritmni
a tomonidan simulyasiya qilinishi mumkin bo‘lgan har qanday operasiyalar ketma-
ketligi deb hisoblash mumkin Turing to‘liq tizim. Ushbu tezisni tasdiqlaydigan
mualliflar orasida Minskiy (1967), Savage (1987) va Gurevich (2000)
mavjud:Minskiy: "Ammo biz Turing bilan birga" tabiiy ravishda "samarali deb
atash mumkin bo‘lgan har qanday prosedurani (oddiy) mashina tomonidan amalga
oshirilishini davom ettiramiz. Garchi bu o‘ta tuyulishi mumkin bo‘lsa ham,
argumentlar ... uning foydasiga rad etish qiyin ".Gurevich: "... Turingning o‘zining
tezis foydasiga norasmiy argumenti kuchliroq tezisni oqlaydi: har bir algoritmni
Tyuring mashinasi tomonidan simulyasiya qilish mumkin ... Savage [1987] ga
ko‘ra, algoritm Turing mashinasi tomonidan aniqlangan hisoblash
jarayonidir".Turing mashinalari tugamaydigan hisoblash jarayonlarini belgilashi
mumkin. Algoritmlarning norasmiy ta’riflari odatda algoritm har doim tugashini
talab qiladi. Ushbu talab rasmiy prosedura algoritmini umumiy holatda imkonsiz
yoki yo‘qligini hal qilish vazifasini bajaradi - bu katta teorema tufayli. hisoblash
nazariyasi nomi bilan tanilgan muammoni to‘xtatish.
Odatda, algoritm ma’lumotni qayta ishlash bilan bog‘liq bo‘lsa, ma’lumotlarni
kirish manbasidan o‘qish, chiqish moslamasiga yozish va keyingi ishlov berish
uchun saqlash mumkin. Saqlangan ma’lumotlar algoritmni bajaruvchi sub’ektning
ichki holatining bir qismi sifatida qaraladi. Amalda davlat bir yoki bir nechtasida
saqlanadi ma’lumotlar tuzilmalariUshbu hisoblash jarayonlarining ba’zilari uchun
algoritm qat’iy belgilangan bo‘lishi kerak: yuzaga kelishi mumkin bo‘lgan barcha
sharoitlarda uning qo‘llanilish uslubida ko‘rsatilgan. Bu shuni anglatadiki, har
qanday shartli qadamlar muntazam ravishda, har holda alohida ko‘rib chiqilishi
kerak; har bir ish uchun mezon aniq (va hisoblash mumkin) bo‘lishi
kerak.Algoritm aniq qadamlarning aniq ro‘yxati bo‘lganligi sababli, hisoblash
tartibi har doim algoritmning ishlashi uchun hal qiluvchi ahamiyatga ega.
Ko‘rsatmalar odatda aniq ro‘yxatlangan deb taxmin qilinadi va "yuqoridan"
boshlanib, "pastga" tushgan deb ta’riflanadi - bu g‘oyani rasmiy ravishda
tasvirlaydigan fikr boshqaruv oqimi.Hozirga qadar algoritmni rasmiylashtirish
bo‘yicha munozaralar quyidagilarni o‘z zimmasiga olgan majburiy dasturlash. Bu
eng keng tarqalgan tushuncha - vazifani diskret, "mexanik" vositalar bilan
tavsiflashga urinish. Ushbu rasmiylashtirilgan algoritmlarning yagona konsepsiyasi](https://docx.uz/documents/9ffe84a6-7474-4cc3-8643-629e5cfd00d4/page_9.png?v=1)
![kamayishiga olib kеladi. Dеmak amal bajarilishlar soni 770 dan 97 gacha kamaydi,
ya'ni 87%. Agar erishilgan natijani 50000 bеlgidan iborat fayl ustida bajarsak,
tеjamkorlik 0.7% ni tashkil qiladi (100771 ta amal o’rniga 100098 amal
bajaramiz).Agarda barcha amallarni sikldan foydalanmay 31 ta yuklashlar orqali
bajarganimizda, vaqtni yanada tеjagan bo’lardik, ammo bu usul 0.07 foyda
kеltiradi. Ishimiz unumli bo’lmaydi. Ko’rib turganimizdеk, algoritmning bajarilish
vaqti bilan bo?liq barcha amallar bеfoyda. Tahlil tili bilan aytganda, boshlan?ich
ma'lumotlar hajmining ortishiga aloxida e'tibor qaratish kеrak.Algoritmlarni tahlil
qilishning boshqa yaxshiroq usuli - uni biror yuqori bosqichli til Pascal, C, C++,
JAVA da yozish yoki oddiy psеvdokodlarda yozishdir. Barcha algoritmlarning
asosiy boshqaruv strukturasini ifodalaganda psеvdokodlarning xossalari
ahamiyatga ega emas. Ixtiyoriy til bizning talabimizga javob bеradi, chunki for
yoki while shaklidagi sikllar, if, case yoki switch ko’rinishidagi tarmoqlanish
mеxanizmlari barcha dasturlash tillarida mavjud. Har gal biz bitta aniq algoritmni
ko’rib chiqishimizga to’?ri kеladi – unda birdan ortiq funktsiya yoki programma
fragmеnti kiritilgan bo’ladi, shuning uchun yuqorida kеltirilgan tillarning tеzligi
umuman muhim emas. Psеvdokodlardan foydalanishimizning sababi
shunda.Ko’plab dasturlash tillarida mantiqiy ifodaning qiymatlari qisqartirilgan
shaklda hisoblanadi. Bu A and V ifodadagi V hadning qiymati qachonki A rost
bo’lsagina hisoblanadi, aks holda natija V ga bog’liq bo’lmagan tarzda yolg’on
bo’ladi. Xuddi shunday A or B ifodada A ning qiymati rost bo’lsa, B hadning
qiymati hisoblanmaydi. Ko’rinib turibdiki, murakkab shartlarning 1 yoki 2 ga
tеngligidagi taqqoslashlarining sonini hisoblash shart emas.Boshlang’ich
bеrilganlar sinfiAlgoritmlarning tahlilida kiruvchi ma'lumotlarning roli yuqori,
chunki algoritm harakatlarining kеtma-kеtligi kiruvchi ma'lumotlar bilan
bеlgilanadi. Masalan, N ta elеmеntdan tashkil topgan ro’yxatning eng katta
elеmеntini topish uchun quyidagi algoritmdan foydalanish mumkin:
largest = list [l]
for i =2 to N do
if (list [i] > largest) then
largest = list[i]
end if
end for
Agar ro’yxat kamayish tartibida bo’lsa, u holda sikl boshlanishidan avval bitta
o’zlashtirish bajariladi, sikl tanasida esa o’zlashtirish bo’lmaydi. Agar ro’yxat
o’sish tartibida bo’lsa, u holda N ta o’zlashtirish bajariladi (tsikl boshlanishidan](https://docx.uz/documents/9ffe84a6-7474-4cc3-8643-629e5cfd00d4/page_16.png?v=1)
![Amaliy ish
// Topoligik chop etish uchun c++ dasturiga kiramiz
// DAG ni saralaymiz
#include <bits/stdc++.h>
using namespace std;
// Grafni ifodalash uchun sinf yaratamiz
class Graph {
// qadamlar soni
int V;
// qo’shni ro’yxatlar ro’yxatini o’z ichiga olgan massiv ko’rsatgichi
list<int>* adj;
// A function used by topologicalSort
void topologicalSortUtil(int v, bool visited[],
stack<int>& Stack);
public:
// Konstruktor
Graph(int V);
//grafikga chekka qo’shish funksiyasi
void addEdge(int v, int w);
// topologic tartibni chop etish
// to’liq grafik](https://docx.uz/documents/9ffe84a6-7474-4cc3-8643-629e5cfd00d4/page_21.png?v=1)
![void topologicalSort();
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
void Graph::addEdge(int v, int w)
{
// v ro’yxatiga w qo’shing
adj[v].push_back(w);
}
//topologic void tomonidan ishlatiladigan rekursiv funksiya
void Graph::topologicalSortUtil(int v, bool visited[],
stack<int>& Stack)
{
// joriy tugunni tashrif buyurilgan deb belgilang
visited[v] = true;
// barcha uchlar uchun takrorlash
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])](https://docx.uz/documents/9ffe84a6-7474-4cc3-8643-629e5cfd00d4/page_22.png?v=1)
![topologicalSortUtil(*i, visited, Stack);
// stack uchun joy ajratish
// natijani saqlash
Stack.push(v);
}
//topologic tartiblash funksiyasi
// It uses recursive topologicalSortUtil()
void Graph::topologicalSort()
{
stack<int> Stack;
// barcha uchlarini tashrif buyurilmagan deb belgilang
bool* visited = new bool[V];
for (int i = 0; i < V; i++)
visited[i] = false;
//rekursiv yordamchi funksiyani chaqirish
// topologic saqlash uchun
// hammasidan boshlab saralash
// birma bir uchlari
for (int i = 0; i < V; i++)
if (visited[i] == false)
topologicalSortUtil(i, visited, Stack);
// Print contents of stack](https://docx.uz/documents/9ffe84a6-7474-4cc3-8643-629e5cfd00d4/page_23.png?v=1)
![while (Stack.empty() == false) {
cout << Stack.top() << " ";
Stack.pop();
}
delete [] visited;
}
// haydochi kodi
int main()
{
//yuqoridagi diagrammada berilgan garafikni yarating
Graph g(6);
g.addEdge(5, 2);
g.addEdge(5, 0);
g.addEdge(4, 0);
g.addEdge(4, 1);
g.addEdge(2, 3);
g.addEdge(3, 1);
cout << "Following is a Topological Sort of the given "
"graph \n";
// funksiya chaqiruvi
g.topologicalSort();](https://docx.uz/documents/9ffe84a6-7474-4cc3-8643-629e5cfd00d4/page_24.png?v=1)
“Lingvistikaning ba’zi bir misollari. Algoritimlarni loyhalash va tahlil qilish