Thursday, December 11, 2014

Дэд тэмдэгт мөр хайх Морисс-Праттын алгоритм

Энэ алгоритм нь бүх боломжийг шалгах алгоритмын үед хийгдэж байсан х тэмдэгт мөрийн зүүнээс баруун тийш чиглэлтэй, нэг тэмдэгтийн алхамтай шилжилтүүдийн алхмыг уртасган, тоог багасгадаг.


n урттай y тэмдэгт мөрөөс m урттай х тэмдэгт мөрийг хайж байна гэж үзье. Тухайн тохиолдолд у тэмдэгт мөрийн j дэх тэмдэгтээс (0≤j
Моррис-Праттын алгоритм дахь шилжилт (v нь u-гийн хил болно)

Алгоритмын бэлтгэл ажиллагаа болох mpNext хүснэгтийг байгуулах хугацаа O(m) ба ажиллах нийт хугацааг O(n+m) гэж үнэлж болно.

Жишээ:
void preMp(char *x, int m, int mpNext[]) {
int i, j;

i = 0;
j = mpNext[0] = -1;
while (i < m) { while (j > -1 && x[i] != x[j])
j = mpNext[j];
mpNext[++i] = ++j;
}
}


void MP(char *x, int m, char *y, int n) {
int i, j, mpNext[XSIZE];

/* Preprocessing */
preMp(x, m, mpNext);

/* Searching */
i = j = 0;
while (j < n) { while (i > -1 && x[i] != y[j])
i = mpNext[i];
i++;
j++;
if (i >= m) {
OUTPUT(j - i);
i = mpNext[i];
}
}
}

Tuesday, December 2, 2014

74. Ганнибал (Hannibal Barca)



"Тайван байдалдаа орсон улсыг зөвхөн зэр зэвсгийн дуу л сэрээж чадна"

(МЭӨ 247-183)



МЭӨ III зууны үед Газрын дундад тэнгисийн баруун хэсэгт Ромоос гадна Карфаген гэсэн хүчирхэг улс байжээ. Эдгээр улсууд ноёрхох байр суурийн төлөө урт удаан хугацааны, хатуу ширүүн дайныг эхлүүлсэн байна. Пунийн гэж нэрлэгдэх гурван дайн болж өнгөрчээ. Эцсийн эцэст Ромчууд тэмцэлд ялсан байна. Гэвч тэдний хойч үеийнхэн олон зууны дараа ч гэсэн Пунийн II дайны үед Ромын оршин суугчдад аймшиг төрүүлж байсан карфагены жанжин Ганнибалын тухай дурссаар байлаа. Ромынхны хувьд "Ганнибал гадаа ирлээ!" гэсэн үг нь хүмүүсийг асар их аюулаас сэрэмжлүүлэн, болгоомжтой байхыг анхааруулсан үг болон хувирсан байна.
Өөр нэг зүйл нь карфагены жанжны тухай зөвхөн ромын түүхчдийн бүтээлээс л олж уншиж болдог явдал билээ. Гайхалтай нь тэд өөрийн заналт дайсны тухай их л биширсэн, хүндэтгэсэн байдалтайгаар бичсэн байдаг юм.

Tuesday, September 2, 2014

Компьютерийн ухаан мэргэжлээр үзэх мэдлэгийн нэгж (Knowledge Unit)

№.KA (Мэдлэгийн муж), KU (Мэдлэгийн нэгж).Монгол
1.AL, Basic Analysis.Үндсэн Шинжилгээ
2.AL, Algorithmic Strategies.Алгоритмын Стратеги
3.AL, Fundamental Data Structures and Algorithms.Өгөгдлийн бүтэц ба алгоритмын үндэс
4.AL, Basic Automata Computability and Complexity.Автоматын үндсэн тооцоолол ба үнэлгээ
5.AR, Digital logic and digital systems.Тоон логик ба тоон систем
6.AR, Machine level representation of data.Өгөгдлийн машины түвшний дүрслэл
7.AR, Assembly level machine organization.Ассемблерийн түвшний машины зохион байгуулалт
8.AR, Memory system organization and architecture.Санах ойн системийн зохион байгуулалт ба архитектур
9.AR, Interfacing and communication.Интерфейс ба харилцаа
10.CN, Introduction to Modeling and Simulation.Загварчлал ба симуляцийн үндэс
11.DS, Sets, Relations, and Functions.Олонлог, харьцаа ба функц
12.DS, Basic Logic.Үндсэн логик
13.DS, Proof Techniques.Баталгааны техник
14.DS, Basics of Counting.Тооцооллын үндэс
15.DS, Graphs and Trees.Граф ба мод
16.DS, Discrete Probability.Дискрет магадлал
17.GV, Fundamental Concepts.Үндсэн зарчим
18.HCI, Foundations.Үндсэн зарчим
19.HCI, Designing Interaction.Харилцан үйлчлэлийн зохиомж
20.IAS, Foundational Concepts in Security.Аюулгүй байдлын үндсэн зарчим
21.IAS, Principles of Secure Design.Аюулгүй зохиомжийн зарчим
22.IAS, Defensive Programming.Хамгаалалтын програмчлал
23.IAS, Threats and Attacks.Аюул ба довтолгоо
24.IAS, Network Security.Сүлжээний аюулгүй байдал
25.IAS, Cryptography.Криптограф
26.IM, Information Management Concepts.Мэдээллийн удирдлагын зарчим
27.IM, Database Systems.Өгөгдлийн сангийн систем
28.IM, Data Modeling.Өгөгдлийн загварчлал
29.IS, Fundamental Issues.Үндсэн асуудал
30.IS, Basic Search Strategies.Хайлтын үндсэн стратеги
31.IS, Basic Knowledge Representation and Reasoning.Мэдлэгийн үндсэн дүрслэлүүд ба гаргалгаа
32.IS, Basic Machine Learning.Машинан сургалтын үндэс
33.NC, Introduction.Оршил
34.NC, Networked Applications.Сүлжээний програм
35.NC, Reliable Data Delivery.Өгөгдлийн найдвартай хүргэлт
36.NC, Routing and Forwarding.Чиглүүлэлт ба дамжуулалт
37.NC, Local Area Networks.Дотоод сүлжээ
38.NC, Resource Allocation.Нөөц хуваарилалт
39.NC, Mobility.Хөдөлгөөнт сүлжээ
40.OS, Overview of Operating Systems.Үйлдлийн систем
41.OS, Operating System Principles.Үйлдлийн системийн зарчим
42.OS, Concurrency.Зэрэгцээ боловсруулалт
43.OS, Scheduling and Dispatch.Төлөвлөлт ба диспетчер
44.OS, Memory Management.Санах ойн удирдлага
45.OS, Security and Protection.Аюулгүй байдал ба хамгаалалт
46.PD, Parallelism Fundamentals.Параллельчлалын үндэс
47.PD, Parallel Decomposition.Параллель задлал
48.PD, Communication and Coordination.Холбоо ба Зохицуулалт
49.PD, Parallel Algorithms, Analysis, and Programming.Параллель алгоритм, шинжилгээ ба програмчлал
50.PD, Parallel Architecture.Параллель архитектур
51.PL, Object-Oriented Programming.Объект хандлагат програмчлал
52.PL, Functional Programming.Функционал програмчлал
53.PL, Event-Driven and Reactive Programming.Үзэгдэлд суурилсан болон реактив програмчлал
54.PL, Basic Type Systems.Төрлийн үндсэн систем
55.PL, Program Representation.Програмын дүрслэл
56.PL, Language Translation and Execution.Хэлний хөрвүүлэлт ба биелэлт
57.SDF, Algorithms and Design.Алгоритм ба Зохиомж
58.SDF, Fundamental Programming Concepts.Програмчлалын Үндсэн Зарчим
59.SDF, Fundamental Data Structures.Үндсэн Өгөгдлийн Бүтэц
60.SDF, Development Methods.Хөгжүүлэлтийн арга
61.SE, Software Processes.Програм хангамжийн Процесс
62.SE, Software Project Management.Програм хангамжийн Төслийн Удирдлага
63.SE, Tools and Environments.Хэрэгсэл ба Орчин
64.SE, Requirements Engineering.Шаардлагын Инженерчлэл
65.SE, Software Design.Програм хангамжийн Зохиомж
66.SE, Software Construction.Програм хангамжийн Бүтээлт
67.SE, Software Verification Validation.Програм хангамжийн Шалгалтын Баталгаажуулалт
68.SE, Software Evolution.Програм хангамжийн Үнэлгээ
69.SE, Software Reliability.Програм хангамжийн Найдвартай байдал
70.SF, Computational Paradigms.Тооцооллын парадигм
71.SF, Cross-Layer Communications.Түвшин хоорондын Харилцаа
72.SF, State and State Machines.Төлөл ба Төлвийн Машин
73.SF, Parallelism.Параллельчлал
74.SF, Evaluation.Үнэлгээ
75.SF, Resource Allocation and Scheduling.Нөөц Хуваарилалт ба Төлөвлөлт
76.SF, Proximity.Төсөөтэй байдал
77.SF, Virtualization and Isolation.Виртуалчлал ба Тусгаарлалт
78.SF, Reliability through Redundancy.Илүүдлээр Найдвартай байдал үүсгэх
79.SP, Social Context.Нийгмийн Орчин
80.SP, Analytical Tools.Шинжилгээний Хэрэгсэл
81.SP, Professional Ethics.Мэргэжлийн Ёс зүй
82.SP, Intellectual Property.Оюуны Өмч
83.SP, Privacy and Civil Liberties.Хувийн мэдээлэл ба Иргэний Эрх чөлөө
84.SP, Professional Communication.Мэргэжлийн Харилцаа
85.SP, Sustainability.Тогтвортой байдал

Эх сурвалж: Computer Science Curricula 2013

Friday, August 29, 2014

Компьютерийн ухаан (Computer Science) мэргэжлээр үзэх мэдлэгийн хүрээ (Knowledge Area)

№.Код,Англи,Монгол
1.AL,Algorithms and Complexity,Алгоритм ба Үнэлгээ
2.AR,Architecture and Organization,Архитектур ба Зохион байгуулалт
3.CN,Computational Science,Тооцооллын Ухаан
4.DS,Discrete Structures,Дискрет Бүтэц
5.GV,Graphics and Visualization,График ба Визуальчлал
6.HCI,Human-Computer Interaction,Хүн-Компьютерийн Харилцаа
7.IAS,Information Assurance and Security,Мэдээллийн баталгаатай ба аюулгүй байдал
8.IM,Information Management,Мэдээллийн Менежмент
9.IS,Intelligent Systems,Ухаалаг Систем
10.NC,Networking and Communication,Сүлжээ ба Харилцаа холбоо
11.OS,Operating Systems,Үйлдлийн систем
12.PBD,Platform-Based Development,Платформд суурилсан хөгжүүлэлт
13.PD,Parallel and Distributed Computing,Параллель болон Хуваарилагдсан Тооцоолол
14.PL,Programming Languages,Програмчлалын Хэл
15.SDF,Software Development Fundamentals,Програм хангамж Хөгжүүлэлтийн Үндэс
16.SE,Software Engineering,Програм хангамжийн Инженерчлэл
17.SF,Systems Fundamentals,Системийн үндэс
18.SP,Social Issues and Professional Practice,Нийгмийн асуудлууд ба Мэргэжлийн дадлага

Эх сурвалж: Computer Science Curricula 2013

Thursday, July 17, 2014

73. Жон фон Нейман (John von Neumann)



"Хэрэв хүмүүс математикийг энгийн гэдэгт итгэхийг хүсэхгүй байгаа бол энэ нь зөвхөн тэд амьдралын бүх нарийн түвэгтэй байдлыг ойлгоогүйг харуулж байгаа юм"

(1903-1957)



Пифагор, Евклид, Архимед, Коперник, Галилей, Ньютон, Паскаль нар олон зууны туршид орчин үеийн шинжлэх ухааны үндсийг тавьсан агуу нээлтүүдийг хийсээр ирсэн. Мэдлэгт тэмүүлэх хүний чин хүсэлд хөтлөгдсөн олон математикч, физикчид манай ертөнцийг өөрчилсөөр байгаа. Хорьдугаар зуун ертөнцөд ердийн сэтгэлгээний стандартаас илүү гарсан бас нэгэн агуу хүнийг илгээсэн нь Жон фон Нейман юм.
Өөрийн ер бусын оюун ухааны хүчээр энэ гайхалтай эрдэмтэн квант физик, квант логик, функцийн шинжилгээ, олонлогийн онол, мэдээлэлзүй, эдийн засаг, цаг уур болон шинжлэх ухааны бусад олон салбарт чухал хувь нэмэр оруулжээ. Фон Нейман шинжлэх ухааны дэвшилд агуулагдаж байгаа аюулыг хүлээн зөвшөөрөхгүй байж чадаагүй юм. Цөмийн зэвсэг бүтээх болон түүнийг өргөнөөр хэрэглэх нь засагдашгүй үр дүнд хүргэх билээ. Гэвч хөгжил дэвшил нийгмийн хөгжилд хэрэгтэй юм. Жон фон Нейман алдар нэрийн төлөө хөөцөлдөггүй тул ихэвчлэн өрсөлдөгчдийнхөө "сүүдэрт" үлддэг байжээ.

Thursday, July 10, 2014

72. Гамаль Абдель Насер (Gamal Abdel Nasser)



"Бие дааж шийдвэр гаргах чадваргүй хүн өөртөө тусалж чаддаггүй"



XIX зууны эхээр албан бусаар Османы эзэнт гүрэнд хамаарч байсан Египет улс үнэндээ Их Британиас хамааралтай байв. Дэлхийн нэгдүгээр дайн дууссаны дараа уг улс тусгаар тогтнолоо олж авсан боловч энэ нь жинхэнэ биш байлаа. Улсын удирдлагыг англичууд эзэмшин тоглоомын засгийн газраар дамжуулан Египтийг удирдаж байв. Тэдний гарт колоничлогчдод асар их орлого авчирч байсан Суэцийн суваг байсаар байлаа.
Зөвхөн XX зууны дундуур л энэ байдалтай эвлэрэхийг хүсээгүй египтийн армийн хэсэг залуу офицерууд цэргийн эргэлт хийж улсдаа жинхэнэ тусгаар тогтнолыг авчрахыг оролдсон байна. Тэднийг чадварлаг улстөрч Гамаль Абдель Насер толгойлж байлаа. Тэрээр их гүрнүүдийн хоорондын маргааныг ашиглан Суэцийн сувгийг улсын өмч болгож чадсан юм. Түүний энэ амжилт египтийн бүх үндэстнийг сэрээж, арабын нэгдсэн улсыг байгуулах зорилго бүхий арабын социалист хөдөлгөөнийг амь оруулжээ.
Насер энэ зорилгыг биелүүлж чадаагүй боловч ирээдүйд арабууд энэ оролдлогоо давтвал египтийн ерөнхийлөгчийн нэр шинэ улсын бэлэг тэмдэг болж болох юм.

Tuesday, July 8, 2014

71. Жанна д'Арк (Joan of Arc)



"Хэрэв хүмүүс Бурхны дуу хоолойг сонсох чадвартай болчихвол тэд аврагдах болно!"



XV зууны эхээр Франц болон Англи улсууд дайтаж байв. Тэр дайн 50 жилийн турш үргэлжилсээр байсан боловч хаан ширээ болон газрын талаарх маргаанаа шийдэж чадахгүй, төгсгөлгүй өш хонзонд хутгалдан орсон байлаа. Энэхүү цус асгаруулсан зөрчлүүдийг түүхэнд Зуун жилийн дайн гэж нэрлэжээ.
Цөхрөлд гүнзгий автсан Франц улсыг зөвхөн гайхамшиг л аварч чадах мэт санагдаж байв. Тэгээд тэр гайхамшиг нь гарч ирсэн байна: өөрийн зовж зүдэрсэн эх орондоо туслахаар Бурхны дуу хоолойг сонсдог гэх тосгоны энгийн нэг бүсгүй иржээ. Жанна д'Арк зөвхөн армийг толгойлоод зогсоогүй цэргүүдэд ялалтанд итгэх итгэлийг өгч байв. Түүний хажууд байснаар цэргүүд Бурхныг мэдэрч, урагш давшдаг байжээ. Өөдгүй урвалт болон хов жив түүнийг үхэлд хүргэсэн боловч одоог болтол түүнийг гэгээн, ариун үйл бүтээгчийн дүрээр л дурсдаг юм.

Tuesday, June 24, 2014

ОХУ-ын Олон Улсын Мэдээлэлзүйн Олимпиадын бэлтгэлийн хөтөлбөр

IOI буюу ОУМЗО дээр дөрвөн сурагч нь бүгд алтан медаль авч чаддаг цөөхөн хэдэн улсын нэг нь ОХУ билээ. Тэдний бэлтгэлийн хөтөлбөрийг орчуулсныг доороос үзнэ үү.
ОХУ-ын Олон улсын Мэдээлэлзүйн олимпиадын бэлтгэлийн хөтөлбөр

Хөтөлбөр дэх дидактикийн нэгж бүрт олон улсын мэдээлэлзүйн олимпиадын бэлтгэлд зориулан тодорхой түвшинг оноосон байгаа. Нийтдээ доор тодорхойлсон гурван түвшин байна:
“*” гэсэн тэмдэггүй дидактикийн нэгжүүд нь анхан шатны түвшинд хамаарна. Энэ түвшний мэдлэгтэй байх нь оролцогч олон улсын олимпиадад ороход тавигдах шаардлагуудыг ойлгоход тус болно. Мөн бодлого бодох сэдэлтэй, өөрийн санааг илэрхийлэх чадвартай байна гэсэн үг юм.
“*” тэмдэгтэй дидактикийн нэгжүүдийг нэмж судлах нь оролцогчид олимпиадын бэлтгэлийн түлхүүр ойлголт, чадваруудад суралцах боломж олгоно. Мөн олимпиадын бодлогыг хангалттай түвшинд шийдэж, өөрийн боломжийг олон улсын түвшинд харуулж шагналт байруудад орох чадвартай болгоно.
“**” тэмдэгтэй дидактикийн нэгжүүдийг эзэмшсэнээр сурагчид өөрийн мэдлэгийн хүрээг тэлж, олон улсын мэдээлэлзүйн олимпиадын тэргүүн байрын төлөө өрсөлдөх чадвартай болно.
Математик үндэс
Функц, харьцаа, олонлог
Функц, урвуу функц, давхар функц
Харьцаа (рефлекс, симметр, транзитив, эквивалент, цагаан толгойн дараалал)
Олонлог (Веннийн диаграм, гүйцээлт, декартын үржвэр)
Бүрэн эрэмбэлэгдсэн олонлог*
Олонлогийн чадал ба тоологдох олонлог**
Геометрийн үндэс
Цэг, шулуун, хэрчим, вектор, өнцөг
Евклидийн огторгуй дахь Декартын координатууд
Евклидийн зай
Хавтгай дээрх вектор болон скаляр үржвэр
Гурвалжин, тэгш өнцөгт, олон өнцөгт
Гүдгэр олон өнцөгт
Тригонометрийн функцууд болон томъёонууд*
Воронойн диаграм ба Делонегийн триангуляц**
Логикийн үндэс
Логик хувьсагч, үйлдэл, илэрхийлэл
Үнэний хүснэгт
Булийн функц
Квантор (универсал, оршин байх)
Логик функцийн өгөгдөх болон үүсгэх хэлбэр
Логик илэрхийллийг хувиргах
Нормал хэлбэр (конъюнктив и дизъюнктив) *
Булийн функцийг минималчлах *
Логикийн үндсэн хуулиуд *
Предикатын логик *
Тооцооллын үндэс
Тооцооллын үндэс:
Нэмэх ба үржүүлэх дүрэм
Арифметик ба геометр прогресс
Фибоначчийн тоо
Оруулж-хасах зарчим *
Рекуррент харьцаа
Матриц ба түүн дээр гүйцэтгэх үйлдэл *
Тоо болон матрицийг хурдан үржүүлэх**
Баталгааны аргууд
Шууд баталгаа
Дирихлейн зарчим
Эсрэг жишээгээр батлах
Эсрэгцүүлэн батлах
Зөрчилд оруулан батлах
Математик индукц
Тооны онолын үндэс
Анхны тоо. Арифметикийн үндсэн теорем
Үлдэгдэлтэй хуваах
ХИЕХ
Харилцан анхны тоо
Үлдэгдлийн ангиуд*
Үлдэгдлийн тухай хятадын теорем*
Анхдагч язгуур ба дискрет логарифм**
Алгебрын үндэс
Олон гишүүнт ба түүн дээр хийгдэх үйлдлүүд. Квадрат тэгшитгэл. Виетийн теорем.
Виетийн теоремийн ерөнхий хэлбэр. Симметр олон гишүүнт*
Бүлгийн тухай ойлголт**
Бүлгийн шинж чанарууд**
Энгийн дэд бүлгүүд**
Гомоморфизм болон изоморфизмын тухай теорем**
Комбинаторикийн бодлогыг бодоход бүлгийн онолыг хэрэглэх**
Хослолын онолын үндэс
Сэлгэмэл, гүйлгэмэл ба хэсэглэл:
Үндсэн тодорхойлолт
Паскалийн дүрэм
Биномын теорем
Грейн код: дэд олонлог, хэсэглэл, сэлгэмэл*
Сэлгэмлийн инверсийн хүснэгт *
Дэд олонлогт хуваах. Стирлингийн тоо*
Хаалтуудын дараалал*
Хаалтуудын дараалал болон бусад комбинаторикийн объектуудын холбоо(хоёртын болон өлгөсөн мод, триангуляц)**
Комбинаторикийн объектуудын тооны үнэлгээ. Стирлингийн томъёо. Мөрдлөгөөнүүд.**
Графын онол
Графын төрлүүд
Зам ба холбоос
Граф дээрх үйлдлүүд
Моднууд
Холболтын мод (spanning tree)
Графыг будах
Эйлерийн болог Гамильтоны граф
Бүрхэлт ба үл хамаарал*
Графыг зурах. Хавтгай граф*
Давхар холбоост граф. Гүүр, блок, мөчлөгийн цэг*
Чиглэлтэй циклгүй граф ба эрэмбийн харьцааны холбоо. Транзитив битүүрэл*
Хоёр талт граф*
Урсгал ба сүлжээ*
Сүлжээний графикийг төлөвлөх*
К-холбоост граф**
Магадлалын онолын үндэс
Магадлал болон математик дунджийн тухай ойлголт. Магадлалын онолын аксиомууд*
Бүтэн магадлалын томъёо болон Байесын томъёо. Нөхцөлт математик дундаж**
Тестлэхэд зориулан санамсаргүй объектуудыг үүсгэх**
Оновчлолын бодлогын дөхөлтийн аргууд**
Тоглоомын онолын үндэс
Тоглоом болон тоглоомын үр дүнгийн тухай ойлголт
Энгийн тоглоом болон стратеги
Грандийн функц*
Матриц дээрх тоглоом**
Шугаман програмчлал
Шугаман програмчлалын бодлогын тавил. Шугаман програмчлалын бодлогын геометр тайлбар *
Шугаман програмчлалын бодлогыг бодох үндсэн аргууд:симплекс арга, хүснэгтийн арга**
Шугаман програмчлалын хосмог бодлого**
Урсгал хайх, ажил хуваарилах, богино замын тухай бодлогууд шугаман програмчлалын жишээ бодлогууд болох нь**
Бүхэл тоон програмчлалын тухай ойлголт**
Математик анализын үндэс
Уламжлал ба интеграл. Талбайг тооцоолох. *
Гриний томъёо**
Автомат ба дүрэм
Төгсгөллөг автоматын тухай ойлголт**
Төгсгөллөг автомат ба дүрэм**
Практик дээр бодлого бодоход төгсгөллөг автоматын хэрэглээний үндэс**
Нормал хэлбэрүүд ба тэдгээрийг дүрмийн шинжилгээ хийхэд ашиглах**
Алгоритмын шинжилгээ ба зохиомж
Алгоритм ба түүний шинж чанар
Алгоритмын тухай ойлголт
Алгоритмын зарчим ба шинж чанар
Алгоритмыг формал бус хэл дээр бичих
Өгөгдлийн бүтэц
Энгийн үндсэн бүтцүүд
Олонлог
Дараалал
Жагсаалт
Чиглэлгүй граф
Чиглэлтэй граф
Мод
Пирамид ба хэрчмийн мод* (Фенвикийн мод г.м)
Фенвикийн мод ба түүний олон хэмжээст хэлбэр*
Тэнцвэртэй мод *
Хэш-хүснэгт ба ассоциатив массив *
Угтварын мод**
Залгаврын мод**
Алгоритмын шинжилгээний үндэс
Том О тэмдэглэгээ
Алгоритмын үнэлгээний стандарт ангиуд
Алгоритмын хамгийн муу болон дундаж тохиолдлын асимптотик үнэлгээ
Алгоритмын санах ой болон ажиллах хугацааны хоорондох холбоо*
Рекурсив алгоритмын шинжилгээнд рекуррент харьцааг хэрэглэх*
Бүрэн NP бодлогууд**
Үр ашигтай тооцоологдох чанар**
Универсал алгоритм ба өөртөө хэрэглэгдэх чанар**
Матроид**
Алгоритмын стратегиуд
Бүх боломжийг шалгах алгоритм
"Шуурхай" алгоритм
"Хуваагаад эзэмш" төрлийн алгоритм *
Буцаалттай хайлт*
Эвристик *
Салаа болон хилийн арга**
Хайлшийн арга**
Дөрвөн оросын алгоритм**
Рекурс
Рекурсийн тухай ойлголт
Математикийн рекурсив функц
Энгийн рекурсив процедур
Рекурсийг хэрэгжүүлэх
"Хуваагаад эзэмш" зарчим*
Рекурсээр буцаалттай хайли гүйцэтгэх*
Тооцооллын үндсэн алгоритмууд
Энгийн тоон алгоритмууд
Комбинаторикийн сонгодог алгоритмууд
Дэд олонлогийн алгоритмууд: үүсгэх, дугаараар нь сэргээх, дугааруудыг олох, дараагийн болон өмнөх дэд олонлогийг үүсгэх (элемент нэмэх ба хасах)
Хэсэглэл ба сэлгэмлийн алгоритмууд: үүсгэх, дугаараар нь үүсгэх, дугааруудыг олох, дараагийн болон өмнөхийг үүсгэх.
Шугаман болон хоёртын хайлтын алгоритмууд
Квадрат хугацаатай эрэмбэлэх алгоритмууд (сонгон эрэмбэлэх, оруулж эрэмбэлэх)
Шугаман хугацаанд тоолж эрэмбэлэх.
O(N log N) хугацаатай эрэмбэлэх алгоритмуу (түргэн эрэмбэлэлт, пирамид эрэмбэлэлт,
хольж эрэмбэлэх) *
Цифрээр эрэмбэлэх*
Тэмдэгтүүдийнх нь сэлгэмлүүдийг цагаан толгойн дарааллаар эрэмбэлсний дараах үгийн дугаарыг тооцоолох алгоритм*
Олон оронтой бүхэл тоон дээрх арифметикийн үйлдлүүд*
Тооны онолын алгоритмууд
Тоог анхны тоон үржвэрт задлах
Эратосфены тор
Евклидын алгоритм
Евклидийн өргөтгөсөн алгоритм. Алгоритмыг хуваалт ашиглалгүйгээр хэрэгжүүлэх*
Евклидийн алгоритмыг ашиглан шугаман харьцуулалтуудыг шийдэх*
Эратосфены торыг богино хугацаанд хэрэгжүүлэх (O(n)) *
Гауссын арга ба урвуу матриц**
Модуль ашиглан зэрэгт дэвшүүлэх хурдан алгоритм. RSA нууцлал**
Дискрет логарифмчлал**
Модулиар язгуур авах**
Анхны тоо эсэхийг шалгах үр ашигтай алгоритм**
Тоог анхны тоон үржвэрт хурдан задлах алгоритм. Ро-эвристик**
Берлэкэмпийн алгоритм**
Тэмдэгт мөрийн алгоритмууд
Тэмдэгт мөрөөс дэд тэмдэгт мөр хайх. Энгийн арга
O(N+M) хугацаанд тэмдэгт мөрөөс дэд тэмдэгт мөр хайх алгоритмууд (Кнут-Моррис-Пратын болон Z-алгоритм) *
Үелэх болон цикл тэмдэгт мөр*
Редакцийн зай болон оновчтойгоор тэнцүүлэх*
Бойер-Мурын алгоритм**
Шугаман хугацаанд хэд хэдэн дэд тэмдэгт мөр хайх Ахо-Корасикийн алгоритм**
Залгаврын мод байгуулах алгоритм**
Залгаврыг цифрээр эрэмбэлэх**
Анхны тэмдэгт мөрүүдэд задлах**
Залгаврын автомат байгуулах**
Графын алгоритмууд
Модны богино замын уртыг тооцоолох
Графын түвшний болон гүний нэвтрэлт
Түвшний нэвтрэлтийг хэрэгжүүлэх аргууд(“энгийн” болон дараалал ашигласан)
Графыг холбоост эсэхийг шалгах
Жинтэй графын богино зам хайх алгоритмууд
Графын тополог эрэмбэлэлт, хүчтэй холбоостой компонентыг олох эрэмбийн диаграм байгуулах*
Сөрөг урттай цикл — шалгах нөхцөл, хайх*
Хугацааг синхрончлох бодлого болон тэнцэтгэл бишийн системийн тухай бодлого*
Эйлерийн циклийг олох алгоритм (цагаан толгойн хувьд хамгийн бага) *
Графын транзитив битүүрлийг олох*
Жинтэй, бүрхэлтийн модыг олох алгоритмууд*
Хоёр холбоост компонент, мөчлөлтийн цэг, гүүрийг гүний нэвтрэлтээр олох алгоритмууд*
Хоёр талт графаас хамгийн их хос оноолтыг болон оройн хамгийн бага бүрхэлтийг олох алгоритм*
Сүлжээн дэх хамгийн их урсгалыг хайх**
Хамгийн бага үнэлгээтэй урсгалыг хайх**
Ажил хуваарилалтын тухай бодлогыг шийдэх Унгар арга. Унгар арга, хамгийн бага үнэлгээтэй урсгал болон Дейкстрагийн алгоритмын хоорондын холбоо**
О(N3) хугацаанд хамгийн их урсгалыг олох хурдан алгоритмууд**
Динамик програмчлал
Динамик програмчлалын үндсэн санаа. Рекурсивээр болон циклээр хэрэгжүүлэх.
Хүснэгт дээрх монотон чиглэлтэй хөдөлгөөнтэй бодлого
Үүргэвчний тухай бодлого– динамик програмчлалын аргаар бодох
Үүргэвчний тухай бодлогыг динамик програмчлалын аргаар бодох үеийн оновчлол (илүү параметруудыг хасах) *
Динамик програмчлалын бодлогын шийдийг сэргээх *
Динамк програмчлалын бодлогыг бодох ерөнхий схем *
Нэг хэмжээсээр нь болон дэд олонлогоор динамаик програмчлалыг гүйцэтгэх *
Нэг хэмжээсээр хийгдэх түргэн динамик програмчлал *
Тоглоомын онолын алгоритмууд
Тоглоомын бодлогуудыг бодоход динамик програмчлал, бүх боломжийг шалгах аргуудыг ашиглах. Циклгүй граф дээрх тоглоомууд*
Циклтэй граф дээрх тоглоомыг шийдэх ретроанализын арга ба түүний үр ашигтай хэрэгжүүлэлт**
Булийн илэрхийллийг товчоор тооцоолох алгоритмыг тоглоомын шинжилгээнд хэрэглэх**
Байрлалын үнэлгээ. Альфа-бета огтлол**
Геометрийн алгоритмууд
Цэг, цацраг, шулуун болон хэрчмийн давхцлыг тодорхойлох алгоритмууд
Цэг, шулуун болон хэрчмийг хавтгай дээр дүрслэх
Хавтгай дээрх объектуудын хоорондын зайг олох*
Хавтгай дээрх хэрчмүүдийн огтлолцлыг тодорхойлох алгоритмууд*
Оройн координатуудаараа өгөгдсөн олон өнцөгтийн талбайг тооцоолох алгоритмууд. Бүхэл тоон торны тохиолдол(Пикийн томъёо) *
Гүдгэр бүрхүүл байгуулах алгоритмууд (Грэхем ба Жарвисын алгоритм) *
Хавтгай дээрх тойрог ба түүний бусад объекттой хийх огтлолцол*
Цэг олон өнцөгт дотор оршиж байгаа эсэхийг шалгах*
Шилжих шулууны арга*
Хагас хавтгайн арга**
“Бэлэг боох” арга**
Хавтгай дээр хамгийн ойр хоёр цэгийг олох үр ашигтай алгоритм**
Воронойн диаграмыг үр ашигтайгаар байгуулах алгоритм**
Програмчлалын үндэс
Програмчлалын хэлүүд
Програмчлалын хэлүүдийн ангилал
Процедур хандалтат хэлүүд
Дээд түвшний хэлний синтакс болон семантикийн үндэс
Синтаксийг тодорхойлох формал аргууд:
Бэкуса-Наурын хэлбэр *
Объект хандалтат хэлүүд*
Програмчлалын үндсэн бүтцүүд
Хувьсагч, төрөл, илэрхийлэл ба утга олголт
Оролт/гаралтын үндэс
Нөхцөл шалгах болон давталтын операторууд
Функц ба параметр дамжуулалт
Бүтцийн задлал*
Хувьсагч ба өгөгдлийн төрөл
Өгөгдлийн төрөл - утгуудын олонлог болон тэдэн дээр хийх үйлдлүүд болох нь
Зарлалтын шинж чанарууд (холболт, харагдах муж, блок ба амьдрах хугацаа)
Төрөл шалгах аргууд
Өгөгдлийн бүтцийн төрлүүд
Энгийн төрлүүд
Массив
Бичлэг
Зөв өгөгдлийн бүтэц сонгох стратеги
Өгөгдлийг санах ойд дүрслэх*
Санах ойг статик, автомат болон динамикаар хуваарилах*
Заагч ба заалт*
Холбоост өгөгдлийн бүтцүүд*
Стек, дараалал болон хэш-хүснэгтийг хэрэгжүүлэх *
Граф болон модыг хэрэгжүүлэх аргууд*
Хийсвэрлэлийн механизм.
Процедур, функц и итераторууд хийсвэрлэлийн механизм болох нь
Параметржүүлэх механизмууд (заалт ба утга)
Програмчлалын хэлэн дэх модулиуд
Төрлөн параметр болон параметрчлэгдсэн төрлүүд**
Үндсэн алгоритмуудыг програмчлахад гарах онцлогууд.
Бодлого бодох стратеги
Бодлого бодох ажиллагаанд алгоритмын гүйцэтгэх үүрэг
Алгоритмуудыг хэрэгжүүлэх стратегиуд
Рекурсийг хэрэгжүүлэх
Зүгшрүүлэх стратеги*
Мэдээллийн технологийн үндэс
Тоон логик
Логик схемүүд
Тооллын систем
Компьютерийн арифметик
Өгөгдлийг компьютерийн санах ойд дүрслэх
Бит, байт болон үг
Тоон өгөгдлийн дүрслэл *
Бэхлэгдсэн болон хөвөх таслалтай системүүд *
Тэмдгийн бит болон гүйцээлт байдлаар кодлох *
Тоон бус өгөгдлийг дүрслэх (тэмдэгтийн код, графикийн өгөгдөл) *
Массив болон бичлэгийг дүрслэх*
Компьютерийн ажиллагааны зохион байгуулалт
Фон Нейманы зарчим
Удирдах төхөөрөмж: командыг унших, задлах болон гүйцэтгэх
Командын багц болон төрөл(өгөгдөл боловсруулах, удирдлагын, оролт-гаралтын)
Командын форматууд *
Хаяглалтын горимууд *
Процедурыг дуудах болон түүнээс буцах механизм*
Оролт-гаралт болон тасалдал*
Компьютер санах ойн төхөөрөмж
Үндсэн санах ойн зохион байгуулалт ба түүн дээр хийх үйлдлүүд
Санах ойн шатлал
Өгөгдлийг кодлох, өгөгдлийг шахах болон бүрэн бүтэн байдлыг нь хангах*
Кэш санах ой*
Холболт, харилцан үйлчлэл
Оролт-гаралтын үндэс
Гадаад санах ой, физик зохион байгуулалт ба төхөөрөмж
Сүлжээний технологийн үндэс
Санах ойн шууд хандалт*
Үйлдлийн систем
Үйлдлийн системийн үндэс
Үйлдлийн системийн үүрэг ба асуудлууд
Энгийн үйлдлийн системийн ажиллагаа
Хавтас: агуулга ба бүтэц
Нэрлэх, хайх, хандах, нөөц хуулбар үүсгэх
Үйлдлийн системийн үндсэн функцууд
Хийсвэрлэл, процес ба нөөцүүд
Төхөөрөмжийн зохион байгуулалт
Хамгаалалт, хандалт болон нэвтрэх
Санах ойн удирдлага
Физик санах ой болон санах ойг удирдах техник хангамжийн тухай
Санах ойн хуудаслалт ба сегментчлэлт *
Кэш санах ой *
Програмчлалын технологийн үндэс
Програмчлалын хэрэгсэл ба орчин.
Програмчлалын орчин
Тестлэх хэрэгслүүд *
Програм хангамжийг тестлэх
Тестлэлтийн үндэс, тестийн төлөвлөгөө ба тест үүсгэх*
Тестлэх «хар хайрцгийн» болон «цагаан хайрцгийн» арга *
Нэгжийн, нэгдсэн, системийн тест болон хүлээн авах тест*
Ачааллын тест *
Тооцооллын болон загварчлалын аргууд
Тооцон бодох математикийн үндэс.
Тооцон бодох математикийн үндсэн аргууд
функцийн утга болон язгуурыг тооцоолох *
хавтгай дүрсийн периметр, талбай болон эзэлхүүнийг тооцоолох *
Функцийг алхамтайгаар тооцоолох. Торны арга*
Хөвөх таслалын арифметик**
Алдаа, тогтвортой байдал, нийлэлт**
Загварчлалын үндэс.
Загвар болон загварчлалын тухай ойлголт
Загварын үндсэн төрлүүд
Компьютерийн загварын бүрдэл хэсгүүд ба тэдгээрийг тодорхойлох аргууд: оролтын болон гаралтын хувьсагчид, төлвийн хувьсагчид, шилжилтийн болон гаралтын функцууд, хугацааны шилжилтийн функц
Компьютерийн загварыг байгуулах үндсэн үе шатууд болон онцлогууд
Практикийн бодлогыг бодоход компьютерийн загварчлалыг ашиглах үндсэн үе шатууд
Компьютерийн сүлжээний технологи
Сүлжээ
Сүлжээний карт ба сүлжээний төхөөрөмж
Өгөгдөл дамжуулах орчин
Сүлжээний архитектур
Нууц үг болон бусад хандалтын хяналтын механизмууд
Үйлчилгээний чанарын асуудал: хурд,гэмтлээс сэргэх хугацаа*
Утасгүй сүлжээ.
Утасгүй болон зөөврийн төхөөрөмжийн асуудлууд
Утасгүй болон зөөврийн төхөөрөмж дээр програм суулгах
Утасгүй дотоод сүлжээ ба холбооны шугам

70. II Александр (Alexander II of Russia)



"Хамжлагат ёс өөрөө доороосоо устаж эхлэх цагийг хүлээснээс дээрээс нь устгаж эхэлсэн нь дээр"



Орос улс сүүлийн хэдэн зууны турш хурдацтай хөгжиж буй Барууныг гүйцэн түрүүлэх оролдлогуудыг хийсээр иржээ. Зарим үед хоцорсноос болж улс орных нь оршин тогтноход ч аюул учирч байв. Иймэрхүү байдал XIX зууны дунд үед үүссэн ба Крымийн дайнд ялагдсаныхаа дараа оросын шинэ хаан II Александр шийдвэртэй өөрчлөлтүүдийг хийх шаардлагаай болсон байна.
Түүний хийсэн шинэчлэлүүд дотроос хамгийн чухал нь Оросын нийгэм-эдийн засгийн болон соёлын хөгжлийг хоёр гурван зуунаар чөдөрлөсөн хамжлагат ёсыг халсан явдал байлаа. Тэр үеийн нийгмийн амьдралын ийм гүнзгий асуудлаар оролдох нь амаргүй байсан боловч II Александр энэ хариуцлагатай алхмыг хийхээс айгаагүй юм.
Гэвч түүний хийсэн шинэчлэлүүд хуучинсаг шинж чанартай байсан тул хүн амын үндсэн хэсгийн байдлыг сайжруулаагүйгээр барахгүй шинэ, хүнд асуудлууд урган гарч иржээ. II Александр тэднийг бүрэн шийдэж чадсангүй. Үр дүнд нь хувьсгалын аллагын золиос болсон байна. Үүгээр шинэчлэл зогссон ба Оросын цаашдын хувь заяанд онцгой нөлөө үзүүлжээ.

Sunday, June 22, 2014

69. Жорж Вашингтон (George Washington)



"Хүн өөрийгөө агуу үйл хэрэгт зориулж байгаа тэр хэмжээгээрээ өөрийн ажлаасаа хамгийн их аз жаргалыг авч байдаг"

(1732-1799)



XVII зууны эхээр англикан сүмийн болон английн засгийн газрын мөрдлөгөөс зугтсан хэсэг хүмүүс "Мэйфлауэр" загасчны гурван шурагт далбаат хөлгөөр Шинэ Ертөнцөд иржээ. Олж авсан эх орондоо эдгээр цагаачид эзгүй газрыг боловсруулах ажлыг хийн өөрийн колонио өргөтгөж байлаа.
Эдгээр анхдагчдийн удам болох англи гаралтай боловч америк сэтгэлтэй Жорж Вашингтонд Нэгдсэн Улсын тусгаар тогтнолын төлөө тэмцлийг толгойлж, дэлхий дээрх анхны ардчилсан улсыг үүсгэх хувь заяа ноогджээ. Түүнийг нас барснаас хойш 200 орчим жилийн дараа ч америкийн ард түмэн анхны ерөнхийлөгчөө Америкийн Нэгдсэн Улсыг үүсгэн байгуулагч-эцэг хэмээн хүндэтгэсээр байна.

Friday, June 20, 2014

68. Араб Лоуренс (Lawrence of Arabia)



Арабын Лоуренс (1888-1935)

"Би төв гудамжаар давхих машинууд дундуур сүлжин явж байгаа шаламгай явган зорчигчтой адилхан"



Томас Эдвард Лоуренс өөрийн үеийнхээ хамгийн маргаантай, нууцлаг хүмүүсийн нэг байсан юм. Найзууд нь түүнийг "энэ ертөнц дээрх гайхамшигт зүйлүүдийн дотроос хамгийн гайхамшигтай үзэгдэл" гэж нэрлэдэг байсан бол дургүй хүмүүс нь түүнийг өөрийн зорилгоо зөв тодорхойлж чаддаггүй, туршлагагүй хүн гэж нэрлэж байв. Нэрт тагнуулч өөрийгөө товчхоноор "Маш хэцүү хүн" гэж хэлсэн байдаг. Английн сурвалжит хүний хууль бус хүү, багаасаа эртний ертөнцөд сонирхолтой болсон тэрээр археологкийн багийн бүрэлдэхүүнд орж дэлхийгээр аялан, дэлхийн мянга мянган жилийн түүхтэй танилцахыг хүсдэг байжээ. Лоуренсийн хүсэл биелсэн мэт байсан боловч түүний хувь заяа арай өөрөөр эргэжээ...
Английн залуу археологич, офицер, арабуудын тусгаар тогтнолын төлөө тэмцлийг дэмжигч түүнд Ойрх Дорнодын төлөө хийсэн ажлынхаа төлөө энэ нэрийг өгчээ. Тэр баатар хүн байсан уу? Эсвэл зөвхөн "арабын асуудлыг" өөрийн ашиг сонирхолдоо ашигласан ашиг хонжоо хөөгч байв уу? Алдарт тагнуулчийн тодорхойгүй байдал нь одоог хүртэл түүнийг дэмжигчид болон эсэргүүчэгдийн сонирхлыг татсаар байгаа ба түүний тухай ном бичиж, кино бүтээцгээсээр байна.

Thursday, June 19, 2014

67. Ричард Никсон (Richard Nixon)



"Та эрсдлээс зайлсхийдэг бол алдахгүй байж чадна. Гэхдээ эрсдлээс зайлсхийснээрээ та амжилтанд хүрч чадахгүй"



XX зууны сүүлийн хагас гэхэд Америкийн Нэгдсэн Улс дэлхийн хүчирхэг гүрэн болсон тул энэ улсын тэргүүний үүргийг гүйцэтгэж байгаа хүний шийдвэр нь дэлхий дээрх сая сая хүний хувь заяанд гүнзгий нөлөө үзүүлж байлаа.
Тэдний нэг нь Ричард Никсон байсан юм. Тэрээр 1968 онд АНУ-ын ерөнхийлөгчийн сонгуульд ялсан ба түүнээс хойш Вьетнамд болж байсан үр дүнгүй, хүч барагдуулсан, удаан хугацаанд үргэлжилсэн дайны улмаас эдийн засгийн болон улстөрийн байдал нь хурцадсан энэ агуу том улсыг таван жил хагасын турш удирджээ.
Улстөрийн гал, усыг бүгдийг нь туулж үзсэн туршлагатай хүнийхээ хувьд Никсон өөрийн үйл хэрэгтээ цэвэр практик ач холбогдлыг баримталсан талыг барьдаг байв. Үүнийхээ ачаар тэрээр Хятад болон ЗХУ-тай улстөрийн харилцаагаа сэргээж, "олон улсын төвөгтэй байдлыг намжаадаг архитекторуудын" нэг болсноос гадна Вьетнам дахь дайныг зогсоож чадсан юм.
Гэвч "Уотергэйтийн хэрэг" дээр хэт шулуун бодлого баримталснаас болж хугацаанаасаа өмнө огцорсон байна.

Wednesday, June 18, 2014

66. Шарль де Голль (Charles de Gaulle)



"Франц улс юу гэж бодож байгааг мэдэх хэрэгтэй үед би энэ асуултыг өөрөөсөө асуусан"



Дэлхийн хоёрдугаар дайны үед, эзлэгдэн суларсан Франц улсад хүчтэй, олны сэтгэлийг татсан, хүмүүст фашизмаас ангижрах найдварыг өгч чадах хүн хэрэгтэй байх үед эх орондоо туслахаар Шарль де Голль гарч иржээ. Францчууд одоог хүртэл түүнийг эх орноо аврагч гэж үзэн зүгээр л "генерал де Голль" гэж дууддаг байна. Үр дүнд нь хайрт Франц орныхоо ерөнхийлөгч болсон тэрээр Алжирийн тусгаар тогтнолын хүнд асуудлыг тууштайгаар шийдэрлэхдээ амиараа өдөр бүр дэнчин тавьж байжээ.
Ерөнхийлөгч Шарль де Голлийн эх оронч байдал нь түүний гадаад болон дотоод бодлого, Францын байдлыг бэхжүүлэн, улсдаа өмнөх үеийн сүр хүчийг нь авчирч, францын ард түмэнд өөрийн орноороо бахархах боломжтой болгох хүсэл гэх мэт бүх зүйлээр илэрч байлаа. Ийм зарчимч хүнд мэдээжээр олон дайсан байсан боловч де Голль өөрийн нугаршгүй чин зориг, тэвчээрийнхээ ачаар бэрхшээлийг даван туулж үргэлж урагш ахихыг хичээдэг байжээ.

65. Фeдор Достоевский (Fyodor Dostoyevsky)



"Гол санаагүйгээр хүн ч, үндэстэн ч оршин тогтнох боломжгүй юм. Харин дэлхий дээр ганцхан л гол санаа байдаг нь хүний сэтгэл санаа үхэшгүй мөнх байдаг тухай санаа юм."



Оросын сонгодог утга зохиол тус бүрийг эрдэмтэд дэлгэрэнгүй судлаж, агуулгыг нь үнэлээд нарийн ангилж, номын тавиурууд дээр өрчихсөн билээ. Эдгээр тавиурууд хэд хэдэн давхраас тогтох ба хамгийн дээд талын тавиур дээр "агуу" гэж нэрлэгдэх хүмүүсийн бүтээл байрладаг. Энд хэдхэн бүтээл л байгаа. Федор Михайлович Достоевский бол энэ тавиур дээр байрлах бүрэн эрхтэй зохиолчдын нэг юм.
Гэвч тэрээр энэ тавиур дээр үргэлж байсангүй. Тавин жилийн өмнө зөвлөлтийн утга зохиол судлаачид Достоевскийн бүтээлүүдийн дэлхийн түвшнийх гэдгийг хүлээн зөвшөөрөлгүйгээр түүнийг "хуучирсан", олон зүйлийг "ойлгодоггүй", жинхэнэ мөн чанарыг болон нийгмийн эволюцийн чиглэлийг авч үздэггүй зохиолчдын тоонд оруулсаар байв. Цаг хугацаа бүх зүйлийг зөв байранд нь оруулсан боловч Достоевскийн өвийг "дунд сургуулийн" музей хэлбэртэй болгосноор түүний уран сайхны ертөнцийн мөн чанарыг хүчтэй гажуудуулж, зохиолчийг музейн "үзмэр" болгосоор байна. Гэвч XXI зууны эхэнд ч гэсэн Достоевскийг мартаагүй л байгаа юм. Тэрээр олон зүйлийг зөгнөж, тааж, урьдчилан хэлсэн. Түүний зарим үгс гайхалтайгаар биелсэн ба бусад нь өөрийн цагаа хүлээсээр байна.

Monday, June 16, 2014

64. Саладин (Saladin)



"Намайг ойлгох гэсэн хүн цэцэн хүний ухааныг эзэмшсэн байх ёстой"



XI зууны сүүлээр загалмайтны аян дайны үе эхэлсэн байна. Баруун европын хүлэг баатрууд Ромын Пап ламын уриалгаар Палестин руу ирсээр байв. 1099 онд тэд Иерусалимыг эзлэн, лалын шашинтнуудаас Ариун Булшийг буцаан авчээ.
Гэвч наян найман жилийн дараа лалын шашинтнууд загалмайтнуудыг Ариун газраас хөөж чадсан байна.
Тэднийг Сири, Египтийн эзэн, султан Саладин толгойлж байв. Загалмайтнууд түүнээс айдаг байсан бол лалын шашинтнууд хүндэтгэдэг байжээ. Тэр сайн үйлс бүтээхийг хичээдэг байсан ба өөрийн гайхалтай амьдралын турш энгийн байдлыг эрхэмлэж байжээ. Бидэнд энэ сайн хүний тухай үлгэр домгийг үе дамжин ярьсаар ирсэн юм.

Sunday, June 15, 2014

63. Чарльз Линдберг (Charles Lindbergh)



"Тэнгэр, нислэг, адал явдалд яаж дурладгийг үгээр бичих аргагүй юм. Агаарт амьдрал үхэл хоёр ижил магадлалтай байдаг бол харин хүний боломж хязгааргүй юм"



Ах дүү Райтын аэропланаар хийсэн анхны нислэгээс хорин дөрвөн жилийн дараа, 1927 оны таван сарын нэгэн өглөө хэний ч танил бус нэгэн америк хүн Чарльз Линдберг "Spirit of St.Louis" жижиг онгоцоор Нью-Йоркоос францийн нийслэл орохоор Атлантын далайн хаа нэгтэй сураггүй болж дуусч мэдэх аялалдаа гарсан байна. Энэ гавъяаныхаа дараа Линдбергийн нэр дэлхий дахинд алдаршжээ...

Thursday, June 12, 2014

62. Николай Коперник (Nicolaus Copernicus)



"Эрдэмтэн үнэнийг хайхдаа Бурхнаас хүний оюун ухаанд олгосон боломжийн хүрээнд хайдаг"



Европын дахин сэргэлтийн үед өмнө нь тогтсон байсан төсөөллүүдийг няцаасан шинжлэх ухааны олон нээлтүүд гарсан. Эдгээрийн нэг нь польшийн эрдэмтэн Николай Коперникийн дэвшүүлсэн, эрт дээр үеэс хүмүүсийн бодож байсны эсрэгээр Дэлхий Нарыг тойрч эргэдэг гэдгийг харуулсан гелиоцентрийн онол юм.
Шинэ таамаглалын хувь заяа амаргүй байжээ. Эхний үед түүнийг хангалттай сайнаар хүлээн авцгаасан боловч хэдэн арван жилийн дараа католик сүм түүнийг буруу номлол гэж зарласан байна. Түүнээс хойш гелиоцентрийг дэмжигчдийг буруу номтон гэж үзэн эрүү шүүлт тулгах болжээ.
Николай Коперник өөрөө лам бөгөөд жинхэнэ католик шашинтан байлаа. Өөрийн Ертөнцийн загварыг байгуулснаар Сүмтэй зөрчилд орж байсан тул тэрээр итгэл үнэмшил болон шинжлэх ухааны хооронд "алтан дунджийг" олохыг хичээж байв. Түүний хувьд тэр хоёрын аль аль нь ижилхэн чухал зүйл байлаа.

Wednesday, June 11, 2014

61. Ататюрк (Mustafa Kemal Ataturk)



"Миний нэр хүнд болон алдар нэр бол зөвхөн миний ард түмний алдар нэр ба нэр төр юм."



XIX зууны эцэст нэгэн цагт агуу том, сүр жавхлантай байсан туркийн султануудын улс - Османы эзэнт гүрэн хүнд үеээ туулж байлаа. Тарж бутрах аюул тулгараад байсан энэ улсыг авъяаслаг цэргийн стратегич, улстөрч Мустафа Кемаль Ататюркийн хүч хөдөлмөрийн үр дүнд тусгаар тогтнолоо хадгалан үлдэж чадсан байна. Чөлөөт Турк улсын анхны ерөнхийлөгч болсныхоо дараа Ататюрк туркийн армийг хүчирхэгжүүлж, эрэгтэй эмэгтэй хүмүүсийн эрхийг тэгшитгэн, шинээр латин цагаан толгойг нэвтрүүлэх гэх мэт тэр үедээ онцгойд тооцогдож байсан хэд хэдэн шинэчлэлүүдийг зоригтойгоор хийсэн юм. Шинэчлэгчийн хэлэх дуртай үг нь "Бидэнд ганц л зам бий. Тэр бол Европ" байв. Ататюрк өөрийн орны ёс заншлыг хадгалсан бөгөөд бараг Европын гэмээр иргэний нийгмийг байгуулж чадсан байна. Эдгээр өөрчлөлтүүдийг хийхэд хялбар байсангүй. Кемалийн бодлого нь ийм эрс өөрчлөлтүүдийг улсдаа сайн зүйл авчрахгүй гэж үздэг түүнийг эсэргүүцэгчид болон дайснуудын зүгээс шийдвэртэй эсэргүүцэлтэй тулгарч байсан юм. Гэвч Ататюрк зоригтой, бие даасан хэвээр байсан ба өөрийн сонгож авсан замыг цорын ганц хэмээн үзэж түүн дээрээ баттай зогсчээ.

Friday, May 30, 2014

60. Никита Хрущев (Nikita Khrushchev)



"Та нарт таалагдах эсэхийг мэдэхгүй юм. Гэхдээ түүх манай талд байгаа. Бид та нарыг булшлах болно"



Дэлхийн хоёрдугаар дайн сая сая хүний амийг авч одсон юм. Энэ аймшигтай гамшгийн дараа ялагчид болох ЗХУ болон барууны улсуудын хооронд "хүйтэн дайн" эхэлсэн юм. Энэ байдал хүндэрвэл дэлхийн шинэ дайн болох магадлал өндөр байв. "Их гүрнүүдийн" удирдагчдын буулт хийхэд бэлэн байдлаас олон зүйл хамаарч байлаа.
ЗХУ-ын шинэ удирдагч Никита Хрущев өөрийн үзэл санааны дайснуудтайгаа шууд холбоо тогтоож, бүрэн хэмжээний дайныг зогсоох механизмыг бүрдүүлж чадсан байна. Иосиф Сталины дараа гарч ирсэн тэрээр зоригтой шинэчлэгч болохоо харуулж өөрийн өмнөх удирдагчийнхаа нэр хүндийг шүүмжлэх гэсэн эрсдэлтэй алхмыг ч хийж байжээ. Хрущев орон даяар их хэмжээний өөрчлөлтийг хийж зөвлөлтийн сая сая иргэдэд ирээдүйдээ итгэх итгэлийг төрүүлсэн байна.
Гэвч түүний шинэчлэлүүд хагас дутуу, дэс дараалал муутай болсон ба үүний нэг гол шалтгаан нь түүний коммунизмыг хурдан байгуулах боломжтой гэдэгт чин сэтгэлээсээ итгэдэг байсан явдал нь байжээ.

Tuesday, May 27, 2014

59. Авраам Линкольн (Abraham Lincoln)



"Миний хөдөлмөрт эх орноо хайрлах хайраар дүүрсэн зүрх, сайн үйлс бүтээх гэсэн чин хүсэл хоёр маань шингэсэн юм"



XIX зууны эхний хагаст бие даасан Америк улс нутаг дэвсгэрээ номхон далайн эргийн дагуу өргөтгөх зорилго тавьсан байлаа. Гэвч Америкийн дотоод байдал тайван бус байв. Хойд болон Өмнөд хэсгүүдийн хоорондох зөрчил гүнзгийрсээр байлаа. Үүний шалтгаан нь боолчлолд хандах хандлага байсан юм. Эвлэрэх сүүлчийн найдвар тасраад байх тэр үед Америкт өндөр, сөрдгөр сахалтай, ширүүн бөгөөд заримдаа ядарсан царайтай, өвчлөмтгий боловч хэзээ ч хошин шогийн мэдрэмжээ алддаггүй нэгэн эр гарч ирсэн байна. Тэрээр хэн ч танихгүй ядуу фермерээс улсынхаа хамгийн цуутай улстөрч хүртлэх замыг туулсан юм. Энэ хүн бол Авраам Линкольн байлаа. Тэр иргэний дайныг зогсоож, Америкийг буцаан нэгтгээд, боолчлолыг үүрд хууль бус хэмээн зарлажээ. Өөрийн хийсэн зүйлийн төлөө Линкольн алуурчны суманд өртөж нас барсан байна. Түүнийг зүй ёсоор үндэстнийг аврагч гэж үздэг ба үүний хажуугаар ард түмнээс гарч ирсэн ер бусын, гоц хүн байжээ.

Thursday, May 22, 2014

CF #247. K-мод

к-мод гэж дараах нөхцлүүдийг хангах модыг нэрлэе:
- орой бүр к ширхэг хүүтэй байна
- ирмэг бүр тодорхой жинтэй байна
- орой бүрийн хувьд хүү оройтой нь холбосон ирмэгүүд 1, ..., к гэсэн жингүүдтэй байна
Доорх зурагт 3-модны хэсгийг үзүүлэв:

Дараах асуултын хариуг ол:
"к-модны үндэснээс эхэлсэн, дайрч өнгөрөх ирмэгүүдийн нийт жин нь n-тэй тэнцүү байх, d-гээс багагүй жинтэй ядаж нэг ирмэг агуулах замын тоо хэд байх вэ?"
Энэ тоо нь маш том байж болох тул түүнийг 1000000007 (10^9+7) тоонд хуваасны үлдэгдлийг олоорой.

Оролт
Ганц мөрөнд n, k болон d (1 ≤ n, k ≤ 100; 1 ≤ d ≤ k) тонууд өгөгдөнө.

Гаралт
Бодлогын хариуг 1000000007 (10^9+7) тоонд хуваасны үлдэгдлийг хэвлэнэ.

Wednesday, May 21, 2014

CF #247. В. Шүршүүр

Өглөө бүр дотуур байрны шүршүүрийн үүдэнд таван оюутан зогсч оочерлодог.
Шүршүүр нээгдэхэд эхний оюутан орно. Хэсэг хугацааны дараа оюутан гарахад дараагийнх нь орох гэх мэтээр дараалал дуустал үргэлжилнэ.
Дараалалд зогсох үедээ оюутнууд хоорондоо ярилцдаг. Гэхдээ дарааллын (2i-1)-р оюутан 2i-р оюутантай гэсэн зарчмаар хос хосоороо ярилцана.
Жишээ авч үзье. Оюутнуудыг 1-ээс 5 хүртэл тоогоор дугаарлая. Эхлээд оюутнууд 23154 гэсэн дарааллаар зогсч байсан гэе (2-р оюутан дарааллын эхэнд байгаа). Шүршүүр нээгдэх хүртэл 2, 3-р оюутнууд, 1, 5-р оюутнууд хоорондоо ярилцах ба 4 хэнтэй ч ярилцахгүй. Дараа нь 2 шүршүүрт орно. 2-ыг шүршүүрт байх хугацаанд 3, 1-р оюутнууд, 5, 4-р оюутнууд тус тус хоорондоо ярилцана. Дараа нь 3 шүршүүрт орно. 1, 5 хоёр хоорондоо ярилцах ба 4 хэнтэй ч ярилцахгүй. Дараа нь 1 шүршүүрт орсон хойгуур 5, 4 хоёр ярилцана. Дараа нь 5 орж, эцэст нь 4 орно.
Хэрэв i болон j оюутнууд ярилцаж байгаа бол i оюутан g[ij] хэмжээгээр баярлаж, j оюутан g[ji] хэмжээгээр баярладаг.
Тэгвэл оюутнуудын баяр баясгалангийн нийт хэмжээ хамгийн их байх тийм дарааллыг ол.
Зарим оюутнууд хэд хэдэн удаа хоорондоо ярьж болохыг анхаар. Жишээ нь 1, 5 хоёр шүршүүр онгойхоос өмнө болон 3-г шүршүүрт байх үед гээд хоёр удаа ярилцаж байгаа.

Оролт
Таван мөрөнд таван тоонууд өгөгдөх ба энэ нь g[ij](0 ≤ g[ij] ≤ 10^5) тоонууд юм. Бүх i-гийн хувьд g[ii]=0 байна.
Оюутнуудыг 1-ээс 5 хүртлэх тоонуудаар дугаарласан гэж үз.

Гаралт
Оюутнуудын нийт баяр баяслын хамгийн дээд хэмжээг илэрхийлэх ганц тоог гаргана.

Codeforces #247 A. Хар квадрат

Мэдрүүртэй утсан дээр Хар квадрат гэдэг тоглоом байдаг.
Дэлгэцэн дээр дөрвөн зурвас байна.
Секунд бүрт аль нэг зурвас дээр хар квадрат гарч ирдэг. i-р зурвас дээр гарч ирсэн квадрат дээр дарахад a[i] калори зарцуулагдаг.
Тоглолтын явцыг харуулах s тэмдэгт мөр болон зурвасуудын калорийг харуулсан a[1], a[2], a[3], a[4] тоонууд өгөгдсөн бол тоглолтонд зарцуулагдах нийт калорийг ол.

Оролт
Эхний мөрөнд калориудыг заах a1, a2, a3, a4 (0 ≤ a1, a2, a3, a4 ≤ 10^4) бүхэл тоонууд өгөгдөнө.
Хоёр дахь мөрөнд s (1 ≤ |s| ≤ 10^5) тэмдэгт мөр өгөгдөнө. Түүний тэмдэгт бүр нь тухайн секундэд аль зурвас дээр квадрат гарч ирснийг заана.

Гаралт
Зарцуулагдан нийт калорийг гаргана.

58. Артур Конан Дойл (Arthur Conan Doyle)



"Хэрэв Холмс байдаг бол тэр нь би өөрөө гэдгээ хүлээн зөвшөөрөх ёстой"



XIX зууны хоёр дахь хагасыг Их британийн түүхэнд английн хаан ширээнд хагас зуун жил суусан Виктория хатан хааны нэрээр "викторийн үе" гэж нэрлэдэг байна. Энэ үеийг консерватизм, цэмцгэр байдал, тэвчээртэй байдал, гайхалтай хошин шог гэх мэт жинхэнэ англи зүйлстэй холбон ярьдаг. Артур Конан Дойл нь викторийн үеийн хамгийн жинхэнэ жентльмен байлаа.
Алдарт мөрдөгч Шерлок Холмс болон түүний найз, түүхийг нь бичигч Ватсон эмчийн тухай дуулаагүй хүн байхгүй биз ээ. Анх харахад эдгээр баатрууд огт өөр хүмүүс мэт санагдана: нэг нь маш ухаалаг, энгийн зүйлст дургүй, ердийн бус, уран сайханч хүн байхад нөгөөх нь өөрийн ер бусын найзыгаа биширдэг, халагдсан цэргийн эмч юм. Гэвч тэр хоёр хоёулаа зохиогчийнхоо адил тэр үеийн хүмүүст байсан бүх сайн сайхныг өөртөө шингээсэн жентльменүүд ажээ.

Sunday, May 18, 2014

Sony Bravia зурагтын "дэлгүүрийн горим" буюу "demo mode"-г унтраах

Sony Bravia зурагттай хүмүүс (өөр зурагтанд ч бас байдаг л байх) дуртай зүйлээ үзэж байтал дэлгэцэн дээр нь энд тэндээс реклам маягийн текст гарч ирээд зурагтаа "магтаад" унадаг юм байна. Манай найз ямар сайндаа тэр хавийнхнаараа үзүүлээд бараагүй тул намайг урьжээ.
Цэс рүү нь ороод элдвийн юм on/off болгоод ч болоогүй гэнэ. Гол нь тэр гараад байгаа юмыг юу гэж нэрлэдгийг нь мэдээгүй юм байна. За тэгээд нэлээн урлагтай хүмүүс нь "demo mode" гэдэг нь байх гээд "suspend demo mode" гэдгийг нь сонгосон боловч минутын дараа дахиад л бөөн demo.
Харин би Google ахаас disable demo mode гэсэн чиглэлд хайгаад л "зурагтны ард байгаа home гэсэн товчийг 5 секунд дар" гэсэн заавар олж өгч, түүнийгээ хэрэгжүүлээд л тэр хавийн "од" болчихов. Зурагт нь хятадад үйлдвэрлэсэн байсан болохоор home товчийг нь таамгаар дарсан л даа.

Friday, May 16, 2014

57. Руаль Амундсен (Roald Amundsen)



"Адал явдал гэдэг бол муу бэлтгэлийн үр дүн юм"



Өнөөдөр хүүхдүүд ч туйлын талаар мэддэг болжээ. Цасан цагаан тал, туйлын шөнө гэрэлтэх гайхамшигтай туйлын туяа, далайд хөвөх асар том мөсөн уулс... Далайн муур, цагаан баавгай, оцон шувууд... Дэлхийн энэ төгсгөлд ямар их аюул нуугдана вэ? Нэг л алдаа гаргахад энд ирэхээр зориглосон хүн замаасаа төөрч, хэзээ ч эргэж ирэхгүй болж болно.
Бүх л саад бэрхшээлийг үл харгалзан хүмүүс дэлхийн газрын зураг дээрх "цагаан цэгүүдийг" бөглөх, шинжлэх ухааны ховор материал цуглуулах болон зүгээр л өөртөө болон бусдад байгалиас хүчтэй гэдгээ харуулах гэж Хойд болон Урд туйл руу аялал хийсээр байлаа. Туйл руу хамгийн анх амжилттай аялсан хүн бол Норвегийн Руаль Амундсен байжээ.
Хувь заяаны эрхээр тэр Хойд туйлд очсон хамгийн анхны хүн болж чадаагүй боловч Урд туйлд очсон анхны хүн болж чадсан байна. Гэвч тэрээр эцэст нь өөрийнхөө дуртай Арктикт өөрийн өрсөлдөгч, италийн агаараар аялагч Умберто Нобилег аврах гэж яваад нас барсан байна.

Thursday, May 1, 2014