Коd prc 01 Nomi

Kurs dasturi

Коd	PRC 3.01
Nomi	Ma’lumotlar tuzilmasi va algoritmlar
ECTS krediti	6
O‘quv yili	2020-2021
Semestr	3

O‘qituvchi haqida ma’lumot

O‘qituvchi	Begulov Olmos Uktam o’g’li
Labarotoriya	Begulov Olmos, Ravshanov Anvar, Boytemirov Asror, Yusupov Sherali
Каfedra	Dasturiy injiniring
Telefon raqami	[phone]
Xona	4-etaj, DI kafedrasi
E-mail	[e-mail]

Kurs haqida qisqacha ma’lumot
Ushbu kurs TATU ning barcha ta’lim yonalishlari uchun umum mutaxassislik fani hisoblanadi. Kurs talabalarni tuzilmalar ko’rinishida ma’lumotlarni gayta ishlash, optimal algoritimlar ishlab chiqish va dasturlash ko’nikmalarini takomillashtirishga yonaltiradi.

Ushbu kurs quyidagi 3 bo’limdan iborat:

1. 
   Ma’lumotlar, tuzilmalar, rekursiya va ob’ektga yonaltirilgan dasturlash
   
2. 
   Standart ma’lumotlar tuzilmalari kutubxonasi
   
3. 
   Dasturiy ta’minotni testlash va tekshirish. Ma’lumotlar tuzilmalarini modellashtirish
   

Fanga qo’yilgan dastlabki talablar

Yo’q

O‘qitish natijalari:
Fanni o‘zlashtirish jarayonida talabada quyidagi qobiliyatlar rivojlantiriladi:

• 
  Ma’lumotlar tuzilmasining asosiy algoritmlaridan foydalana olish va yuqori darajali dasturlash tilida shablonlarning standart kutubxonalari imkoniyatlaridan foydalanish;
  
• 
  Ma’lumotlarni qayta ishlash usullari va algoritmlari, qidirish, saralash va xeshlash to’g’risida ma’lumotga ega bo’lish;
  
• 
  Standart ma’lumotlar tuzilmalari usullariga mo’ljallangan kutubxona funksiyalaridan masala yechishda foydalanish (bog’langan ro’yxatlar, saralangan massivlar, daraxtlar, xesh-jadvallar) ;
  
• 
  Rekursiya, rekursiv ma’lumotlar tuzilmasi, rekursiv algoritmlarni dasturlash to’g’risida ma’lumotga ega bo’lish;
  
• 
  Muammoli ob’yekt sohani obyektlar sinfiga bo’lish va unug holati(ma’lumotlar) va hodisalar(usullar) bog’liqligi;
  
• 
  Obyektga mo’ljallangan dasturlash yordamida yangi tuzilmalar ishlab chiqish(sinflar yoki shablonlar) va amallar yoki usullarni qayta ishlash va qayta aniqlashning farqlarini bilish;
  
• 
  Testlash, validatsiya,verifikasiya tushunchalar va ularni farqi to’g’risida ma’lumotlarga ega bo’lish, modulli yoki iteratsion testlash ma’lumotlar to’plamini ishlab chiqish;
  
• 
  Tegishli ma’lumotlar modeli uchun hujjatlashtirishda modellashtirishning standart notatsiyasini ishlatish(masalan UML);
  

Kursning mazmuni
Ma’ruzalar:

1. 
   Ma’lumotlar, tuzilmalar va ob’ektga yonaltirilgan dasturlash. Ushbu bo’lim ma’lumotlar tuzilmalari va bunday tuzilmalarning dasturlash jarayonlarini ob’ektga yonaltirilgan yondoshuv orqali ochib beradi.
   

