- •Основні положення теорії алгоритмів та її застосування
- •Введення до теорії алгоритмів
- •Загальні риси алгоритмів
- •Машина Поста
- •Машина т’юринга
- •Основи лямбда-числення та функціонального програмування
- •Теза Черча-т’юринга про алгоритмічну розв’язність задачі
- •Проблема розв’язності (зависання)
- •Алгоритмічно нерозв’язні задачі
- •Проблема відсутності загального методу вирішення задачі
- •Проблема інформаційної невизначеності задачі
- •Проблема логічної нерозв’язності задачі
- •Побудова машини т’юринга для обчислення деяких простих функцій
- •Введення до оцінки складності алгоритмів
- •Визначення порядку складності алгоритму
- •Оптимізація алгоритмів
- •Структури даних в алгоритмічній мові програмування
- •Визначення алгоритмічної мови програмування
- •Базові елементи сучасної мови програмування: типи даних; екземпляри даних; вирази; оператори; функції; класи.
- •Поняття типу даних
- •Прості типи: числові; символьні; логічні.
- •Тип даних рядок
- •Структуровані типи даних: масиви, записи, множини
- •Типи даних за значенням і за посиланням
- •Сумісність типів та перетворення між типами даних
- •Екземпляри даних: змінні, константи
- •Видимість даних
- •Управління ходом виконання та структурування програм в алгоритмічній мові програмування
- •Вирази, операнди та операції
- •Основні операції: арифметичні; логічні; бульові; з використанням рядків
- •Поняття оператора
- •Прості оператори: присвоювання; виклику функції
- •Оператори управління ходом виконання: розгалуження; вибору; цикли; переходу
- •Структурування програм: функції та класи
- •Параметри функцій: вхідні, результуючі.
- •Рекурсивні функції
- •Файли: текстові, бінарні
- •Алгоритми чисельних методів, апроксимації функцій, інтегрування та вирішення рівнянь з одним невідомим
- •Чисельні методи
- •Особливості вирішення задач чисельними методами, точність та коректність рішень
- •Апроксимації функцій: лінійна інтерполяція; інтерполяційний многочлен Ньютона.
- •Чисельне інтегрування: метод трапецій; метод Сімпсона; метод Сімпсона з оцінкою погрішності.
- •Вирішення рівнянь з одним невідомим: метод простих ітерацій; метод Ньютона; метод парабол.
- •Алгоритми вирішення системи лінійних рівнянь, пошуку екстремуму функції
- •Вирішення системи лінійних рівнянь методом Гауса
- •Пошук екстремуму функцій одної змінної: метод золотого перетину; метод парабол.
- •Пошук екстремуму функцій багатьох змінних: метод координатного спуску; метод найскорішого спуску.
- •Алгоритми обробки масивів
- •Визначення масивів
- •Операції над масивами
- •Упорядкування масивів: сортування вибором; сортування вставкою; бульбашкове сортування; сортування методом Шелла; метод швидкого сортування.
- •Вибір методів сортування
- •Пошук в упорядкованих масивах методом половинного поділу, інтерполяційним методом
- •Застосування індексів для пошуку у невпорядкованих даних
- •Алгоритми обробки даних на основі списків та дерев
- •Визначення списку
- •Види списків: незалежні списки, однозв’язані списки; двозв’язані списки; кільцеві списки; упорядковані списки
- •Основні операції над списками: включення елементу до списку; видалення елементу; перехід між елементами; ітератор для списку
- •Упорядкування та пошук в списках
- •Похідні структури даних: черга, стек, дек
- •Визначення дерева
- •Впорядковані дерева
- •Бінарні дерева
- •Основні операції з бінарними деревами: включення елементу; видалення елементу; обхід дерева
- •Балансування дерева
- •Алгоритми обробки текстових даних на основі регулярних виразів
- •Введення до теорії кінцевих автоматів
- •Графічне представлення кінцевих автоматів
- •Використання кінцевого автомату: синтаксичний аналіз.
- •Реалізація синтаксичного аналізу файлу з розділяючими комами
- •Детерміновані та недетерміновані кінцеві автомати
- •Регулярні вирази
- •Форма Бекуса-Наура для запису регулярних виразів
- •Синтаксичний аналіз регулярних виразів
- •Компіляція регулярних виразів
- •Інструменти для спрощення роботи з регулярними виразами
- •Зіставлення рядків з регулярними виразами.
- •Алгоритми систем числення
- •Введення до систем числення
- •Двійкова система числення
- •Шістнадцяткова система числення
- •Системи числення з нетрадиційними основами
- •Перетворення між різними системами числення
- •Арифметика чисел з плаваючою комою
- •Точність операцій з плаваючою комою
- •Арифметика великих чисел
- •Алгоритми криптографії та хешування
- •Значення випадкових чисел у програмуванні
- •Алгоритми генерації рівномірно розподілених псевдовипадкових чисел
- •Перевірка якості випадкових чисел
- •Кодування з виправленням помилок
- •Стиснення даних
- •Стиснення даних зі словником
- •Алгоритм стиснення даних Лемпела-Зіва
- •Введення до криптографії
- •Елементи теорії порівнянь
- •Алгоритми цифрового підпису
- •Введення до хешування
- •Функції хешування
- •Проста функція хешування рядків
- •Шифрування за допомогою випадкових чисел
- •Створення таємного ключа по Діффі-Хеллману
- •Система rsa
- •Функції хешування з використанням рандомізації
- •Вирішення конфліктів за допомогою лінійного зондування
- •Псевдовипадкове зондування
- •Подвійне хешування
Тип даних рядок
Тип даних рядок (string) призначений для зберігання рядків тексту. Також як і символьний тип, для кодування символів використовується Unicode.
Рядкові літерали записуються у подвійних лапках. Символ косої зворотної риски («\») використовується для позначення спеціальних символів, тому, якщо він присутній у рядку, його слід подвоювати, наприклад:
string filePath = "C:\\Some Path\\Some File.txt";
Для спрощення запису можна використовувати символ «@» перед початком рядку, у такому разі усі символи (не лише зворотна коса риска, а й кінець рядку) будуть оброблятися однаково, серед них не будуть виділятися службові, наприклад:
string filePath = @"C:\Some Path\Some File.txt";
Структуровані типи даних: масиви, записи, множини
Масиви
Масив – регулярна структура даних, яка зберігає компоненти одного типу. Крім того, масив є структурою із довільним доступом – усі його компоненти можуть обиратися довільно і є однаково доступними.
Для доступу до елементів масивів використовуються індекси, які записуються у квадратних дужках після ідентифікатора масиву.
Мова C# підтримує наступні типи масивів:
одновимірні;
багатовимірні прямокутні;
багатовимірні ортогональні (непрямокутні).
Декларація і доступ до елементів масиву у C#
Декларація масиву у C# відбувається наступним чином:
int[] Integers;
Декларація і створення одномірного масиву розміром 100 значень:
int[] Integers = new int[100];
Для доступу до елемента масиву слід вказати його ідентифікатор і індекс:
Integers[50] = 12345;
Індексація елементів масиву починається з 0, тому перший елемент має індекс 0, а останній – розмірність масиву мінус 1.
Ініціалізація масиву під час декларації
Під час декларації масиву можна ініціалізувати його, наприклад:
string[] DaysOfTheWeek = { "Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday" };
Декларація багатовимірних масивів
Декларація багатовимірних прямокутних масивів здійснюється наступним чином (наприклад, декларація та ініціалізація двовимірного масиву рядків):
string[,] StudentNameGrade = { {"Петренко", "Відмінно"},
{"Луценко", "Задовільно"},
{"Шевченко", "Добре"}
};
Декларація ортогональних масивів здійснюється наступним чином:
int[][][] Integers;
Операції над масивами
Для отримання довжини одновимірного масиву використовується конструкція:
int ArrayLength = Integers.Length;
Для багатовимірного масиву використовується метод GetLength(), у параметрах якого слід вказати номер виміру (починаючи з 0):
int multiArrLength = StudentNameGrade.GetLength(0);
Для сортування масиву використовується наступна конструкція (викликається статичний метод Sort() стандартного класу Array, якому передається масив, що необхідно відсортувати, у якості параметру) :
Array.Sort(Integers);
Для зміни порядку елементів масиву на зворотній використовується наступна конструкція:
Array.Reverse(Integers);
Обробка всього масиву
Якщо необхідно звернутися до всіх елементів масиву, то зробити це можна в циклі, або використати ітератор.
Виведення всіх елементів масиву на екран, використовуючи цикл:
for (int i = 0; i < Integers.Length; i++)
{
Console.WriteLine(Integers[i].ToString());
}
Виведення всіх елементів масиву на екран, використовуючи ітератор:
foreach (int item in Integers)
{
Console.WriteLine(item.ToString());
}
Записи
Записи або структури дозволяють логічно поєднати у одному складному типу даних декілька різних простих типів даних.
Приклад декларації структури:
struct Point
{
public int X;
public int Y;
}
Доступ до складових структури здійснюється через крапку:
Point thePoint = new Point();
thePoint.X = 100;
thePoint.Y = 200;
Операції над записами
Структури можуть містити конструктори – підпрограми, які виконуються при створенні структури і призначені для ініціалізації даних.
Приклад структури з конструктором:
struct Point
{
public int X;
public int Y;
public Point(int a, int b)
{
X = a;
Y = b;
}
}
Приклад створення структури з викликом конструктора:
Point thePoint = new Point(100, 200);
Структури можна створювати також не використовуючи оператор new:
Point thePoint;
Множини
Деякі мови програмування (Pascal) підтримують тип даних “множина”, який реалізує математичні множини.
Тип даних множина дозволяє зберігати обмежену кількість значень певного типу без визначеного порядку. Повторення значень, як правило, не допускається.
Мови програмування, які підтримують множини, реалізують також і стандартні математичні операції над ними.
C-подібні мови програмування, і C# в тому числі, не підтримують цей тип даних на рівні стандартних типів самої мови. Однак, за необхідності, його можна реалізувати за допомогою класів. Серед стандартних класів .NET Framework є клас HashSet, який відповідає множині, у Java є клас java.util.Set.
Обмежені типи даних
У певних ситуаціях необхідно, щоб тип даних був підмножиною якогось із стандартних типів даних. Наприклад, допустимою температурою, яка зчитується з певного датчика може бути лише значення температури у певних межах, якщо відбувається спроба присвоїти значення, що виходить за вказані межі, то це свідчить про помилку.
Деякі мови програмування, наприклад, Pascal підтримують обмежені типи даних, які можна створити на основі стандартних типів.
Мова C# прямо не підтримує обмежені типи даних, однак їх можна реалізувати за допомогою класів.
