Va kommunikatsiyalarini rivojlantirish vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari univesiteti

public class Shared {

private int a = 0, b = 1;

public void one() { a = b; }

public void two() { b = a; }

...

}

public static void main(String[] args) {

final Shared object = new Shared();

for (int i = 0; i < 1000; i++) {

new Thread() { public void run() { object.one(); } }.start();

new Thread() { public void run() { object.two(); } }.start();

}

...

}

Qulflar

Bir vaqtning o'zida faqat bitta oqim ba'zi bir ob'ektni qulflashi mumkin

Qulflangan ob'ektni blokirovka qilishga urinish, ushbu ob'ekt qulflanmaguncha oqimning to'xtatilishiga olib keladi

Qulfning mavjudligi ob'ekt bilan bog'liq barcha harakatlarga taqiq bermaydi.

Oqim 1

1. 
   Bloklaydi
   
2. 
   Ishlaydi
   
   
   Obyekt
   
3. 
   Blokdan oladi
   

Oqim 2

4. 
   Blokni ochishga harakat qiladi
   
5. 
   Kutadi
   
6. 
   Bloklaydi
   
7. 
   Ishlaydi
   

Oqim 3

3. NP sinfiga tegishli ekanligi isbotlanmagan, ammo ularga NP - to'liq masalalar keltiriladigan masalalar NP-murakkab deb nomlanadi. Bu sinf NP-to’liq masalalarning ko'plab optimallashtirish variantlarini o'z ichiga oladi.

NP-to'liq masalalarning namunalari:

• 
  Bool formulalarining bajarilish masalasi
  
• 
  “O’n beshlik” o'yinining eng qisqa yechimi
  
• 
  Kommivoyajer masalasi
  
• 
  Shteyner muammosi
  
• 
  Grafni bo'yash muammosi
  
• 
  Graf cho’qqisini qoplash masalasi
  
• 
  To’plamni qoplash masalasi
  
• 
  Graf cho’qqilarining mustaqil to’plamlari masalasi
  
• 
  Saper o’yini
  
• 
  Tetris o’yini
  

NP-murakkab masalalarni hal qilish usullari quyidagilarga bo'linadi:

• 
  aniq,
  
• 
  evristik
  
• 
  metaevristik usullari
  

Aniq usullar barcha mumkin bo'lgan yechimlarni to'liq ko’rib chiqishga (полный перебор) asoslanadi va bu o'z navbatida ularning samadorligini kamaytiradi. Evristik usullar yechimlarni nisbatan cheklangan qidirishga olib keladi va odatda maqbul vaqt ichida juda yaxshi yechimni topadi. Ammo bu usullar ham kamchilikka ega, ya'ni ular taxminiydir. Metaevristik usullar eng samarali hisoblanadi, ammo bu usullarda natijaga bevosita ta'sir qiladigan parametr mavjud, kirish ma'lumotlariga asoslanib, amalda har safar ushbu parametrni qayta hisoblash kerak.

Evristik metodlar eng katta hisoblash murakkabligiga ega. Metaevristik usullar ko'proq maqbul hisoblanadi. Lokal qidiruv usuliga asoslangan klassik evristik usullardan metaevristik metodlarning ustunligi shundaki, ular sizga eng katta yechim maydonini tadqiq qilib optimal yechimga yaqin yechimni topish imkonini beradi, lokal qidirish usullari esa lokal yechimni topgandan keyin to'xtaydi.