Bo’lim mavzulari	Soat
1. Ma’lumotlar turlari. Abstraktsiya. Ma’lumotlar abstraktsiyasi va ma’lumotlarning abstrakt tuzilmalari (MAT).	2
2.Qidiruv va xeshlash algoritmlar. Qidiruv algoritmlar: chiziqli algoritm, tartiblangan navbatlar, binary qidiruv. Xesh jadval va xesh funksiyalar. Xesh funksiyalarga misol.	4
3. Saralash usullari. Massiv elementlarini saralash. Saralash turlari va algoritmlar samaradorligi. Yaxshilangan usullar.	4
4. Rekursiya va rekursiv triada tushunchasi. Rekursiya konsepsiyasi va qo’llanilishiga misol.Iterativ va rekursiv algoritmlar , ular orasidagi bog’lanish.	2
5.Klass va funksiyalar shablonlari. Klass va funksiyalar shablonlarini dasturlash. Shablonlarning standart kutubxonasi (ShSK). ShSK-komponentalari.	2
6.Dasturlash tilida sinflar. Do’stona funksiyalar. Inkapsulyasiya. Meroshorlik. Polimorfizm. Virtual funksiyalar . Amallar va usullarni qayta ishlash va qayta aniqlash	2

2. 
   Standart ma’lumotlar tuzilmasining kutubxonasi. Bu bo’limda tuzilmani masofaviy hizmat qilish bilan tanishtirish. Shu mavzular yordamida konteyner va foydalanuvchi shablonlar ishlatgan holda dasturlar tuzish.
   

1.Abstrakt ma’lumotlar tuzilmasidagi ro’yhat(statik va dinamik). Ro’yxatlar ustida amallar. Bog’langan ro’yhatlar. Bir bog’lamli ro’yxat. Ko’rsatgichlar bilan ishlash.	2
2.Steklar va navbatlar. Stek tuzilmasi. Stek ustida asosiy amallar. Stekni massiv va ro’yxatlar ko’rinishda ifodalash. Navbat tuzilmasi. Navbatni massiv va ro’yxatlar ko’rinishda ifodalash.	2
3. Daraxtsimon ma’lumotlar tuzilmalari. Binar va ko’ptarmoqli daraxtlar. Ta’riflar va xususiyatlar. Binar daraxtlar ustuda amallar.	2
4. Binar daraxtlar. Binar daraxtni qurish. Tugunlar qo’yish va o’chirish. Daraxtlarni binar ko’rinishga keltirish.	2
5. Ma’lumotlarning tarmoqli tuzilmalari. Graf tushunchasi va uning ko’rinishlari. Graflarni tasvirlash usullari. Eng qisqa yolni to’pish algoritmi.	2

3. Dasturiy ta’minotni testlash, tekshirish va validatsiya. Ma’lumotlarni modellashtirish. Ushbu bo’limda ma’lumotlar test to’plamini ishlab chiqishga va ma’lumotlar modelini ko’rsatishga mo’ljallangan.

1. Testlash, validatsiya,verifikasiya tushunchalar va ularni farqi. Modulli testlash(oq quti, qora quti va kulrang quti)	2
2. Ma’lumotlarlar modeli va ularni ishlatish. UML modellashtirish tili	2

Laboratoriya mashg’ulotlari:
1. Ma’lumotlar, tuzilmalar va ob’ektga mo’ljanlangan dasturlash. Bu bo’limda ob’ektga mo’ljanlangan holda ma’lumotlar tuzilmasi va ularni dasturlash jarayoni ko’rib chiqiladi. Bunda tuzilmalarning ob’ektga mo’ljanlangan dasturlashni o’rganib chiqamiz.

Blok mavzulari	Soat
1. Dasturlash tillarida ma’lumotlarning standart turlari.	2
2. Funksiyalarni amalga oshirish	2
3. Qidiruv algoritmlari:chiziqli va binary qidiruv.	2
4. Hesh funksiya va heshlash algoritmlarini tuzish	2
5. Saralash usullari va ularning qo’llanilishi.	2
6. Saralashning yaxshilangan usullari va ularning qo’llanilishi.	2
7. Rekursiya va ularni dasturlashda ishlatish	2
8. Rekursiv va iterative algoritmlarni ishlatishga misol	2
9. STL komponentalar va konteynerlar bilan tanishish. Shablonlar standart kutubxonasining tuzilmasi.	2
10. Foydalanuvchining shablonlari	2
11. Sinflarni qo’llash. Sinflarning konstruktor va destruktorlari. Qayta yuklash va qayta aniqlash usullari	2
12. Sinflarni qo’llash. Do’stona va virtual funksiyalar	2

