DEV Community: Samandar Komilov

Database Dizaynda Kalitlar: Hamma Joyda Kalit! 🗝

Samandar Komilov — Sat, 21 Sep 2024 20:46:23 +0000

🇺🇿 Database Dizayn desa miyaga eng birinchi nima keladi? Diagrammalar, bog'lamlar, jadvallar va hokazo shundaymi? Lekin menimcha kalitlar tasavvur qilinishi ham noto'g'ri bo'lmaydi. Chunki aynan kalitlar orqali biz database'da ma'lumotlarning yagonaligini ta'minlay olamiz.

❓ O'zi aslida Database Design nima va u bizga nimaga kerak?

Database dizayn bizga o'zi nimani xohlayotganini o'zi ham bilmagan klientning noaniq va o'ta abstrakt g'oyalarini bir qolipga solib, tartiblab, maqsadli va ishlatsa bo'ladigan bir model ko'rinishiga olib kelishga yordam beradi. Uning yordamida ma'lumotlar takrorlanishi, jadvallar o'rtasidagi ortiqcha bog'liqliklar, noaniqliklardan xalos bo'lish mumkin. Shuningdek to'g'ri dizayn qilingan database keyinchalik kengaytirilishi ham osonroq va muammosi kamroq bo'ladi.

🤔 Xo'sh yaxshi, xalq tushundi. Unda kalitlarni nima aloqasi bor?

Yaxshi savol. Yuqorida aytdik, database dizayn ma'lumotlar tartibli bo'lishi, yagonaligi, ortiqcha bog'liqliklar bo'lmasligi va hokazolarni ta'minlaydi dedik. Albatta database design bu general atama, demak bu ishlarni ichkarida kimlardir qilishi kerak. Va shu "ishchi"lardan biri bu kalitlardir.

