Алгоритмы и структуры данных. Программирование в Cи

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

ТУЛЬСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ

ИМ. Л.Н. ТОЛСТОГО

Кафедра иностранных языков

РЕФЕРАТ

на право получения допуска к сдаче кандидатского экзамена

по иностранному языку

Тема: “Алгоритмы и структуры данных. Программирование в Cи”

Гордеев Вячеслав Валериевич, аспирант

кафедры информатики и вычислительной техники

ТГПУ им. Л.Н. Толстого

Материалы реферата: Grundlagen Computernetze, Prof. Jürgen Plate, FH München, FB 04, http://www.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.         Эффективность описания и исполнения алгоритма.

После описания свойств необходимо дать достаточно краткое определение понятия алгоритм:

Обрабатываемое предписание называется алгоритмом, если оно имеет следующие свойства: