МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
ТУЛЬСЬКИЙ ДЕРЖАВНИЙ ПЕДАГОГІЧНИЙ УНІВЕРСИТЕТ
ІМ. Л.Н. ТОЛСТОГО
Кафедра іноземних мов
РЕФЕРАТ
на право отримання допуску до складання кандидатського іспиту
по іноземної мови
Тема: "Алгоритми і структури даних. Програмування в Cи "
Гордєєв В'ячеслав Валерійович, аспірант
кафедри інформатики та обчислювальної техніки
ТГПУ ім. Л.Н. Толстого
Матеріали реферату: Grundlagen Computernetze, Prof. JГјrgen Plate, FH MГјnchen, FB 04, .netzmafia.de/skripten/ad/index.html. р. 232.
Дата здачі: Квітень 2004
Тула - 2004
Введення
Дана книга написана професором Мюнхенського університету Юргеном Платі. Вона входить в серію книг, присвячених інформаційним технологіям, які виходять у рамках проекту В«NetzmafiaВ». Книга присвячена одному з головних розділів інформатичних освіти - алгоритмізації та програмування і адресована тим, хто бажає познайомитися й зануритися в світ алгоритмів і розробки програм. Вона складається з двох досить докладних лекцій за темами В«Алгоритми і структури даних В»таВ« Програмування В». У книзі вводиться поняття алгоритму та розглядаються всі необхідні поняття, пов'язані з алгоритмами. Потім обговорюються принципи написання алгоритмів і складання програм на мові програмування Сі.
Сі - це структурний мову програмування високого рівня, створений в 1972 році Керніганом і Рітчі. Він створювалася як мова для розробки операційної системи UNIX. Cи дозволяє працювати з даними практично так само ефективно, як на асемблері (машинному мовою), надаючи при цьому структуровані керуючі конструкції і абстракції високого рівня (структури і масиви). Саме з цим пов'язана його величезна популярність і понині. При цьому компілятор C дуже слабо контролює типи, тому дуже легко написати зовні абсолютно правильну, але логічно помилкову програму.
У вступі Юрген Платі коротко розповідає про структуру книги. Вона складається з двох основних частин - основних понять алгоритмізації та основ програмування. Обидві частини достатньо тісно взаємопов'язані, так як при вивченні основних понять доводиться вдаватися до прикладів рішення задач на конкретних мовах програмування, а при вивченні програмування необхідно постійно пам'ятати основи алгоритмізації.
Автора спонукало написати цю книгу ситуація, яка склалася в світі створення програмного забезпечення. Незважаючи на те, що в останні роки в методиці створення програмного забезпечення зроблений великий прогрес - з'явилася дисципліна програмна інженерія (техніка програмного забезпечення), багато розробників недостатньо кваліфіцированни в цій області. Тому необхідно краще навчати мистецтву програмування. І ця книга в зручній формі викладає основні прийоми програмування, що супроводжується великою кількістю прикладів на мові програмування С.
Кожен програміст повинен виконувати ряд правил при написанні програм:
- Грунтовно подумати перед тим, як натискати на клавіші.
- Мати власний стиль програмування.
- Навчитися звертатися з підводними камінням та з недбалістю мов програмування.
- Виконувати безліч вправ для досягнення результату.
1. Дані та алгоритми
У цій главі автор зібрав основний теоретичний матеріал з алгоритмізації. Тут представлений загальний огляд як програмного, так і апаратного забезпечення. Але основний наголос природно робиться на поняття алгоритму, способи запису алгоритмів, методи і етапи складання програм.
1.1 Основні поняття: повідомлення і інформація
У цьому параграфі професором розглядаються наступні питання:
- Що таке "інформація"?
- Що є "сполученням"?
- Як інформація передається?
- Як інформація представляється?
Поряд з енергією та матерією, інформація - це базове поняття універсального значення. В інформатиці поняття інформації дещо відрізняється від буденного. Інформація - Це знання про що-небудь. Повідомлення служать для відображення інформації.
Обсяг інформаційного повідомлення фіксуються, визначається кількістю рішень в повідомленні і вимірюється в бітах .
Після абстрактної інформації автор переходить до конкретного відображенню інформації, повідомлень. Для цього він наводить кілька визначень:
- Повідомлення - набір символів для інформаційної передачі.
- Символ - елемент символьного запасу, встановленої кінцевої маси різних символів.
- Алфавіт - упорядкований набір символів.
- Слово - послідовність символів, які розглядаються в певному зв'язку в якості єдиної величини.
Фізично повідомлення можуть представлятися через сигнали. При цьому розрізняються аналогові і цифрові сигнали. При аналогових або безперервних сигналах йде безперервне розподіл фізичної величини до об'єму інформації повідомлення, а при цифрових (дискретних) сигналах мається лише кінцеве число можливих станів фізичної величини. Цифрова техніка працює зазвичай з двома значеннями сигналу - 0 і 1.
1.2 Створення програмного забезпечення (програмування)
Цей параграф Платі починає з пояснення поняття алгоритм. Автор говорить про те, що алгоритми повинні розроблятися не для спеціальних цілей, а містити кроки, які потрібно застосовувати при вирішенні певного класу проблем, а не для окремого прикладу.
Програма - це опис шляху, виходячи з певних вхідних даних, до певного результату або метод одержання рішення.
Звідси виділяють наступні властивості алгоритмів:
1. Повнота опису . Повинна бути показана повна послідовність дій. Посилання на невідому інформацію повинні бути відсутніми.
2. Повторюваність алгоритму . Алгоритм можна повторювати скільки завгодно часто і кожне повторення повинне приносити при рівних вхідних даних рівний результат.
3. Коректність алгоритму . На практиці коректність потрібно підтверджувати. Тому використовуються тести, при яких вже відомий для заявлених вхідних даних результат, і порівнюються потім дані з результатами.
4. Ефективність опису і виконання алгоритму .
Після опису властивостей необхідно дати достатньо коротке визначення поняття алгоритм:
обробляти припис називається алгоритмом , якщо воно має такі властивості:
1. Припис описується кінцевими засобами.
2. Воно однозначно встановленим способом для введених даних видає точний результат.
Далі Юрген Платі говорить про те, що програма складається з кінцевого числа кроків і наводить конкретні приклади, що наочно це обгрунтовуючи. Для написання програм необхідно використовувати особливі мови. Мови програмування - це нормовані мови, які служать для опису інструкцій обробки, структур даних, а також введення і виведення даних.
Необхідно перетворювати алгоритм завжди таким чином, щоб виділяти в ньому "Подалгорітми". Теорія розробки програмного забезпечення грунтується на цій ідеї. Складні і комплексні структури та види діяльності реалізуються відомими структурами і більш простими подалгорітмамі. Розробка і складання алгоритмів перетвориться на конструювання з готових алгоритмів.
Найпростіший мову програмування складається з системи команд . Це - вбудовані команди, вони порівнянні з командами мікрокалькулятора, які ви викликаєте, натискаючи клавіші. Цими командами можна виконувати арифметичні операції і зберігати результати дій.
Якщо якимось чином нумерують команди, то отримують машинну мову . Це найпростіший програмістський код. У цьому коді номер команди може використовуватися як її ім'я. Програма на машинній мові є нічим іншим як довгою послідовністю таких слів коду.
Програмувати мовою машин досить важко. ...
