Коd swd 1336 Nomi

Kurs dasturi

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

O‘qituvchi haqida ma’lumot

O‘qituvchi	Ganihodjayeva Dilfuza Ziyavutdinovna
Laboratoriya
Каfedra	Tizimli va amaliy dasturlashtirish
Telefon raqami	[phone]
Xona	B bino, 5-etaj, № 516 xona
E-mail	[e-mail]

Kurs haqida qisqacha ma’lumot

Ushbu kurs TATU ning barcha ta’lim yo’nalishlari uchun umum- mutaxassislik fani hisoblanadi. Kurs talabalarni tuzilmalar ko’rinishida ma’lumotlarni gayta ishlash, optimal algoritimlar ishlab chiqish va dasturlash ko’nikmalarini takomillashtirishga yo’naltiradi.

Ushbu kurs quyidagi 5 ta bo’limdan iborat:

1. 
   Maʻlumotlar, tuzilmalar va obʻektga yo‘naltirilgan dasturlash.
   
2. 
   Maʻlumotlarni qidirish va saralash usullari va algoritmlari.
   
3. 
   Chiziqli maʻlumotlar tuzilmasi.
   
4. 
   Chiziqsiz maʻlumotlar tuzilmasi.
   
5. 
   Dasturiy ta’minotni testlash va tekshirish. Ma’lumotlar tuzilmalarini modellashtirish
   

Fanga qo’yilgan dastlabki talablar

Zamonaviy dasturlash tillaridan birini, jumladan C++ tilini boshlang’ich tushunchalarini va dasturlash ko’nikmalarini bilishi kerak.

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 uning holati(ma’lumotlar) va hodisalar(usullar) bog’liqligi;
  
• 
  Ob’yektga 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 tushunchalari 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:

	Bo’lim mavzulari	Soat
1.	Ma’lumot va ma’lumotlar tuzilmasi tushunchalari. Ma’lumotlarni ifodalash bosqichlari. Ma’lumotlar toifalari. Ma’lumotlar tuzilmalarini sinflashtirish.	2
2.	Dasturlash tilida sinflar. Ob’ektga yonaltirilgan dasturlash tushunchasi. Sinf va ob’ekt. Konstruktor va destruktorlar . Do‘stona funksiyalar. Istisno holatlarni qayta ishlash. Vorislik (merosho‘rlik), virtual funksiyalar va polimorfizm.	2
3.	Ma’lumotlarni qidirish usullari, algoritmlar va ularning samaradorligi.	2
4.	Ma’lumotlarni xeshlash algoritmlari. Xesh jadval va xesh funksiyalar . Ziddiyatlarni hal qilish usullari .	2
5.	Ma'lumotlarni saralash algoritmlari. Saralashning qat’iy va yashilangan usullari	2
6.	Chiziqli ma’lumotlar tuzilmalari. Statik va dinamik massivlar. Chiziqli konteynerlar va ularni qo‘llash. Iteratorlar.	2
7.	“Ro‘yxat” turdagi ma'lumotlar tuzilmalari. Ro‘yxatlarni statik va dinamik tarzda amalga oshirish. Bir va ikki bog‘lamli ro‘yxatlar va ular ustida amal bajarish algoritmlari.	2
8.	Steklar va navbatlar. Ularni mantiqiy tasvirlash va ustida amal bajarish algoritmlari. Stek va navbatni bog‘langan ro‘yxat ko‘rinishida tasvirlash	2
9.	Chiziqsiz ma’lumotlar tuzilmasi. Daraxtsimon maʻlumotlar tuzilmalari Binar va ko‘ptarmoqli daraxtlar. Taʻriflar va xususiyatlar. Daraxtlarni binar ko‘rinishga keltirish algoritmi. Rekursiya va ularni dasturlashda ishlatish.	2
10.	Heap tree ko’rinishidagi binar daraxtlarni qurish algoritmi va ular ustida amallar.	2
11.	Qidiruv binar daraxti. Qidiruv binar daraxtini qurish. Tugunlar qo‘shish va o‘chirish algoritmlari.Qidiruv binar daaxtini muvozanatlash algoritmlari.	2
12.	Maʻlumotlar tarmoq tuzilmalari. Graf tushunchasi va uning ko‘rinishlari. Graflarni tasvirlash usullari.	2
13.	Graflarda eng qisqa yo‘lni aniqlash algoritmlari. Lug‘atlar va ularni amalga oshirish.	2
14.	Dasturiy ta’minotni testlash va tekshirish. Ma’lumotlar tuzilmalarini modellashtirish. Testlash, validatsiya,verifikasiya tushunchalar va ularni farqi. Modulli testlash(oq quti, qora quti va kulrang quti).	2
15.	Ma’lumotlarlar modeli va ularni ishlatish. UML modellashtirish tili	2
	Jami	30

