Algoritmlar nazariyasi
Ushbu kitob algoritm nazariyasiga kirish bo'lib, O'zbekiston Respublikasi Oliy va O'rta maxsus ta'lim vazirligi tomonidan tasdiqlangan o'quv dasturi asosida tuzilgan. Kitobda algoritmlash, algoritmlarni formal tasvirlash, ularning murakkablik darajasi, klassik algoritmlar, berilganlarni qayta ishlash algoritmlari, algoritmlarning berilish usullari, Tyuring, Post, Markovlarning formal algoritmik sxemalari, rekursiv funksiyalar, algoritmik echimsizlik tushunchasi, saralash, izlash va optimallash algoritmlari o'rganiladi.
Asosiy mavzular
- Algoritmlar nazariyasiga kirish: Algoritm tushunchasi, algoritmlarni formal tasvirlash usullari, algoritmlarning asosiy xossalari (aniqlik, diskretlik, ommaviylik, tushunarlilik, natijaviylik), algoritmlarni tasvirlash usullari (so'zlar orqali, formulalar bilan, grafik shaklida, jadval ko'rinishida).
- Algoritm tushunchasini formallashtirish: Intuitiv algoritm tushunchasi, algoritm ob'ekti va uning tasviri, algoritm alfaviti, algoritmni konkretlashtirish zarururati.
- Algoritmlar, ularning xossalari. Berilish usullari va strukturalari: Algoritmning asosiy xossalari, algoritmning tasvirlash usullari, chiziqli algoritmlar, tarmoqlanuvchi algoritmlar, takrorlanuvchi algoritmlar, algoritm ijrosini tekshirish.
- Tyuring mashinasi tushunchasi: Tyuring mashinasi va uning sxemasi, Tyuring mashinasi xolatlari va uning dasturi, algoritmga berilgan Tyuring ta'rifi, sonni 1 taga oshirib beruvchi Tyuring mashinasi, shtrixlar sonini hisoblab, ular o'rniga yig'indini yozadigan Tyuring mashinasi.
- Hisoblanuvchi funksiyalar va Tyuring tezisi: Hisoblanuvchi funksiyalar va sanoqli to'plamlar, hisoblanuvchi funksiyalarga oid Tyuring tezisi, Tyuring mashinalari va EHMlar.
- Post mashinasi: Asosiy tushunchalar va amallar, Post mashinasining tuzilishi, 1-Finit jarayon tushunchasi, muammoning berilish usuli va 1-Formulirovka.
- Markovning Normal algoritmlari: Normal algoritm tushunchasi, normal algoritmning bajarilish koidasi, normal algoritmda So'z va kism Suz tushunchasi, Markovning normalizasiya prinsipi, normal xisoblanuvchi funksiyalar.
- Rekursiv funksiyalar: Rekursiv funksiyalar nazariyasi hisoblanuvchi funksiyalar intuitiv tushunchasini matematik aniqlashtirish usuli sifatida, Primitiv rekursiya operatori, minimizasiya operatori, Chyorch tezisi.
- Algoritmik echimsizlik tushunchasi: Algoritmik echimsiz masalalar, uz-uziga kullanuvchanlik muammosi, Tyuring mashinasining uz-uziga kullanuvchanligi.
- Berilganlarning dinamik strukturalari: Ro'yxat dinamik strukturasi, siklik ro'yxatlar, steklar.
- Optimallash masalalari va ularni echish algoritmlari: Eng yaxshi konserva bankasi haqida masala, bir o'lchovli optimallash masalalari, bir o'lchovli masalalarini sonli echsh, ko'p o'lchovli optimallash masalalari.
- Ichki Saralash algoritmlari: "Pufakchali" saralash algoritmi, "Piramidali" saralash algoritmi, "Tez" saralash algoritmi.
- Tashqi saralash algoritmlari: Diskli xotira qurilmasining tuzilishi, Bouz-Nelson algoritmi, Ketma-ket qo'shib olish usulida saralash, takrorlanuvchi balansli saralash.
- Izlash algoritmlari: Oddiy ko'rib chiqish va binar izlash algoritmlari, Vinar daraxtda izlash algoritmlari, raqamli izlash daraxtlari.
- Arxivlash algoritmlari: Seriyalarni ketma-ket kodlash algoritmi, Xaffman algoritmi, Lempel-Ziv algoritmi.