Kalitlarning bir qancha turlari bor. Nomlari ingliz tilida "takoy" bo'lsa ham, o'zi uncha vahimali emas. Ba'zilarini o'zingiz bilmagan holda ishlatgansiz. Hozir shulardan 10 tasini (agar hammasi shu bo'lsa) ko'rib chiqamiz.

Superkey
Candidate Key
Primary Key
Alternate Key
Unique Key
Surrogate Key
Natural Key
Composite Key & Compound Key
Foreign Key

⏳ Nega bunaqa g'alati tartib? Birinchi Primary va Foreignkeylar emasmi, eng osonlari shularku? Wait for it...)

1️⃣ Superkey

Super kalit kalitlar ichidagi eng katta to'plam. Ma'lumotlar jadvalidagi bitta qatorni bir to'plam deb hisoblasak, superkey uning barcha qism to'plamlaridan iborat to'plam, faqat bitta sharti bor. Har bir qism to'plam ushbu qatorni yagonaligini ta'minlashi kerak.

Bu jadvalda qaysi ustun qatorlarning yagonaligini ta'minlaydi? Albatta id ustuni. Qiziq, faqat shu ustunmikin..?

Superkey 1: {id}
Superkey 2: {id, email}
Superkey 3: {id, Phone}
Superkey 4: {id, email, name}
Superkey 5: {id, email, phone, name}
Superkey 6: {email, phone}

Yo'q! Qatorni yagonaligini ta'minlay oladigan barcha to'plamlar superkey bo'lishi mumkin. Xususan, id qatnashgan barcha to'plamlar aniq superkey bo'la oladi, chunki id ni o'zi bir superkey.

Shuningdek, email va phone juftligi ham uniqueness berishi mumkin (O'ylab ko'ringchi nega?). Lekin e'tibor beraylik, masalan {email, name} qism to'plami superkey bo'la olmaydi, sababi xuddi shu email va name bilan boshqa odam bo'lishi mumkin (aslida yemay qoldi example, juda bo'lmasa email o'rniga country deb tasavvur qiling).

2️⃣ Candidate Key

Nomzod kalit - sodda aytganda eng minimal superkey. Superkeylar to'plamlari ichidagi eng kichik qism to'plam. Bizning yuqoridagi holatda {id} bir vaqtda superkey hamda candidate key, chunki u eng minimal superkey. Lekin {id, email} candidate key emas, sababi unda bitta redundant ustun mavjud. Ammo agar {email} ustuni yagonaligi ta'minlansa, rostdan ham emaillar takrorlanmas bo'lsa, bu qism to'plam ham candidate key bo'lishi mumkin.

3️⃣ Primary Key

Database dizayner bir vaqtning o'zida superkey va candidate key bo'lgan qism to'plamlar (ustunlar) orasidan eng mos va qulay birini tanlaydi va u asosiy kalit bo'ladi. Asosiy kalit bo'lish shartlari:

qatorning yagonaligini ta'minlay olishi
NOT NULL bo'lishi
har bir jadvalda faqatgina bitta Primary Key bo'lishi

Asosiy kalit sifatida auto-incremented integerlar, yoki UUID kabi maxsus generatsiya qilingan idlar ishlatilishi mumkin. Ularning ham turlari bor (surrogat va tabiiy) va birozdan keyin bunga to'xtalamiz.

4️⃣ Alternate Key

Muqobil Kalit - Primary Key sifatida tanlanmagan barcha kandidat kalitlar muqobil kalit bo'ladi.

Aytaylik, jadvalimizda bir nechta Unique ustunlar bor:

U holda ularning faqat bittasi Primary Key bo'la oladi, va tabiiyki qolgani unique=True bo'lsa-da, muqobil darajasida qoladi.

5️⃣ Unique Key

Unique Key - deyarli Primary Key, faqat bitta sharti bor: NULL qiymatlarni ham qabul qila oladi. Ya'ni, qatorning shu ustunida ma'lumot bo'sh bo'lishi mumkin.

Rostdan ham-da, masalan email ustunini biz Unique Key desak bo'ladi, sababi hamma user ham birdan emailini kiritmasligi mumkin. Natijada o'sha katakda bo'sh ma'lumot, NULL turadi.

Primary Key bir vaqtda Unique Key bo'lishi mumkin, lekin Unique Key bir vaqtda Primary Key bo'la olmaydi.

6️⃣ Surrogate Key

Sun'iy Kalit - default holatda har bir jadval uchun avtomatik yaratiladigan kalit bo'lib, har bir ustunni yagonaligini ta'minlaydi. Lekin u o'z nomi bilan surrogat, ya'ni haqiqiy hayotda hech nimani anglatmaydi.
Masalan,

IDsi 329 bo'lgan foydalanuvchi layk bosdi.

Bu yerda 329 nima ma'noni anglatadi? Hech nimani! U shunchaki 329-user 328-, 330- va boshqa barcha userlardan boshqa user ekanini bildiradi xolos.

Mazkur rasmda ham ko'rish mumkinki, order_id surrogat kalit, sababi u faqat uniqueness ta'minlash uchun va SERIAL tipida turibdi.

7️⃣ Natural Key

Tabiiy Kalit - jadvaldagi haqiqiy hayotda nimadir ma'no bildiradigan ustun kalit sifatida tanlanishi. Ya'ni bu holatda kalit qandaydir muhim ma'lumotni o'zida saqlaydi, yuqoridagi sun'iy kalitdan farqli ravishda. Masalan,

Emaili mematibash@gmail.com bo'lgan foydalanuvchi layk bosdi.

Bu yerda biz foydalanuvchi emailini bilyapmiz va agar istasak unga xabar yuborishimiz ham mumkin.

Bu rasmda esa Primary Key sifatida auto-increment integer emas, balki 17 talik char tanlangan va u ma'lum ma'noni anglatadi. Aniqki, bu tabiiy kalit deb atalishi mumkin.

8️⃣ Composite Key & Compound Key

Ko'pincha bu ikki atama bir xil ma'noda ishlatiladi. Sodda tushunsak, jadvaldagi bir necha ustunni birlashtirib, bitta kalit sifatida olish. Xususiy holatlarda bu atamalar boshqa-boshqa ma'no anglatishi mumkin, masalan biri ManyToMany jadvallarda ishlatilsa boshqasi ForeignKey qatnashmagan ustunlardan iborat paytlarda ishlatiladi. Lekin biz uncha chuqur kirmay turamiz.

Quyidagi StudentCourse jadvali misolida ko'raylik:

Bu holatda {StudentID, CourseID} qism to'plami Composite Key bo'lishi mumkin, chunki u har bir student qaysi kursga qatnashganini yagona tartibda aniqlab bera oladi. Shuningdek, e'tibor beraylikki, bu jadval ManyToMany bog'lami uchun ochilgan "o'rtakash" jadvaldir. Ya'ni, Student va Course jadvallari o'rtasidagi ManyToMany bog'lamni mazkur jadval ta'minlab turibdi.

9️⃣ Foreign Key

Tashqi Kalit - bir jadvalni boshqasi bilan bog'laydigan kalit. Bu ustunda boshqa bir jadvalning asosiy kaliti joylashadi va shu orqali ikki jadvalning o'zaro bog'lami ta'minlanadi.

Rasmda ko'rish mumkinki, customer_id ustuni integer tipida bo'lsa-da, boshqa customer nomli jadvalning shu nomdagi Primary Key ustuniga reference qilib turibdi. Va aynan shu narsa jadvallar o'rtasida virtual relationship, ko'rinmas ip hosil qiladi.

🏁 Shunday qilib bugun database dizaynda doim ishlatiladigan, qayerga qarasa ham topsa bo'ladigan kalitlar mavzusi haqida gaplashdik. Umid qilamanki, bu o'zimga ham o'qiganlarga ham foydali bo'ldi. E'tiboringiz uchun rahmat!

Understanding SQL Joins and Grouping using Set Theory

Samandar Komilov — Sat, 13 Jul 2024 10:13:12 +0000

🏁 In the world of databases, SQL joins are fundamental operations that allow us to combine data from multiple tables based on related columns. While SQL joins might seem daunting at first, they are conceptually rooted in Set Theory — a branch of mathematics that deals with collections of objects and operations on them.

This post aims to demystify SQL joins by exploring their relationship with set theory concepts:

Understanding Tables as Sets: In SQL, each table can be seen as a set of rows (records). Just as in set theory, these rows are unique unless explicitly defined otherwise.
Types of Joins: SQL offers several types of joins—such as inner joins, left joins, right joins, and outer joins—each serving a specific purpose in combining data from multiple tables.
Set Operations Analogies: We'll delve into how SQL joins correspond to set operations. For instance, an inner join can be likened to the intersection of two sets, where only the common elements (rows) are retained.
Visualizing Joins: Using practical examples and diagrams, we'll visualize how data from different tables intersects or combines based on join conditions.

By the end of this post, you'll have a clearer understanding of SQL joins not just as technical database operations, but as logical extensions of set theory principles.

Understanding Tables as Sets

Each table consists of some number of rows and columns, we know. In each row, there are a number of elements equal to the number of columns.

For instance, in this table, there are 4 rows with 3 elements each (3 columns). Each row is considered as a tuple in set theory and the table is a set of tuples of elements:
K = {(1, Polat, 45), (2, Memati, 40), (3, Abdulhey, 39), (4, Cahit, 35)}

So, I hope we got the point. Now, let's move onto the JOINS.

Types of Joins

There are various sources that tell distinct information about the exact number of Joins. We'll consider the following Join types:

INNER JOIN
LEFT (OUTER) JOIN
RIGHT (OUTER) JOIN
FULL (OUTER) JOIN
CROSS JOIN (Cartesian Product)
ANTI LEFT JOIN
ANTI RIGHT JOIN
ANTI OUTER JOIN

INNER JOIN

An inner join returns only the rows (tuples) that have matching values in both tables (sets).

In set theory terms, it performs an intersection of two sets. Let's say, we are inner joining A and B tables, then:

Inner Join = A ∩ B

It would be clearer if we consider elementwise, yeah? So, say we have these sets:

A = {(1, 'Pusat'), (2, 'Zaza'), (3, 'Murad')}
B = {(1, 'HR'), (2, 'IT'), (4, 'Sales')}

Then the inner join on the 1st element (employeeID) of these 2 sets will be:

A ∩ B = {(1, 'Pusat', 'HR'), (2, 'Zaza', 'IT')}

But 'Murad' and 'Sales' have different IDs, so they are not present in inner join result.

LEFT (OUTER) JOIN

A left outer join returns all the rows from the left table (set), along with the matching rows from the right table (set). If there is no match, the result is NULL from the right table.

In set theory, it can be thought of as including all elements from the left set and the intersection with the right set:

Left Outer Join = A ∪ (A ∩ B)

In terms of the above example sets, the resulting left outer join set will be like this:

A ∪ (A ∩ B) = {(1, 'Pusat', 'HR'), (2, 'Zaza', 'IT'), (3, 'Murad', NULL)}

Because, the result is all the matching rows (tuples) plus the other tuples on the left set. Due to the absence of Department for Murad, NULL will be saved.

RIGHT (OUTER) JOIN

A right outer join returns all the rows from the right table (set), along with the matching rows from the left table (set). If there is no match, the result is NULL from the left table. This is similar to the left join but includes all elements from the right set.

In set theory, it can be thought of as including all elements from the right set and the intersection with the left set:

Right Outer Join = B ∪ (A ∩ B)

In terms of the above example sets, the resulting right outer join set will be like this:

B ∪ (A ∩ B) = {(1, 'Pusat', 'HR'), (2, 'Zaza', 'IT'), (4, NULL, 'Sales')}

Because, the result is all the matching rows (tuples) plus the other tuples on the right set. Due to the absence of Name for Sales, NULL will be saved.

FULL (OUTER) JOIN

A full outer join returns all the rows when there is a match in either table (set). If there is no match, the result is NULL on the side that does not have a match.

In set theory, it is the union of both sets, including their intersection:

Full Outer Join = (A ∪ B) ∪ (A ∩ B)

In terms of the above example sets, the resulting right outer join set will be like this:

B ∪ (A ∩ B) = {(1, 'Pusat', 'HR'), (2, 'Zaza', 'IT'), (3, 'Murad', NULL), (4, NULL, 'Sales')}

This is like the sum of 2 above cases, but the matching rows participate only once in the result set.

CROSS JOIN (Cartesian Product)

A cross join produces the Cartesian product of two tables, meaning it combines each row from the first table with every row from the second table.

In set theory, there is a cartesian product operation: A × B.
In terms of the above example sets, the result becomes:

A × B = {(1, 'Pusat', 1, 'HR'), (1, 'Pusat', 2, 'IT'), ...}

The list is too long (3×3 elements), hence I left only a few of them, but you got the point.

ANTI LEFT JOIN

Returns rows from the left table (A) that do not have matching rows in the right table (B).

In set theory, this operation is similar to finding elements in set A that are not in set B, denoted as A ∖ B. The result according to the example sets above:

A ∖ B = {(3, 'Murad')}

ANTI RIGHT JOIN

Returns rows from the right table (B) that do not have matching rows in the left table (A).

In set theory, this operation is similar to finding elements in set B that are not in set A, denoted as B ∖ A. The result according to the example sets above:

B \ A = {(4, 'Sales')}

ANTI FULL JOIN

Returns rows that do not have matching rows in either table (A or B).

In set theory, this operation corresponds to the symmetric difference of sets A and B, denoted as A Δ B. The result according to the example sets above:

A Δ B = {(3, 'Murad', NULL), (4, NULL, 'Sales')}

Enough with Joins, now let's start considering Group By in terms of set theory and with examples.

GROUP BY

Sooon...

🏁 As everything in databases are constructed using mathematical concepts under the hood, it is so essential to understand the database operations using set theory operations and imagine how it is working. To study Set Theory, which is a branch of Discrete Mathematics, I recommend taking this MIT course:

https://openlearninglibrary.mit.edu/courses/course-v1:OCW+6.042J+2T2019/course/

Today, I tried to help giving the idea as I can, thanks for your attention!

Preprocessors and Macros in C

Samandar Komilov — Sun, 01 Oct 2023 13:32:22 +0000

👉 Today, I am going to consider one of the most essential but least common topics in C/C++ world - Preprocessors and Macros.

Preprocessors are programs that process the source code before compilation. There are a number of steps between writing and executing a program in C. Let us have a look at these steps before we actually start familiarizing:

Source code written by programmers is stored in a file program.c.
It is then processed by preprocessors and an expanded source code file is generated program.i.
Expanded file is compiled by the compiler and an object code file is generated program.obj.
The linker links this object code file to the object code of the library functions to generate the executable file program.exe.

Preprocessor Directives

Preprocessor programs provide preprocessor directives that tell the compiler to preprocess the source code before compiling. All of these preprocessor directives begin with a # (hash) symbol.

❗️ Remember that the # symbol only provides a path to the preprocessor, and a command such as include is processed by the preprocessor program. For example, #include will include the code or content of the specified file in your program.

The following table lists all directives:

There are 3 Main Types of Preprocessor Directives:

Macros
File Inclusion
Conditional Compilation

Let's now consider each of these directives in detail with many subtleties.

1. Macros

A macro is a piece of code in a program that is replaced by the value of the macro. Macro is defined by #define directive. Whenever a macro name is encountered by the compiler, it replaces the name with the definition of the macro. We use it always, you know, when we declare static arrays like below:

#include <stdio.h>
#define MAX 100    // Macro

int main()
{
    int array[MAX];  // Declaring array
    printf("The value of MAX" is "%d", MAX);
    return 0;
}

However, there are many other types of macros that probably you have not used yet.

1.1. Object-like Macros
An object-like macro is a simple identifier that will be replaced by a code fragment. It is called object-like because it looks like an object in code that uses it. It is popularly used to replace a symbolic name with numerical/variable represented as constant. Just now we illustrated the example above.

1.2. Chain Macros
Macros inside macros are termed as chain macros. In chain macros first of all parent macro is expanded then the child macro is expanded. Below is the illustration of a Chain Macro:

#include <stdio.h>
#define INSTAGRAM FOLLOWERS
#define FOLLOWERS 500

int main()
{
    printf("Cristiano Ronaldo has "%dM" followers on Instagram", INSTAGRAM);
    return 0;
}

// Output: Cristiano Ronaldo has 500M followers on Instagram

1.3. Multi-line Macros
An object-like macro could have a multi-line. So to create a multi-line macro you have to use backslash-newline. Below is the illustration of multiline macros:

#include <stdio.h>
#define ELE 1, \
            2, \
            3

int main()
{
    int arr[] = { ELE };
    printf("Elements of Array are:\n");
    for (int i = 0; i < 3; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

// Output: Elements of Array are: 1  2  3

1.4. Function-like Macros
These macros are the same as a function call. It replaces the entire code instead of a function name. Pair of parentheses immediately after the macro name is necessary. If we put a space between the macro name and the parentheses in the macro definition, then the macro will not work. A function-like macro is only lengthened if and only if its name appears with a pair of parentheses after it. If we don’t do this, the function pointer will get the address of the real function and lead to a syntax error.
Below is the illustration of function-like macros:

#include <stdio.h>
#define min(a, b) (((a) < (b)) ? (a) : (b))

int main()
{
    int a = 18;
    int b = 76;
    printf("Minimum value between %d and %d is %d\n", a, b, min(a, b));

    return 0;
}

// Output: Minimum value between 18 and 76 is 18

2. File Inclusion

This type of preprocessor directive tells the compiler to include a file in the source code program. The #include preprocessor directive is used to include the header files in the C/C++ program. There are 2 types of files that can be included by developer:

1. Standard Header Files
The standard header files contain definitions of pre-defined functions like printf(), scanf(), etc. These files must be included to work with these functions.

#include <file_name>

// < and > brackets tell the compiler to look for standard directory

2. User-defined Header Files
When a program becomes very large, it is a good practice to divide it into smaller files and include them whenever needed. These types of files are user-defined header files. These files can be included as:

#include "file_name"

// The double quotes ( ” ” ) tell the compiler to search for the header file in the source file’s directory.

3. Conditional Compilation

It is a type of directive that helps to compile a specific portion of the program or to skip the compilation of some specific part of the program based on some conditions. There are the following preprocessor directives that are used to insert conditional code:

#if Directive
#ifdef Directive
#ifndef Directive
#else Directive
#elif Directive
#endif Directive

Syntax:

#ifdef macro_name
    statement1;
    statement2;
    statement3;
    .
    .
    .
    statementN;
#endif

If the macro with the name macro_name is defined, then the block of statements will execute normally, but if it is not defined, the compiler will simply skip this block of statements.

Actually, there is 2 more derivatives are available, but as they are not commonly used and #pragma is not even supported by GCC compilers, I think there is no point to show them.

📌 Interesting Facts

That's all about Preprocessors and Macros. Now, let's have fun by learning some gripping facts about them.

1️⃣ Macros can take function like arguments, the arguments are not checked for data type. For example, the following macro INCREMENT(x) can be used for x of any data type:

#include <stdio.h>
#define INCREMENT(x) ++x
int main()
{
    char* ptr = "Embedded";
    int x = 10;
    printf("%s ", INCREMENT(ptr)); // pointer to string is moved by 1 character
    printf("%d", INCREMENT(x));
    return 0;
}

// Output: mbedded  11

2️⃣ The macro arguments are not evaluated before macro expansion. For example, consider the following program:

#include <stdio.h>
#define MULTIPLY(a, b) a* b

int main()
{
    // The macro is expanded as 2 + 3 * 3 + 5, not as 5*8
    printf("%d", MULTIPLY(2 + 3, 3 + 5));
    return 0;
}

// Output: 16

This problem can be solved as shown below:

#include <stdio.h>
#define MULTIPLY(a, b) (a) * (b)

int main()
{
    // The macro is expanded as (2 + 3) * (3 + 5), as 5*8
    printf("%d", MULTIPLY(2 + 3, 3 + 5));
    return 0;
}

// Output: 40

3️⃣ The tokens passed to macros can be concatenated using operator ## called Token-Pasting operator:

#include <stdio.h>
#define merge(a, b) a##b
int main()
{
    printf("%d ", merge(12, 34));
}

// Output: 1234

4️⃣ A token passed to macro can be converted to a string literal by using # before it:

#include <stdio.h>
#define get(a) #a

int main()
{
    // Memati is changed to "Memati"
    printf("%s", get(Memati)); // Note: Memati is not a string here!
}

Output: Memati

5️⃣ The macros with arguments should be avoided as they cause problems sometimes. And Inline functions should be preferred as there is type checking parameter evaluation in inline functions. From C99 onward, inline functions are supported by C language also.

For example consider the following program. From first look the output seems to be 1, but it produces 36 as output.

#include <stdio.h>

#define square(x) x* x
int main()
{
    // Expanded as 36/6*6
    int x = 36 / square(6);
    printf("%d", x);
    return 0;
}

// Output: 36

But we can write this code as follows to get the expected result:

#include <stdio.h>

#define square(x) (x * x)
int main()
{
    // Expanded as 36/(6*6)
    int x = 36 / square(6);
    printf("%d", x);
    return 0;
}

// Output: 1

6️⃣ There are some standard macros which can be used to print program file __FILE__, Date of compilation __DATE__, Time of compilation __TIME__ and Line Number in C code __LINE__. Below is an example:

#include <stdio.h>

int main()
{
    printf("Current File :%s\n", __FILE__);
    printf("Current Date :%s\n", __DATE__);
    printf("Current Time :%s\n", __TIME__);
    printf("Line Number :%d\n", __LINE__);
    return 0;
}

// Output: Current File :/usr/share/IDE_PROGRAMS/C/other/081c548d50135ed88cfa0296159b05ca/081c548d50135ed88cfa0296159b05ca.c
Current Date :Sep  4 2019
Current Time :10:17:43
Line Number :8

Today, we completed discussing about Preprocessors and Macros in C. It turns out that although pieces of code with #s and <>s seems "negligible", they play really fundamental role in any C program.

The only one very vital topic is lasting: Bit Manipulation!
🏁 That's it for now. Thank you!

✅ Algorithm Correctness haqida

Samandar Komilov — Tue, 08 Aug 2023 20:02:01 +0000

❗️ Disclaimer: Mazkur maqola Steven Skienaning "Algorithm Design Manual" kitobidan UZ-EN aralash tilda konspekt sifatida yozilgandir. Iltimos, xato-kamchilik ko'rsangiz kommentda feedback qoldiring.

👉 Biz hozirgacha aynan algoritm haqida ko'p fikr yuritdik, hayotiy misollar orqali tasavvurga ega bo'ldik. Biroq bu approach qaysidir ma'noda siz-u bizda "Algoritm universal narsa ekan. Hamma narsa algoritm ekan" degan sodda tushunchani shakllantirgan bo'lsa ajab emas. Lekin aslida rostdan ham shundaymi?
Algoritmlar ishlashiga qarab yaxshi va yomon turlarga bo'linadi. Yaxshi algoritmning 3 xil asosiy xususiyati mavjud:

correct
efficient
easy to implement

Kitobning dastlabki chapterida correctness haqida so'z boradi va biz ham maqola davomida mazkur jihatga e'tibor qaratamiz.

📏 7-sinfda geometriya darslaridan "teorema" va "aksioma" atamalariga duch kelgansiz-a? Algoritmlarda ham xuddi shu kabi struktura ishlar ekan:
Algoritm - qabul qilishi mumkin bo'lgan har qanday input uchun har doim to'g'ri natija chiqaradigan steplar ketma-ketligi algoritmdir.
Heuristic - kamida 1 ta shunday input instance topiladiki *algoritm noto'g'ri output chiqaradi va bu heuristic deyiladi.

Keling bir misol orqali tushunib olsak.
❓ Aytaylik bir aktyorga rasmdagi kabi kinolardan takliflar kelgan. Har bir kino qancha davom etishidan qat'iy nazar bir xil pul to'laydi. Aktyor qanday algoritm orqali kinolarni tanlasa eng ko'p pul ishlay oladi?
✅ Hah, osonku degandirsiz. Ehtimol har safar eng birinchi boshlanadigan kinolarni tanlab borish kerakdir? Ha siz haqsiz va.. nohaqsiz! Agar holat quyidagi rasm kabi bo'lsachi?

E'tibor bering, agar birinchi boshlanadiganni tanlasak, boshqa hech bir kinoni tanlay olmaymiz!
Yaxshi, demak ko'proq pul topish uchun kino qisqaroq bo'lishi kerak. Demak eng qisqa kinolarni tanlab ketaversak bo'lmaydimi? Ok, siz aytgandek bo'laqolsin:

Bu holatda esa eng qisqasini tanlash eng optimal yechim bo'lmaydi. Demak bu ikki ehtimoliy yechimlar algoritm bo'la olmaydi, ular heuristicdir. Yechim esa greedy algorithm usulida bo'ladi. Ya'ni, eng tez tugaydigan kinolarni tanlab boramiz. Mazkur holatda kinolar qay tartibda joylashishidan qat'iy nazar baribir biz eng optimal yechimga ega bo'lamiz. Buni esa algoritm deb tushunish mumkin.

Mantiqan to'g'ri algoritmlar osongina xato bo'lishi mumkin.

Xo'sh, demak biz algoritm degan hamma ketma-ketlik ham to'g'ri bo'lavermas ekan. Mayli, lekin uni to'g'ri ekanini qanday aniqlash mumkin? Buning uchun bizga maxsus tool kerak va bu isbot deb ataladi.
Proper matematik isbot 3 ta asosiy qismdan tashkil topadi:

isbot qilinishi kerak bo'lgan narsa haqida aniq tavsif
isbotning bir qismi sifatida foydalanish mumkin bo'lgan, to'g'ri deb olinadigan farazlar to'plami
mazkur farazlardan isbot tomon olib boradigan mulohazalar zanjiri

Osonroq tushunadigan bo'lsak, bu xuddi biror matematik masalani yechayotganimizda masala nimani so'rayotganini aniqlab, foydalanish mumkin bo'lgan formulalarni topib, zanjir tarzida formuladan yechimga qarab yurishga o'xshaydi.

Expressing Algorithms

Algoritm haqida uning har bir qadami haqida aniq tavsif bo'lmasa fikr qilish imkonsizdir. Demak, biz albatta qandaydir usulda algoritmni ta'riflab berishimiz shart. Buni ham 3 xil usul yoxud tilda amalga oshirish mumkin:

- English
- Pseudocode
- Programming language

Har birining o'z ustunlik va kamchiliklari bor: English ko'proq natural, lekin aniqligi past. Java, C++ kabi dasturlash tillari aniq, lekin tushunish qiyin. Pseudocode esa oltin o'rtalikda - uni yozish ham o'qish ham tushunish ham oson, hamda hech qanday syntax errorlar mavjud emas. Ammo pseudocode yozishda ham eng muhim narsa aniqlik ekanini unutmaslik shart, zero ko'pgina xatoliklar psevdokodni chiroyli qilaman deb aniqlikni kamayishi va ideaning buzilishi ortidan hosil bo'ladi.

Har qanday algoritmning yuragi aniq g'oyadan iborat.

Algoritmning to'g'riligini ko'rsatish uchun bizga uning ta'rifidan tashqari yechilayotgan muammoning ham aniq tavsifi kerak bo'ladi. Bular:

barcha ruxsat etilgan input instancelar to'plami
barcha talab etilgan outputlar to'plami

Shu ikki narsa qanchalik noaniq bo'lsa, muammo ham shunchalik well-specified holatidan uzoqlashib general bo'lib boradi. Bu esa o'z navbatida muammoga yechim topishning qiyinlashishi va hatto imkonsiz qilishi mumkin.

Generalized problem uchun hech qanday efficient algoritm mavjud emas.

Demak, hatto muammo umumiy bo'lsa ham uning miqyosini qisqartirgan holda yechim topish algoritm dizaynning eng asosiy texnikalaridan biridir.

Demonstrating Incorrectness

🖋 Yana matematikaga qaytamiz. Biror ayniyatni xato ekanini isbotlash uchun qanday harakat qilardik, eslaysizmi? Bitta bo'lsa ham holat topishga harakat qilardikki ayniyat xato bo'lsin, shundaymi?
Algoritm noto'g'ri ekanini isbotlashning ham usuli shunday: xato natija beradigan instance, ya'ni counter-example topishdir. Yaxshi counter-example quyidagi xususiyatlarga ega bo'ladi:
- Verifiability: 1) shu example kiritilganda algoritm chiqaradigan natijani hisoblash; 2) algoritm xato ekanini isbotlash uchun bundan yaxshiroq natija borligini ko'rsatish.
- Simplicity: algoritm nima uchun xato ekanini aniq va oddiy holda ko'rsata olish.

Shu o'rinda kitobda counter-example topish uchun bir necha maxsus texnika va maslahatlar keltirilgan, biroq ularga to'xtalmay oldinga o'tamiz.

Induction and Recursion

Ba'zida algoritm xato ekanini counter-example usuli bilan ham ko'rsata olmaymiz. Lekin bu ham algoritm to'g'ri ekanini anglatmas ekan. Bizga baribir isbot zarur va odatda bu matematik induksiya metodi orqali amalga oshiriladi.

Rekursiya aslida matematik induksiyadir.

Ha adashmadingiz, aynan shunday. Bir o'ylab ko'ring-a, har ikkisi uchun quyidagicha umumiyliklar mavjud:

- base case (like 1 or 2)
- Divide and Conquer metodi: muammoni sub-muammolarga ajratish
- Progressive approach

Agar siz rekursiya va matematik induksiya haqida yaxshi bilsangiz, menimcha ma'noni tushundingiz.

Tez orada davomini yozaman...

🏁 Xulosa qiladigan bo'lsak, bizga algoritm tuyulgan hamma ketma-ketlik ham aslida unday bo'lmasligi mumkin ekan. Algoritm to'g'riligini isbotlash Algoritm dizaynning eng muhim fundamental bilimlaridan ekanligi tushunildi. E'tiboringiz uchun rahmat!

C da Struct, Union va Enum

Samandar Komilov — Fri, 14 Jul 2023 12:07:39 +0000

Bugun C dasturlash tilining muhim qismlaridan bo'lgan Strukturalar, Birlashmalar va Enumlar haqida gaplashamiz.

👉 Struct

Struct bu user-defined data turi bo'lib, bir necha turdagi ma'lumotlarni bir turga jamlash uchun ishlatilishi mumkin. Struct xuddi Object oriented tillardagi Classlarga o'xshab ketadi, biroq ba'zi farqlari mavjud. Struct dasturda ishlatilishidan oldin e'lon qilinishi shart. Odatda main() dan ham tashqarida e'lon qilish maslahat beriladi:

// Maqolada Student misolida beriladi.
struct Student {
    char name[100];
    int  matricula;
    ...
};

Mazkur blok struktura prototipi deb ataladi va biz unga instance hosil qilmagunimizcha xotiradan joy olmaydi.
Buni biz shu struktura tipidagi o'zgaruvchi e'lon qilish orqali amalga oshirishimiz mumkin:

struct Student {
    char name[100];
    int matricula;
    ...
} student1, student2;

struct Student student3, student4;
// 2 xil usulda struktura o'zgaruvchilari hosil qilindi.

Struktura memberlariga dot operator (.) orqali access qilinadi:

student1.matricula;
student3.name;

❗️ Struktura memberlariga declaration paytida qiymat berish mumkin emas:

struct Student {
   char name[100] = "Abdulxay"; 
   int matricula = 28;
   // Compile error!
};

Sababi yuqorida aytganimizdek, struct e'lon qilinganda xotiradan joy olmaydi toki shu turdagi o'zgaruvchi e'lon qilinmaguncha. O'zgaruvchi memberlarini initialize qilishning 3 xil usuli mavjud:

// 1-usul

// String holatida strcpy ishlatilishi shart!
strcpy(student1.name, "Hikmet");
student1.matricula = 26;

// 2-usul
struct Student student2 = {"Erhan",27};

// 3-usul
struct Student student3 = {.name = "Zaza", .matricula = 22};

- typedef
⌛️ Ba'zida struktura nomi uzun bo'lib ketadi va bu vaqtni bekorga sarf qilishi mumkin. Shu holatda typedef keywordini ishlatish maqsadga muvofiq:

typedef struct Student {
    char name[100];
    int  matricula;
    ...
} student_t;

student_t winner = {"Memati", 30};

Bu yerda yangi student_t derived type bo'yicha o'zgaruvchi e'lon qilinmoqda.

- Nested structures
OOP mavjud tillarda Class ichida Class ochish mumkin bo'lgani kabi C da ham struct ichida struct ochish mumkin. Buning ham 2 xil usuli bor:

// 1. Embedded Nesting
struct Wolves {
    char name[100];
    struct Team team {
        int no;
        int power;
        ...
    }
    ...
}

// 2. Separate Nesting
struct Team {
    int no;
    int power;
    ...
}

struct Wolves {
    char name[100];
    struct Team team;
    ...
}

Nested memberlarga access qilish ham dot operator yordamida amalga oshadi:

wolve1.team.no;
wolve2.team.power;

Nested holatida bir necha struktura alohida e'lon qilinsa-da, qiymat faqat Parent strukturaga beriladi:

struct Wolves wolve1 = {.name="Jahid", .team.no = 1, .team.power = 100};

- Structure Pointers
Biz boshqa turlarga qilganimiz kabi strukturaga ham pointer berishimiz mumkin. Bu aslida juda efficient usul bo'lib, funksiya argumentiga struct o'rniga uning pointeri kiritilishi buning bir misoli.
Struktura pointeri yordamida struct memberlariga access qilish biroz murakkab (ptr.field), shu sabab **arrow operator (->)* yordamida osonlashtirilgan:

struct Point {
    int x, y;
};

struct Point nuqta = {1,2};
struct Point* ptr = &nuqta;

// Pointer yordamida strukturaga access qilish
printf("%d %d",ptr->x, ptr->y);

- Self-referential Structures
O'z-o'ziga murojaat qiluvchi strukturalarni tushunish bizga Data Structures tomon yo'l ochadi. Chunki bu tushuncha ustiga Linked List, Tree, Graph kabi ma'lumot tuzilmalari qurilgan.
O'z-o'ziga murojaat qiluvchi - o'z turidagi boshqa o'zgaruvchilarning adresini/pointerini ham saqlaydigan struct o'zgaruvchilari. Buni misol bilan ko'rish yaxshiroq:

typedef struct Node {
    char name[50];
    int no;
    struct Node* next;
} node_t;

int main()
{
    node_t node1 = { "N1", 1, NULL };
    node_t node2 = { "N2", 2, NULL };

    // node2 ning adresini node1.next ga tenglash
    node1.next = &node2;

    // node1 ga pointer
    node_t *ptr1 = &node1;

    // node1 yordamida node2 ga access qilish
    printf("node2.name: %s\nnode2.no: %d", ptr1->next->name,
           ptr1->next->no);

    return 0;
}

Ko'rib turganimizdek, node1.next = &node2; orqali node2 ning adresi node1 da saqlanmoqda. Linked Listda ham idea shunday to'g'rimi, ya'ni o'zidan keyingi element adresini saqlashi kerak.

- Structure Padding
❓ Bir savol tug'iladi, struct xotirada qanday joy egallaydi?
✅ 32 bitli kompilyator uchun protsessor bir vaqtning o'zida faqat 4 baytni o'qiy oladi. Shu tufayli bunday kompilyatorda, xotira 4 baytlik bloklarga bo'lingan bo'ladi.

Keling bir misol ko'raylik. Berilgan rasmda quyidagi struct qurilgan:

struct student 
{
       int id1;
       int id2;
       char a;
       char b;
       float percentage;
};

Bu yerda int uchun 4 bayt, har bir belgi uchun 1 bayt. Ko'rib turganingizdek, 2 ta belgi faqat 2 bayt xotirani ajratadi va protsessor avtomatik ravishda boshqa 2 baytni bo'sh qoldirib, keyingi 4 baytlik blokga o'tadi. Bu Struct padding deb ataladi.

Shunday qilib struct bo'yicha kirish qismi tugadi. Endi Union va Enum haqida fikr yuritamiz.

👉 Union

Union ham user-defined data type va syntax jihatdan 100% struct bilan bir xil:

typedef struct {
    int x;
    float y;
    char z;
} str_t;

typedef union {
    int x;
    float y;
    char z;
} uni_t;

// Memberlarga access qilish
uni_t uni1.x = 4;

Bu ikki tuzilmaning farqi xotiradan oladigan joyda seziladi. Struktura memberlari alohida locationlarga joylashadi, Union esa barcha o'zgaruvchilar bir locationga joylashadi. Keling, o'xshatish uchun bir stupid html example keltiraman:
Struct - input:checkbox
Union - select
Ya'ni, strukturada bir necha memberlar "tanlanishi" mumkin, unionda esa faqat bittasi "tanlanadi".

Strukturaning o'lchami undagi barcha memberlar o'lchamlari yig'indisiga teng bo'lsa, Unionda esa ularning eng kattasi. Buni isbotlash uchun yuqoridagi struct va unionning o'lchamlarini topamiz:

...
int main(){
    printf("Size of struct: %lu\n", sizeof(str_t));
    printf("Size of union: %lu\n", sizeof(uni_t));

    return 0;
}

// Returns 12 and 4 respectively

Demak, struct uchun:
4 (int) + 4 (float) + 1 (char) + 3 (struct padding) = 12
bo'lsa, union uchun:
max(4 (int), 4 (float), 1 (char)) = 4

❓ Xo'sh, Union qanday hollarda ishlatiladi?
Buni bir misol bilan tushuntiramiz. Tasavvur qiling, bir o'yin yasayapmiz va unda characterlar bor. Character odam bo'lishi ham robot bo'lishi ham mumkin. Agar u odam bo'lsa, uning shaxsiyati, agar robot bo'lsa ichidagi dasturi haqidagi ma'lumotlar bo'lishi kerak. Aynan shu qismda Union bizga kerak bo'ladi:

typedef struct {
    char *name;
    bool isRobot;
    union {
        char *personality;
        int firmware_version;
    }
} character;

void print_character(character* c){
    printf("Character is : %s",c->name);
    if (c->isRobot){
        printf("Version: %d", c->firmware_version);
    } else{
        printf("Personality: %s", c->personality);
    }
}

Demak union orqali biz xuddiki dropdown menu vazifasini C da bajaryapmiz. Bu usul memory-efficient ham hisoblanadi.

- Enum

Enumeration (yoxud perebor) user-defined data type bo'lib, o'zbek tilida "sanab chiqish, hisoblash" kabi ma'nolarda keladi. Ushbu data type integral konstantalardan iborat bo'ladi:

enum Size {
    Small,
    Medium,
    Large,
    ExtraLarge
};

int main(){
    enum Size shoeSize;
    shoeSize = Small;

    printf("Shoe Size is : %d", shoeSize);

    return 0;
};

// outputs 0

Bu yerda ko'rishimiz mumkinki, biz define qilgan nomlarga enum o'zi raqam - state qo'yib berar ekan. Small keywordi birinchi turgani uchun unda state=0 bo'ladi. Biz shunchaki ularni raqamlab chiqsak va indeks bo'yicha chaqirsak ham bo'lar edi, lekin dastur readability va osonligi jihatdan enumeration bizga qulayroq. Quyidagi rasmda yanada batafsil tanishish mumkin:

🏁 Xulosa qilib aytadigan bo'lsak, Struct, Union va Enum tiplari barchasi user-defined hisoblanadi va turli holatlarda ishlatiladi. Ular ichida eng muhimi Struct bo'lib, uni "C ning Classi" deyish mumkin.
Bu maqolamiz DSA ga kirish oldidan oxirgi fundamental bilimlar haqida bo'ldi. E'tiboringiz uchun rahmat!

Dinamik xotira | Dynamic Memory allocation

Samandar Komilov — Mon, 10 Jul 2023 18:56:52 +0000

👉 Keling, avvalo Memory Allocation o'zi nima ekanligi haqida biroz so'z yuritsak.
Memory allocation deb dastur ishlashi uchun kompyuter tezkor xotirasi (RAM)dan talab etilgan miqdorda resurs/joy ajratish jarayoni tushuniladi. Xotira ajratishning 2 xil turi mavjud:

1. Static Memory Allocation
Mazkur jarayon dastur kompilyatsiya bo'layotgan paytda amalga oshadi (Compile-time allocation). Sababi bunda Stack xotiradan joy ajratiladi.

2. Dynamic Memory Allocation
Bu jarayon esa dastur ishlashni boshlagan paytda amalga oshadi (Run-time allocation). Sababi bunda Heap xotiradan joy ajratiladi. (Stack va Heap haqida keyingi maqolalarda batafsil so'z yuritamiz)

C dasturlash tilida Dinamik xotiradan joy ajratish uchun <stdlib.h> kutubxonasining 4 ta funksiyasidan foydalaniladi.

- malloc()

malloc() yoxud "memory allocation" funksiyasi belgilangan data type va o'lcham bo'yicha dinamik xotiradan joy ajratadi. Quyida bir misol ko'ramiz:

#include <stdio.h>
#include <stdlib.h>

int main() {
    int n;

    int* ptr;
    ptr = (int*) malloc(n * sizeof(int));

    if (ptr == NULL) {
        printf("Xotirada joy ajratilmadi.\n");
        exit(0);
    }

    // Pointerni dinamik array sifatida ishlatish
    for (int j = 0; j < n; ++j) {
        ptr[j] = j + 1;
    }

    return 0;
}

Dasturning maqsadi n ta integer uchun dinamik xotiradan joy ajratish. Lekin bu yerda sizeof() nega kerak? Sababi har bir ma'lumot turi xotirada turlicha joy egallaydi va biz shulardan n tasiga joy ochish uchun uning o'lchamini aniqlashimiz shart: n * sizeof(<data_type>)

Yaxshi, o'lchamni aniqladik, malloc() bizga joy ajratdi. Lekin (int*) yana nimasi?!
Void pointer - hech qayerga point qilmaydigan pointer. Ya'ni hech bir data turidagi o'zgaruvchining addressini qaytarmaydi. malloc() xotiradan joy ajratgach, shu joydagi 1-baytga nisbatan aynan void pointer qaytaradi. Chunki dastur bu joyga biz qaysi turdagi o'zgaruvchini saqlamoqchi ekanimizni bilmaydi. Natijada bu vazifani qo'lda bajarishimiz kerak bo'ladi va buni biz type-casting yoxud (<data_type>*) yordamida bajaramiz.
Finally, ajratilgan joyning 1-baytiga nisbatan integer pointerni ptr o'zgaruvchisiga assign qilamiz. Endi aynan shu o'zgaruvchi yordamida bu dinamik xotiraga access qilish mumkin bo'ladi. Dasturning oxirida esa tekshirib ko'ryapmiz: agar malloc() o'zidan NULL qaytarsa yoxud xotiradan joy ajratmasa dasturni o'chirib foydalanuvchini ogohlantirsin.

✅ Bonus sifatida Dinamik array tushunchasiga ham to'xtalamiz. Eng qiziq joyi nima bilasizmi? Hozir ko'rgan pointerimiz bir vaqtda array vazifasini bajaradi😄. Yuqoridagi kodning so'ngi blokida ko'rish mumkinki, biz pointerga array kabi access qilyapmiz, chunki ptr[j] = *(ptr+j) o'rinli.

- calloc()

calloc() yoxud "contiguous allocation" deyarli malloc() bilan bir xil, shu 2 ta nuqtadan tashqari:

u har bir ajratilgan xotira blokining qiymatini 0 ga tenglashtirib chiqadi;
malloc() dan farqli ravishda 2 ta argument qabul qiladi.

Quyida bir misol ko'ramiz:

#include <stdio.h>
#include <stdlib.h>

int main() {
    int n;

    int* ptr;
    ptr = (int*) calloc(n, sizeof(int));

    if (ptr == NULL) {
        printf("Xotirada joy ajratilmadi.\n");
        exit(0);
    }

    return 0;
}

Haqiqatan ham e'tibor bersak, bu funksiyada n va sizeof(int) vergul bilan ajratiladi, ya'ni alohida 2 ta argument sifatida.

- free()

free() funksiyasi dinamik xotiradan ajratilgan joyni bo'shatish uchun ishlatiladi. Yuqoridagi 2 funksiya ham o'zi band qilgan joyni avtomatik tarzda bo'shatmagani tufayli bu funksiyaga ehtiyoj sezamiz. Ayniqsa, cheklangan xotira bilan ishlashda bu funksiya juda qo'l keladi.

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int n;
    int *ptr1, *ptr2;

    ptr1 = (int*) malloc(n * sizeof(int));
    ptr2 = (int*) calloc(n, sizeof(int));

    if (ptr1 == NULL || ptr2 == NULL) {
        printf("Xotirada joy ajratilmadi.\n");
        exit(0);
    }

    free(ptr1);
    free(ptr2);

    return 0;
}

Ko'rinib turibdiki, free() yagona argument - ajratilgan xotiraga nisbatan pointer qabul qiladi va o'sha xotirani bo'shatadi.

- realloc()

realloc() yoxud "re-allocation" funksiyasi oldin malloc() yoki calloc() yordamida ajratilgan xotiraning taqsimotini dinamik ravishda o'zgartirish uchun ishlatiladi. Masalan oldin 4 ta integer uchun joy ajratilgan edi, endi esa 6 ta uchun ajratishimiz kerak. Quyida mazkur misolni ko'ramiz:

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int n;
    int *ptr1, *ptr2;

    n = 4;
    ptr = (int*) malloc(n * sizeof(int));

    if (ptr == NULL) {
        printf("Xotirada joy ajratilmadi.\n");
        exit(0);
    }

    n = 6;
    ptr = realloc(ptr, n * sizeof(int));

    if (ptr == NULL) {
        printf("Xotirada joy ajratilmadi.\n");
        exit(0);
    }

    free(ptr);

    return 0;
}