2. Standart ma’lumotlar tuzilmasi kutubxonasi. Ushbu bo'lim chiziqli va foydalanadigan tuzilmalarning navbat tuzilishi bilan tanishishga bag'ishlangan. Ushbu mavzulardan foydalanib, konteynerlar va maxsus andozalar yordamida dasturlar yaratishingiz mumkin.

1. Konteynerlar ro'yxati. Ro'yxat operatsiyalari	2
2. Bog'langan ro'yxat. Birgalikda bog'langan ro'yxat bilan ishlash	2
3. Bog'langan ro'yxat. Ikkala bog'langan ro'yxat bilan ishlash	2
4. Konteyner steki. Stackning asosiy operatsiyalari	2
5. Stekning tuzilishi. Massiv va ro'yxatlar bilan stackni tuzish	2
6. Navbat. Navbatdagi asosiy operatsiyalar.	2
7. Navbat tuzilmasi. Ro'yxatlar yordamida navbatni amalga oshirish	2
8. Dek tuzilmasi. Asosiy operatsiyalar	2
9. Binar daraxtlarni tashkil qilish. Binar daraxtlar ustida amallar	2
10. Binar daraxtlar. Daraxt balandligi va ko’ruv .	2
11. Muvozanatlangan binar daraxtlar	2
12. Graf tushunchasi. Tasvirlash usullari	2
13. Graf tushunchasi.Eng qisqa yo'lni aniqlash algoritmlari	2

3. Dasturiy ta'minotni testlash va tekshirish. Ma'lumotlarni modellashtirish. Ushbu bo'lim test tuzish va modellashtirish usullari bilan tanishish va o'rganishga bag'ishlangan.

1. Sinov turlarini o'rganish. Sinovni rejalashtirish	4
2. Modulli yoki iteratsion testlash ma’lumotlar to’plamini yaratish	2
3. Ma'lumotni tasvirlash modellarini o'rganish. UML modellashtirish tili bilan ishlash	4

Mustaqil ish:

№	Bo’lim mavzulari	Soat
1.	Asosiy ma'lumotlar tuzilmalarini tasniflash. Abstrakt ma'lumotlar turlari	6
2.	Ma'lumotlar tuzilmalarida ishlash.	6
3.	Algoritm tushunchasi. Algoritm ishlab chiqish usullari. Algoritm sinflari	6
4.	Algoritmlarning xossalari	6
5.	Eng oddiy qatorlarni qayta ishlash algoritmlari	6
6.	Chiziqli va binar qidirish usullarini tadqiq qilish	6
7.	Rekursiv algoritmlar va ularning vazifalari	6
8.	Binar daraxtlar bilan ishlash (ishlab chiqish, qo'shish, qidirish, chiqarish)	6
9.	Muvozanatlangan binar daraxtlar	6
10.	Yo'naltirilgan va yo'naltirilmagan graflar	6
11.	Binary heap shaklidagi ma'lumotlar tuzilmalari	6
12.	Sinash, testlash va tekshirish	6
13.	Sinov usullarini qiyosiy tahlil qilish	6
14.	Ma'lumotlarni o'chirish	6
15.	Hesh jadvallari va funksiyalari	6

Yuklama

Ma’ruza	Soat
Ma’ruza	30
Amaliyot	-
Laboratoriya	60
Mustaqil ish	90
Jami	180

O’qitish strategiuasi
Kurs quyidagicha ishlab chiqilgan: ma'ruzalar paytida talaba kurs haqidagi zarur nazariy bilimlarni oladi. Semestrda bir marta oraliq nazorat o'tkaziladi. Labaratoriya mashg'ulotlar davomida o'qituvchi ma'ruzalar paytida olingan nazariy bilimlarning amaliy qo'llanilishini namoyish etadi. Labaratoriya ishlari uchun har bir bo'lim oxirida talaba individual topshiriq oladi, mavzuni yanada mustahkamlash uchun mustaqil ishlarni bajaradi. Semestr davomida talaba 6 ta laboratoriya ishlarini bajarishi kerak.

Laboratoriya vazifalari.

1. Statik ma'lumotlar tuzilmalarini o'rganish

2. Yarim statik ma'lumotlar tuzilmalarini o'rganish

3. Dinamik ma'lumotlar tuzilmalarini o'rganish

4. Daraxt ma'lumotlarini tuzilishini o'rganish

5. Tarmoq ma'lumotlarini tuzilishini o'rganish

6. Ma'lumot qidirish va saralash algoritmlari

Baholash
Kursning nazariy qismi bitta oraliq nazoratdan iborat.

Amaliy qism har bir bo'limga ko'ra 10 ta individual laboratoriya ishlaridan iborat:

Oraliq nazorat: 10%

Labaratoriya: 30% (har biri 5%)

Mustaqil ish: 10% (har biri uchun 5%)

Yakuniy nazorat: 50%

Baholashning asosiy yo'nalishlari: matnning o'ziga xoslik darajasi, ish sifati, dolzarblik va ijodkorlik. Baholash quyidagi mezonlar bo'yicha amalga oshiriladi:

1) Oraliq nazorat. Imtihon uchta vazifadan iborat: ikkita nazariy va bitta amaliy.

Vazifalar quyidagicha baholanadi:

A. 1-vazifa (nazariy). 3% mavzuni to'liq ochib berish va misolda tushuntirish.

B. 2-vazifa (nazariy). 3% mavzuni to'liq ochib berish va misolda tushuntirish.

C. 3-vazifa (amaliy topshiriq). 4% Sharxlar bilan to'g'ri bajarililgan ish uchun.

Oraliq nazoratning umumiy ballari: 10%.
2) Laboratoriya vazifasi. Laboratoriya vazifasi uchta vazifadan iborat.

Vazifalar quyidagicha baholanadi:

A. 1-vazifa (shablon namunasini amalga oshirish). 3% to'g'ri bajarilishi uchun.

B. 2-vazifa (individual topshiriqni bajarish). 5% to'g'ri bajarilishi uchun.

Laboratoriya vazifasi uchun umumiy ball: 5%.
2) Mustaqil ish. Talaba dars davomida uni qiziqtirgan har qanday mavzuni tanlashi va taqdimot va qo'lyozma shaklida hisobot taqdim etishi shart.

Mustaqil ish uchun umumiy ball: 5%.

Baholash shartlari:

Har bir amaliy ish uchun muddat belgilanadi. Amaliy topshiriq o'z vaqtida topshirilmagan taqdirda, baholash kamayadi.

Adabiyotlar
Asosiy:

1. Adam Drozdek. Data structures and algorithms in C++. Fourth edition. Cengage Learning. 2013 y.

2. Кормен Т., Лейзерсон Ч., Ривест Р. «Алгоритмы. Построение и анализ», 2013 г.
Qo’shimcha:

1. 
   Г.Шилтд Самоучитель С++. 5-е издание. “БХВ Петербург” 2010 г.
   
2. 
   Вирт Н. Алгоритмы и структуры программы//М., Оберон, 2010 г.
   
3. 
   Род Хаггарти «Дискретная математика для программистов» 2012 г.
   
4. 
   Томас Х.Кормен «Алгоритмы. Вводный курс» 2014 г.
   
5. 
   Г.Уоррен «Алгоритмические трюки для программистов», 2014 г.