# Проекти ---- ## Ігри ### Сірники На столі лежать сірники. Грають двоє, по черзі роблять ходи. За один хід можна взяти 1, 2 або 3 сірники. Хто візьме останній сірник -- той програв. ### Хрестики-нулики Є квадратне поле 3х3. В клітинки поля гравці по черзі ставлять хрестик або нулик. Хто перший набирає 3 в ряд, 3 в стовпчик чи 3 в діагональ своїх елементів, той виграв. ### Шашки Поле -- шахова дошка. На полі у 3 ряди з кожного боку стоять шашки в шаховому порядку. Шашки ходять на одну клітинку по діагоналі. Якщо попереду ворог, його треба перестрибнути, і ворожа шашка знімається з поля. Якщо можна в кілька стрибків забрати кілька ворогів, то так і треба зробити. Якщо шашка дійшла до останнього рядку, то перетворюється в дамку і може рухатись по всій діагоналі. Гра закінчується, коли всі шашки суперника знищено або утворилась нічия. ### Тетріс Фігури тетраміно з'являються випадково зверху екрану і поступово опускаються донизу. Гравець може розвертати фігури та переміщувати горизонтально, щоб оптимізувати місце приземлення. Якщо фігури заповнюють ряд повністю, він знищується. Якщо неповністю заповнені ряди доходять до верху і новій фігурі немає місця щоб з'явитись, це кінець гри. ### Breakout На полі є кулька, ракетка та прямокутники. Кулька рухається по екрану як більярдна куля. Ракетка керується гравцем і рухається по горизонталі в нижній частині екрану. Ракетка повинна недопустити потрапляння кульки в нижню грань екрану. Якщо кулька потрапляє в прямокутник на полі, то прямокутник забирається з поля, а кулька відбивається як від бортика. Завдання гравця --- збити всі прямокутники кулькою. ### Астеорїди Гравцеь керує зорельотом в космосі (інерційна система без гравітації та тертя) за допомогою маневрових двигунів. Навколо гравця літають астероїди різних розмірів. Завдання гравця --- пострілами знищити всі астероїди. Після вистрілу астероїд розпадається на 2 менших, які в свою чергу після пострілу можуть також розпастись на 2 менших. Найменші астероїди знищуються пострілом повністю. Якщо зорельот вдаряється в астероїд, то знімається життя. Коли всі життя кінчились --- програш, якщо ж всі астероїди знищено --- виграш. ---- ## Біоінженерія ### Алгоритми над РНК/ДНК Аналіз послідовності РНК/ДНК: - частотний розподіл нуклеотидів - порівняння геномів, співставлення геномів - пошук найпопулярніших послідовностей - врахування можливості мутації при пошуку - пошук паліндромічних послідовностей в геномі ### Візуалізація самозбору РНК РНК є одинарном ланцюгом нуклеотидів, тому цілком може самосклеїтись, якщо її код має інверсно-паліндромічний вигляд. Потрібно візуалізувати всі варіанти того як може самосклеїтись ланцюжок РНК. Візуалізацію зробити кількома способами: арками та терміналами. ### Реплікація ДНК Зробити візуалізацію реплікації послідовності ДНК. Показати в якому порядку беруть участь: нуклеотиди, реплікази, полімерази, лігази, та інші ензими. Показати, що зміна молекули відбувається тільки тоді, коли відповіний ензим або нуклеотид "пропливає" поруч з місцем "роботи". Показати, як залежить швидкість реплікації від концентрації нуклеотидів та ензимів. ---- ## Фізика ### Фізика ідеального більярду Кулі на полі без тертя рухаються, вдаряються та відбиваються один від одного. Удари абсолютно пружні. ### Фізика ідеального газу Те саме що і з більярдом, але потрібно додати механізм "тиску": одна з сторін поля може рухатись і або зменшувати поле, або збільшувати його. Рахувати статистичні показники та відбражати динамічно: - площа поля -- це "об'єм" - сума імпульсів ударів молекул в стінки поля за секунду -- це "тиск" - середня енергія молекул -- температура Показати, що при зменшенні об'єму зростає тиск, а температура не змінюється. Також моделювати температуру стінок поля, і при ударах молекул в стінку може відбуватись передача енергії як від стінок до молекул, так і від молекул до стінок. Показати, що з часом температура газу стає рівною температурі стінок. ### Фізика руху автомобіля Автомобіль не має танкового розвороту, тому не може розвертатись на місці. Показати, як буде себе вести автомобіль на поворотах. Додати силу тертя, щоб коли газ відпущено машина гальмувала, а коли натиснуто тормоз -- машина залишала тормозний слід. Зробити можливість дріфту на поворотах, якщо на великій швидкості сила зчеплення шин стає менша за силу тертя. Зробити 2D трек і скролл екрану при їзді машини. ### Фізика гравітації Змоделювати в 2D рух небесних тіл навколо спільного центру гравітації (Сонця). Змоделювати також гравітацію між тілами (задача кількох тіл). ---- ## Математика ### Прості функції Реалізувати: - середнє арифметичне, геометричне, гармонійне - піднесення до цілого степеня, швидке піднесення до степеня - ділення націло, остача від ділення - факторіал - кількість комбінацій (числа з трикутника Паскаля) ### Ірраціональні функції Реалізувати: - квадратний корінь - синус, косинус, тангенс, котангенс - арксинус, арктангенс - exp(x), ln(x) - обчислення $\pi$ та $e$ - піднесення до будь-якого степеня на основі exp та ln ### Робота з матрицями та векторами Реалізувати: - створення одиничних матриць - додавання матриць - множення матриць на число - транспозиція - скалярний добуток матриць - детермінант, довжина вектора - інверсія матриці ### Довга арифметика Реалізувати всі найпростіші операції по роботі з довгою арифметикою. Підтримувати дробові числа. ### Інтегрування Реалізувати чисельне інтегрування: - метод стовпчиків - метод трапецій - метод Рунге-Кутта ---- ## Робототехніка ### Найпростіший клітинний автомат Найпростіший клітинник автомат виглядає так: - одновимірне поле клітинок, якщо клітинка не зайнята, то це 0, якщо зайнята то це 1 - у кожної клітинки поля є "округ" -- одна клітинка до та одна після - клітинка з округом є 3-бітовим числом, всього таких може бути 8 варіантів - для кожного з восьми варіантів робиться правило -- що стається з цією клітинкою в наступній ітерації. Тобто, всього є вісім правил, які перетворють 3 біта в 1 біт. - результат правила і є наступною ітерацією автомату Реалізувати цей автомат, малювати кожну наступну генерацію під попередньою. Дослідити всі можливі варіанти правил (всього їх 256). ### Пошук шляху в лабіринті Потрібно: а) згенерувати лабіринт, з якого є вихід б) написати алгоритм пошуку в ширину, який знайде вихід з цього лабіринту. ### Алгоритм А* Реалізувати пошук шляху між двома точками з врахуванням перешкод. ---- ## Інформатика ### Перетворення в bytearray - число в рядок (в бінарній системі, в шістнадцятковій системі, в будь-якій системі) - ASCII та UNICODE, аналіз кодування - розмір чисел та MessagePack кодування чисел - рядок з довжиною та рядок з 0000 термінатором, операції над рядками ### Код з визначенням та виправленням помилок - симуляція шумових помилок в випадкових бітах - повторення символів як захист від шуму - код Хемінга для захисту від шуму - CRC32 як детектор помилок ### Ентропійне кодування (архіватор) - ентропія інформації - створення словника для повідомлення - створення оптимального словника по Шеннону-Фано ### Простий парсинг Перетворити вираз з математичними знаками та дужками у структуру, яку можна обчислити. ### Інтерпретатор `Brainf*ck` Зробити інтерпретатор Brainf*ck ### Компілятор асемблера Зробити парсинг та компіляцію асемблерного коду під x86_64 платформу. ---- ## Графіка В усіх задачах для малювання дано тільки два примітиви: - намалювати піксель заданого RGB кольору по координаті (x, y) - отримати RGB колір пікселя по координаті (x, y) Всі інші примітиви потрібно реалізувати. ### Примітиви 1 - горизонтальна лінія з точки в точку - вертикальна лінія з точки в точку - прямокутник (квадрат) з ліній, заданий по координатам протилежних кутів - замальований прямокутник - лінія заданої товщини (товщина -- непарна кількість пікселів) ### Примітиви 2 - відрисовка кола та круга - відрисовка лінії по двум точкам (алгоритму Брезенхема) - відрисовка лінії по точці та куту нахилу - антиаліасинг для кола та лінії - відрисовка полігона по списку вершин - заливка області кольором - поворот квадрата (полігону) навколо його центру. Поворот навколо будь-якої точки ### Примітиви 3 - дублювання області екрану (в змінну або на екран). Підтримка альфа-каналу (color key) - віддзеркалення області екрану (горизонтальне або вертикальне) - поворот текстури (області екрану) навколо її центру з підтримкою color key. Поворот навколо будь-якої точки - маштабування текстури (розтягнення горизонтальне або вертикальне) - віддзеркалення текстури відносно прямої ---- ## Психологія ### Клон ANKI Реалізувати систему інтервального згадування по типу ANKI або Memrise. ### Тест Шульте Реалізувати систему для тесту Шульте на уважність. ### Організація точок Тренажер візуального сприйняття: зробити генератор фігур для задач по визначенню фігур по точкам (Organization of Dots). ### Блоки Корсі Зробити тренажер для визначення розміру просторової робочої пам'яті по типу блоків Корсі. ---- ## Картографія ### Карта Відобразити карту та реалізувати інтуїтивне маштабування/переміщення карти. ### Кластери точок Об'єднувати точки на карті у одну точку більшого радіусу при збільшенні маштабу карти.