realloc() ishlash jarayonida avvalgi 4 ta integer uchun ajratilgan joyni saqlab qoladi va unga yana 2 ta qo'shib, 6 ta integerlik joy hosil qiladi. Agar xotirada buning uchun joy yetarli bo'lmasa, funksiya NULL qaytaradi. Shu sabab bu funksiyani ham xatolikka tekshirish maqsadga muvofiqdir.

Qo'shimcha: Dynamic Strings!

Odatda string ham static holatda bo'ladi, ammo biz uni malloc() funksiyasi yordamida boshqarishimiz mumkin. Bu ham xuddi yuqorida ko'rgan dinamik array bilan bir xil, sababi string aslida "charlar arrayi" hisoblanadi.
Shuningdek, stringni copy qilish uchun biz strcpy() ni ishlatar edik. Dinamik string uchun esa strdup() ishlatiladi:

#include <string.h>

...

char *name;

char input[30];
scanf("%s", input);

name = strdup(input);

Sababi bu funksiya avtomatik tarzda malloc() ham qiladi hamda o'lcham berilmagan dinamik string uchun kerakli joyni ochadi.

🏁 Dinamik xotira mavzusi C dasturlash tilining eng muhim qismlaridan biri hisoblanadi. Mazkur bilimni yaxshi bilish uning ustiga Data Strukturalar ilmini erkin qurish imkonini beradi.
📌 Maqolani foydali deb topgan bo'lsangiz uni share qilishingiz mumkin. E'tiboringiz uchun rahmat!