Laboratoriya mashg’ulotlari:

	Laboratoriya mashg’ulotlari mavzulari	Soat
1.	Dasturlash tillarida ma’lumotlarning standart turlari. Sinflarni qo’llash. Sinflarning konstruktor va destruktorlari. Qayta yuklash va qayta aniqlash usullari. Do’stona va virtual funksiyalar.	4
2.	STL komponentalar va konteynerlar bilan tanishish. Shablonlar standart kutubxonasining tuzilmasi. Iteratorlar bilan ishlash. Funksiyalarni amalga oshirish	4
3.	Qidiruv algoritmlari:chiziqli va binar qidiruv.	4
4.	Hesh funksiya va heshlash algoritmlarini tuzish	4
5.	Saralashning qat’iy va yaxshilangan usullari va ularning qo’llanilishi.	4
6.	Statik va dinamik massivlarni dasturda ifodalash. Chiziqli konteynerlar va ularni qo‘llash. Iteratorlar bilan ishlash.	4
7.	Bog'langan ro'yxat. Bir va ikki bo’glamli ro'yxat bilan ishlash	4
8.	Stek konteyneri. Stekning asosiy operatsiyalari. Stekni dasturda massiv va ro’yxat ko’rinishida ifodalash. Navbat. Navbatdagi asosiy operatsiyalar. Navbat tuzilmasini ro'yxatlar yordamida amalga oshirish	4
9.	Rekursiya va uni dasturlashda ishlatish. Rekursiv va iterative algoritmlarni ishlatishga misol	4
10.	Heap tree ko’rinishidagi daraxtlar va ularni tashkil qilish. Ustida amal bajarishga doir misollar	4
11.	Qidiruv binar daraxtlarni tashkil qilish va ustida amal bajarishga doir misollar	4
12.	Graf tushunchasi. Graflarni dasturlash tilida ifodalash usullari. Graf ko’ruvi.	4
13.	Graflarda eng qisqa yo'lni aniqlash algoritmlari	4
14.	Sinov turlarini o'rganish. Sinovni rejalashtirish. Modulli yoki iteratsion testlash ma’lumotlar to’plamini yaratish	4
15.	Ma'lumotni tasvirlash modellarini o'rganish. UML modellashtirish tili bilan ishlash	4
	Jami	60

Mustaqil ish:

№	Bo’lim mavzulari	Soat
1.	C++ tilida klasslar va ularni qo’llanilishi	4
2.	Ob’ektga yo’naltirilgan dasturlash. Vorislik, polimorfizm va inkapsyulatsiya.	6
3.	Statik ma’lumorlar tuzilmalari	4
4.	Yarimstatik ma’lumotlar tuzilmalari	4
5.	STL komponentalar va konteynerlar bilan tanishish.	4
6.	Shablonlar standart kutubxonasining tuzilmasi. Iteratorlar bilan ishlash. Funksiyalar.	4
7.	Algoritmlarni ishlab chiqish usullari va samaradorlikni baxolash	4
8.	Eng oddiy qatorlarni qayta ishlash algoritmlari	4
9.	Chiziqli va binar qidirish usullarini tadqiq qilish	4
10.	Hesh jadvallari va funksiyalari	4
11.	Saralash algoritmlari va samaradorliklari	4
12.	Rekursiv algoritmlar va ularning vazifalari	4
13.	Dinamik ma’lumotlar tuzilmalari	4
14.	Halqasimon bo’glangan ro’yxatlar	4
15.	Binary heap shaklidagi ma'lumotlar tuzilmalari	4
16.	Binar daraxtlar bilan ishlash algoritmlari	4
17.	Muvozanatlangan binar daraxtlar	4
18.	Yo'naltirilgan va yo'naltirilmagan graflar	4
19.	Minimal narxli daraxt skeleti dasturiy ta’minotini tuzish	4
20.	Graflarda eng qisqa yo’lni aniqlash algoritmlari	4
21.	Dasturiy ta’minotni sinash, testlash va tekshirish	4
22.	Sinov usullarini qiyosiy tahlil qilish	4
	Jami	90

Yuklama

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

O’qitish strategiyasi
Kurs quyidagicha ishlab chiqilgan:

• 
  ma'ruzalar paytida talaba kurs haqidagi zarur nazariy bilimlarni oladi. Semestrda bir marta oraliq nazorat o'tkaziladi.
  
