Вікіпедія:Проєкт:Комп'ютерні науки/Список тем пов'язаних з програмуванням (1996)

Теоретичні основи

1. Алгебра множин, Алгебра відношень, Алгебраїчні системи, Алгебраїчні моделі, алгебри, Породжуючі сукупності: Система твірних, Система визначаючих співвідношень, Конгруенція.
2. Одноосновні та багатоосновні універсальні алгебри. Структури. Решітки. Булеві алгебри. Категорії. Топоси.
3. Формальна мова. Числення висловлювань. Виконувані та загальнозначимі формули. Теорема Геделя про неповноту.
4. Числення предикатів. Нормальна форма. Теорема Ербрана. Метод резолюцій. Лямбда-числення. Поняття редекса. Теорема Черча-Россера.
5. Основні обчислювані оператори. Примітивно-рекурсивні, загально-рекурсивні та частково-рекурсивні функції. Тезис Черча-Тьюрінга-Поста-Кліні. Теорема про універсальну машину та з-т-п-теорема. Теорема Кліні про нерухому точку.
6. Алгоритмічно нерозв'язні проблеми. Проблема зупинки. Теорема Черча про нерозв'язні проблеми розпізнавання виведенності в численні предикатів першого порядку. Теорема Райса про розпізнавання властивостей.
7. Поняття скінченого автомата. Гомоморфізм та ізоморфізм автоматів. Мінімізація автоматів. Скінчені автомати та їх зв'язок з регулярними мовами. Аналіз та синтез скінчених автоматів. Дискретні перетворювачі. Системи алгоритмічних алгебр Е М. Глушкова.
8. Формальні граматики. Ієрархія Чомскі. Синтаксис та семантика формальних мов. Алгоритми визначення регулярності граматики. Контекстно-вільна граматика та їх зв'язок з магазинними автоматами. Нормальна форма Хомського. Нормальна форма Грейбах. Контекстно-вільна мова як розв'язання рівняння. Аналіз та синтез магазинних автоматів.
9. Синтаксичний аналіз «зверху-вниз»; LR-граматики. Рекурсивний спуск. Синтаксичний розбір «знизу-вверх». Граматики передування.
10. Дискретні системи та задачі їх реалізації. Приклади дискретних систем. Граф (математика). Мережа Петрі.
11. Складність алгоритмів та обчислень. NP-складні та NP-повні задачі. Градієнтні методи, евристичний пошук, лінійне програмування та динамічне програмування, розфарбування вершин графа, задача комівояжера.

Архітектура систем обробки інформації

1. Логічна конструкція та принципи роботи обчислювальної машини: пам'ять і її адресація; процесор, система команд і схема, його функціонування; зовнішні пристрої і концепція загальної шини; переривання.
2. Керування зовнішніми пристроями: . клавіатура (перевірка символів в буфері, перепрограмування окремих клавіш); дисплей (керування курсором, виведення символів на екран, зсув екрану та сторінки); дискові накопичувачі (читання таблиці розміщення файлів, робота з файлами); принтер (встановлення специфікацій друку, посилання даних на принтер ); введення/виведення (доступ до послідовного порту, створення драйвера пристрою).
3. Способи організації і класифікація систем паралельної обробки інформації: суміщення у часі різних етапів різних задач, одночасне розв'язування різних задач чи частин однієї задачі; конвеєрна обробка інформації; системи з одиночним потоком команд і одиночним потоком даних; системи з одиночним потоком команд і множинним пото ком даних; системи з множинним потоком команд і одиночним потоком даних; системи з множинним потоком команд і множинним потоком даних.
4. Поняття обчислювального комплексу. Багатомашинні комплекси: слабозв'язані, прямозв'язані, сателітні. Багатопроцесорні комплекси: з загальною шиною, з перехресною комутацією, багатовходовим ОЗП Особливості організації обчислювальних процесів в комплексах. Порівняння багатомашинних і багатопроцесорних комплексів.
5. Поняття обчислювальної системи. Системи з конвеєрною обробкою інформації; матричні системи; асоціативні системи і осередки; функціонально розподільні системи; системи з перебудовуванною структурою. SIMD- і MIMD-архітектура.
6. Поняття обчислювальної мережі і її структура. Характеристики мережі: операційні можливості, час доставки повідомлень, продуктивність і вартість обробки даних. Процеси. Рівні керування. Інтерфейси. Структура повідомлень. Протоколи. Способи і засоби комутації і передачі даних. Адресація, маршрутизація пакетів і керування потоками даних. Транспортна служба. Протоколи високого рівня. Адміністративне керування. Локальні обчислювальні мережі.

Операційні системи

1. Операційна система (ОС): призначення та основні концепції ОС.
2. Файлова система; драйвери зовнішніх пристроїв; процесор командної мови. Командні файли. Конфігурування системи.
3. Структура та функції MS-DOS: базова система введення-виведення (BIOS); блок початкового завантаження (Master Boot Record, Boot Loader), модуль розширення базової системи введення-виведення, модуль обробки переривань, командний процесор; утиліти MS-DOS.
4. Організація взаємодії програм через переривання. Динамічне завантаження. Завантаження та запуск програмових оверлеїв. Резиденти і програми.
5. Апаратні, логічні і програмові переривання. Написання власного переривання; доповнення до існуючого переривання.
6. Організація мультипрограмних процесорів. Утворення процесів. Програмові засоби комплектування ЕОМ та мультипроцесорних систем.
7. Структура та функції ОС UNIX.
8. Середовище Windows. Базові класи вікон. Керуючі елементи, кнопки, фокус введення. Об'єкти. Організація сценаріїв.

Мови та системи програмування

1. Процедурні та проблемно-орієнтовані мови: особливості організації і напрямки розвитку. Основні концепції і можливості мов Фортран, Паскаль, Модула-2, Сі, C++, Ада, Лісп, Пролог.
2. Транслятори (асемблери і компілятори) та інтерпретатори. Етапи трансляції: лексичний, синтаксичний, семантичний аналіз, оптимізація, генерація об'єктного коду, збирання.
3. Керування пам'яттю в програмі, що створюється транслятором: статична, автоматична, базована та динамічна пам'ять. Методи гешування.
4. Організація передачі параметрів між програмовими модулями. Виклик за значенням, за найменуванням, за результатом. Проблеми комплексування різномовних модулів.
5. Мови, що орієнтовані на паралельну та розподілену обробку. Особливості реалізації.
6. Генератори систем програмування. Макрогенератори та розширювані системи програмування, препроцесори.
7. Метасистеми програмування: багатомовні системи, параметричні системи та метатранслятори.
8. Діалогові системи програмування: призначення та архітектура. Форми організації діалогу. Способи мовного спілкування: відеоформи, меню, електронні таблиці, використання функціональних клавіш і т. п.. Діалог на природній мові.

Технологія програмування та проєктування програмного забезпечення (ПЗ)

1. Основні стадії та етапи проєктування програм та документування. Технічне завдання. Ескізний, технічний, робочий проєкти. Впровадження та супроводження, моделі життєвого циклу ПЗ.
2. Специфікація програм. Понятійні засоби специфікації. Денотаційна, операційна та аксіоматична семантики. Класифікація мов специфікацій.
3. Якість програмового забезпечення. Методи налагодження та тестування програм, верифікація програм.
4. Організація роботи колективів програмістів. Бригада головного програміста. Планування виробництва ПЗ. Проєктування послідовних та паралельних програм.
5. Поняття рекурсії. Рекурсивні означення та рекурсивні програми. Властивості рекурсивних алгоритмів. Функціональні і рекурсивні структури даних.
6. Структурне програмування. Теорема про структурування програм. Багатоосновні алгебри структур даних. Теоретико-множинні структури даних.
7. Схеми програм над пам'яттю. Алгебра алгоритмів. Повторне використання ПЗ. Модифікованість алгоритмів та програм.
8. Об'єктно-орієнтоване програмування. Мови: Smalltalk, C++.
9. Функціональне програмування. Концепції та приклади. Мова Лісп.
10. Логічне програмування. Приклади систем програмування "за правилами". Мова Пролог.

Системи управління базами даних

1. Загальне уявлення про систему баз даних: схеми і екземпляри даних, фізична база даних, модель даних, схема даних, підсхема. Проєктування концептуальної схеми. Мова означення даних. Адміністратор бази даних. Мова маніпулювання даними. Незалежність даних; цілісність даних та види функціональних залежностей.
2. Фізична організація даних: модель організації зовнішньої пам'яті, гешовані та індексовані файли, В-дерева, файли зі щільним індексом, файли із записами змінної довжини; пошук за частковою відповідністю.
3. Реляційна, мережева та ієрархічна моделі даних і їх реалізація; порівняння моделей.
4. Мови маніпулювання даними для реляційної моделі: реляційна алгебра та реляційне числення; алгебраїчні мови та мови числення.
5. Теорія проєктування реляційних баз даних: функціональні залежності, декомпозиція схем відношень, нормальні форми схем відношень; багатозначні залежності.
6. Тезаурус в автоматизованих системах управління і обробки інформації.
7. Системи словників-довідників даних: основні поняття, використання, питання проєктування, стратегії реалізації.
8. Розподілені бази даних: централізовані і децентралізовані СУБД; проблеми розподілення баз даних; виконання запитів; одночасна обробка та оновлення.
9. Машина баз даних як апаратно-програмовий мультипроцесорний комплекс, призначений для виконання функцій СУБД.

Системи, що грунтуються на знаннях

1. Концепція знання. Відмінність понять «Знання» та «Дані». Бази знань. Системи програмування баз знань.
2. Моделі подання знань: продукційні, логічні, мережеві та фреймові (en:Frame language).
3. Методи інженерії знань: формалізація знань, поповнення знань та виключення надлишковості, узагальнення та класифікація, дедуктивне виведення, теорема Байєса, індуктивне виведення, обробка неповної інформації, нечітке виведення. Планування розв'язування задач, аналогія та дедукція.
4. Мови та системи подання знань: концепці ї і приклади.
5. Поняття Експертна система та її структура: база даних; база знань; розв'язувач (машина виведення); компонент Придбання знань (en:Knowledge discovery); пояснювальний та діалоговий компонент. Формалізовані і неформалізовані знання.
6. Пакети прикладних програм (ППП: моделі, функці ї, режими роботи, архітектура. Системне і функціональне наповнення ППП і міжмодульний інтерфейс. Модульний аналіз предметної області.
7. Системи підтримки прийняття рішень та особливості їх реалізації.
8. Етапи розробки систем, що грунтуються на знаннях: ідентифікація, концептуалізація, формалізація, виконання, тестування, дослідна експлуатація, модифікація. Інструментарій і методологія розробки систем, що грунтуються на знаннях, класифікація інструментальних засобів.
9. Принципи розроблення апаратних засобів для підтримки систем, що грунтуються на знаннях. Лісп-процесори і Пролог-машина.