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

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

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