• 
  Laboratoriya mashg'ulotlar davomida o'qituvchi ma'ruzalar paytida olingan nazariy bilimlarning amaliy qo'llanilishini namoyish etadi. Laboratoriya ishlari uchun har bir bo'lim oxirida talaba individual topshiriq oladi. Semestr davomida talaba 6 ta laboratoriya ishlarini bajarishi kerak.
  
• 
  Mavzularni yanada mustahkamlash uchun talabalar mustaqil ish bajaradi. Bunda talaba o’ziga berilgan mavzu bo’yicha darsda berilgan bilimlardan tashqari ma’lumotlarni izlab, mustaqil o’rganib, doir misollarni yechish dasturlarini tuzish ko’nikmasini xosil qilib, kurs oxirigacha hisobot ko’rinishida tayyorlab topshirishi talab etiladi.
  

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

Nazorat turi	Ajratilgan bali	Izoh
Oraliq nazorat. Kursning nazariy qismi bitta oraliq nazoratdan iborat.	36 ball	Imtihon uchta vazifadan iborat: ikkita nazariy va bitta amaliy. Vazifalar quyidagicha baholanadi: A. 1-vazifa (nazariy) - 11 ball mavzuni to'liq ochib berish va misolda tushuntirisi uchun. B. 2-vazifa (nazariy) – 11ball mavzuni to'liq ochib berish va misolda tushuntirishi uchun. C. 3-vazifa (amaliy topshiriq)- 14 ball qo’yilgan masalni dasturini tuza olishi uchun.
Joriy nazorat. Kurs bo’yicha 6 ta laboratoriya topshiriqlarini bajarilishi talab qilinadi.	48	Laboratoriya ishlari 6 ta bo’lib, har bir ish quyidagi ikkita vazifadan iborat va ular quyidagicha baholanadi: A. 1-vazifa (shablon namunasini amalga oshirish) – 2 ball, to'g'ri bajarilishi uchun. B. 2-vazifa (individual topshiriqni bajarish) – 6 ball, to'g'ri bajarilishi uchun. Har bir laboratoriya ishi uchun ball: 8 ball . Fan bo’yicha laboratoriya ishlari uchun umumiy ball: 8x6%=48%
Mustaqil ta’lim. Kurs bo’yicha bitta mustaqil ish bajariladi.	16 ball	Talaba kurs davomida uni qiziqtirgan har qanday mavzuni tanlashi yoki o’qituvchi tomonidan berilgan mavzu bo’yicha taqdimot qilishi va qo'lyozma shaklida hisobot taqdim etishi shart. Taqdimotni doklad qila olishi, tushuntirish qobiliyati – 10 ball; Hisobotni shakllantirishi – 6 ball.
Jami:	100 ball
Yakuniy nazorat	100 ball

Baholashning asosiy yo'nalishlari: matnning o'ziga xoslik darajasi, ish sifati, dolzarblik va ijodkorlik.

Baholash shartlari:

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

ball	Baho	Talabaning bilim darajasi
90-100	A’lo	Yetarlicha xulosalar chiqara oladi va mustaqil qaror qabul qila oladi. Ijodiy yondasha oladi. Mustaqil fikr yurita oladi va o’quv materiallari mohiyatini anglay oladi. Egallagan bilimlarini amalda qo’llay oladi. Fan bo’yicha yetarlicha bilim va tasavvurga ega.
70-89,9	yaxshi	Mustaqil fikrlay oladi. O’quv materiali mohiyatini anglay oladi. Egallagan bilimlarini amalda qo’llay oladi. Bilimni egallagan va tushuntira oladi. Fan haqida tasavvurga ega.
60-69,9	qoniqarli	Material mohiyatini tushunadi. Bilimlarini amalda qo’llay oladi. Bilimni egallagan va tushuntira oladi. Fan haqida tasavvurga ega.
0-59,9	qoniqarsiz	Fan bo’yicha aniq tasavvurga ega emas. Nazariy bilimga ega emas va masalalarni yecha olmaydi.

“Ma’lumotlar tuzilmasi va algoritmlar” fanidan rejalashtiriladigan talabalar bilimini nazorat turlari va soni, reyting baholash taqsimoti, har bir oraliq nazoratning maksimal va o’tish ballari birinchi darsda talabalarga e’lon qilinadi.

Fandan talabalar bilimini baholashning quyidagi nazoratlari o’tkaziladi:

Oraliq nazorat (ON) – talabalarning nazariy bilim va amaliy yetuklik darajalarini aniqlash va baholash usuli. Semestr davomida bir marta olinadi va yozma, og’zaki yoki test ko’rinishida bo’lishi mumkin.

Joriy nazorat (JN) – talabaning amaliy bilimini baholash usuli. Fan bo’yicha 6 ta laboratoriya topshiriqlarini bajarilishidan kelib chiqib baholanadi.

Mustaqil ish (MI) – talabaning mustaqil bilim egallay olishi va mustaqil shug’ullana olishini baholash usuli. Semestr davomida bitta mustaqil ish topshiriladi. Hisobot tayyorlab topshiriladi va taqdimot yordamida doklad qilinadi.

Yakuniy nazorat (YN) – talabalarning nazariy bilimlar va amaliy tayyorgarliklaridagi o’zgarishlarini baholash usuli. Yakuniy nazorat yozma yoki test ko’rinishida olinishi mumkin.

ON o’tkazilishi kafedra mudiri tomonidan tayinlanadigan 3 ta a’zodan iborat komissiya tomonidan o’rganilishi mumkin va uni o’tkazish tartibi buzilganda ON bekor qilinishi va qayta o’tkazilishi mumkin.

JN laboratoriya o’qituvchisi tomonidan dars jarayonida talabalarni individual topshiriqlarni bajarib topshirishlariga qarab qo’yiladi. Baholash tartibi yoki talablari buzilgan holda, kafedra mudiri tomonidan tayinlanadigan 3 ta a’zodan iborat komissiya tomonidan talabaning laboratoriya ishi o’rganilishi mumkin va qayta qabul qilinishi mumkin.

MI qabul qilish yoki baholash tartibi buzilganda kafedra mudiri tomonidan tayinlanadigan 3 ta a’zodan iborat komissiya tomonidan o’rganilishi mumkin va qayta topshirilishi mumkin.

YN kredit bo’limi tomonidan o’tkaziladi. Agar YN olish tartibi buzilsa, nazorat va natijalar bekor qilinadi va qayta olinadi.

Reyting tizimiga asoslanib, talabalar bilimi ballarda baholanadi. “Ma’lumotlar tuzilmasi va algoritmlar” fani semestr davomida 100 ballik tizimda baholanadi va quyidagicha taqsimlanadi:

[100 ball (ON+JN+MI ballari) + 100 ball(YN)]/2=100 ball (kurs bo’yicha o’rtacha ball)

Kurs bo’yicha o’tish bali – 60.

ON+JN+MI ballarining yig’indisi 60 ball, ya’ni o’tish bali va undan yuqori ball to’plagan talaba YN ga qo’yiladi. ON reyting nazorat grafigiga asosan o’tkaziladi. JN va MI semestr davomida qabul qilinadi. YN semestr oxirida grafikka asoslanib olinadi.

O’tish balini to’play olmagan talabalar YN gacha qayta ishlash va zarur ballarni to’plashi mumkin. Barcha nazoratlardan o’tish balini to’play olmagan talabalar fanni o’zlashtira olmagan va akademik qarzdor deb hisoblanadi.

YN natijasidan norozi talabalar ishni qayta ko’rib chiqish uchun, natijalar e’lonidan keyin 1 kundan kechiktirmasdan dekan nomiga ariza berish huquqiga ega.Rektor buyrug’iga asosan 3 ta a’zodan kam bo’lmagan apellyatsion komissiya tuziladi va shu kunni oz’idayoq talaba YNi qayta ko’rib chiqilib, baholanadi.

Barcha nazorat baholarining o’z vaqtida qo’yilishini kafedra mudiri, fakultet dekani, o’quv-uslubiy bo’lim, kredit bo’limi va ichki nazorat va monitoring bo’limi nazorat qiladi.

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 г.
   
6. 
   Кнут Д. Искусство программирования. T. 1. Основные алгоритмы. 3-изд. – М.: Вильямс. – 2001.
   
7. 
   Ахо А. и др. Структуры данных и алгоритмы. – М.: Вильямc. – 2000.
   
8. 
   6.1.5. Седжвик Р. Фундаментальные алгоритмы на C++. – М.: Вильямc. – 2001.
   
9. 
   6.1.6. Серебряная Л.В. Структуры и алгоритмы обработки данных: учеб.-метод. пособие/ Л.В. Серебряная, И.М. Марина. – Минск: БГУИР, 2013. – 51 с.
   
10. 
    Лэнгсам Й., Огенстайн М., Тененбаум А., Структуры данных для персональных ЭВМ. – М.: Мир. – 1989.
    
11. 
    Кинг Д. Создание эффективного ПО.– М.: Мир. – 1991.
    
12. 
    Топп У. Структуры данных в С++. – М., Бином. – 2000.