Основни понятия за структури от данни
Структурите от данни и алгоритмите са градивните елементи на програмите. Вградените структури от данни са представени от онези регистри и думи от паметта, където се съхраняват двоични стойности. Алгоритмите, вградени в дизайна на оборудването, са строги правила, въплътени в електронни логически схеми, според които данните, въведени в паметта, се интерпретират като команди, които трябва да бъдат изпълнени.
Програмирането е не само автоматизация на умствената дейност, но и обект на научно изследване.
Процесът на създаване на програма за решаване на всеки практически проблем се състои от няколко етапа:
Поставяне на задачата (създаване на технически спецификации за оригиналната задача);
Формализация (математическа постановка на проблема);
Избор (или разработване) на метод за решение;
Разработване на алгоритми (алгоритмизация);
Съставяне на програма (програмиране);
Програма за тестване и отстраняване на грешки;
Изчисляване и обработка на резултатите и документиране на програмата;
Процесът на програмиране може да бъде схематично представен по следния начин:
Абстрактни типове данни
програма за псевдо език
Програма на Паскал
На първия етап се създава модел на оригиналния проблем, за който се включват съответните математически модели (като например теория на графите).
На следващия етап алгоритъмът е написан на псевдоезик - композиции (смеси) от езикови конструкции на Pascal и по-малко формални и обобщени оператори на прост човешки език.
Продължението на този етап е замяната на неформалните оператори.
Третият етап от процеса на програмиране осигурява имплементирането на всеки абстрактен тип данни и създаването на процедури за изпълнениеразлични оператори за данни от този тип. Тази стъпка също заменя всички неофициални оператори на псевдоезици с код на Pascal. Резултатът от стъпката трябва да бъде изпълнима програма.
Информацията и нейното представяне в паметта
Решаването на всяка задача с помощта на компютър включва запис на информация в паметта, извличане на информация от паметта и манипулиране на информация.
В информационно-теоретичен смисъл информацията се разглежда като мярка за разрешаване на неопределеността. Да приемем, че има N възможни състояния на някаква система, в които всяко състояние има вероятност за възникване P и всички вероятности са независими. Тогава несигурността на тази система се определя като:
За измерване на неопределеността на системата се избира специална единица, наречена бит. Битът е мярка за несигурността (или информацията), свързана с наличието на само две възможни състояния, като вярно-невярно или да-не. Един бит се използва за измерване както на несигурността, така и на информацията; тъй като количеството получена информация е равно на количеството несигурност, елиминирана в резултат на получаване на информация.
Хранилище за данни
Има три основни типа устройства за съхранение: супербърза, оперативна и външна памет. Обикновено паметта на scratchpad е изградена върху регистри. Регистрите се използват за временно съхранение и трансформиране на информация.
Някои от най-важните регистри се съдържат в централния процесор на компютъра. Централният процесор съдържа регистри, които съдържат аргументите (т.е. операндите) на аритметичните операции. Събирането, изваждането, умножението и делението на информацията, въведена в регистрите, се извършва с помощта на много сложни логически схеми. Освен това за целтапроверката на необходимостта от промяна на нормалната последователност от контролни трансфери в регистрите може да се анализира по отделни битове. В допълнение към съхраняването на операнди и резултатите от аритметичните операции, регистрите се използват и за временно съхраняване на програмни инструкции и контролна информация за номера на следващата инструкция, която трябва да бъде изпълнена.
Външната памет служи предимно за дългосрочно съхранение на данни. Характерно за данните във външната памет е, че те могат да се съхраняват там дори след като програмата, която ги е създала, е приключила и могат впоследствие да бъдат използвани повторно от същата програма, когато тя се рестартира или от други програми. Външната памет се използва и за съхраняване на самите програми, когато не работят. Тъй като цената на външната памет е много по-малка от оперативната памет и обемът е много по-голям, друга цел на външната памет е временно да съхранява онези кодове и данни от изпълняваната програма, които не се използват на този етап от нейното изпълнение. Активните кодове на изпълнимата програма и данните, обработвани от нея на този етап, трябва задължително да бъдат поставени в RAM, тъй като директният обмен между външна памет и операционни единици (регистри) е невъзможен.
Значителни количества информация, които трябва да бъдат обработени, са абстракция на някакъв фрагмент от реалния свят. Информацията, необходима за решаване на определен проблем, се състои от определен набор от данни, свързани с проблема. При решаването на всеки проблем е необходимо да изберете нивото на абстракция, т.е. дефинирайте набор от данни, представящи реалната ситуация. Когато избирате, трябва да се ръководите от проблема, който трябва да бъде решен. Следващата стъпка е да изберете как ще бъде представена тази информация.
Типове данни, абстрактни типоведанни и структури от данни
Въпреки че тези термини звучат сходно, те имат различни значения.
В езиците за програмиранетип даннина променлива обозначава набора от стойности, които променливата може да приеме. Типовете данни включват естествени числа, цели числа, реални числа (като приблизителни десетични числа), знаци, низове и т.н.
В някои езици за програмиране типът на всяка константа или променлива се определя от компилатора чрез отбелязване на стойността, която присвоява; наличието на десетична точка, например, може да служи като знак за реално число. Други езици изискват от програмиста изрично да посочи типа на всяка променлива и това има едно важно предимство. Въпреки че стойността на една променлива може да се променя много пъти по време на изпълнение на програмата, нейният тип никога не трябва да се променя; това означава, че компилаторът може да провери операциите, извършени върху тази променлива, и да се увери, че всички те отговарят на описанието на типа на променливата. Такава проверка може да се извърши чрез анализиране на целия текст на програмата, като в този случай тя ще обхване всички възможни действия, определени от тази програма.
В зависимост от предназначението на езика за програмиране, защитата на типа, предоставена по време на компилиране, може да бъде повече или по-малко строга. Например езикът Pascal, който първоначално е бил предимно инструмент за илюстриране на структури от данни и алгоритми, запазва много стриктна защита на типа спрямо първоначалната си цел. Компилаторът Pascal в повечето случаи разглежда смесването на данни от различни типове в един израз или прилагането на необичайни за него операции към тип данни като фатална грешка. За разлика от това, езикът C, предназначен предимно за системно програмиране, е език с много слаба сигурност.видове. C компилаторите издават предупреждения само в такива случаи. Липсата на силна защита на типа дава на системния програмист, който разработва програма на езика C, допълнителни възможности, но такъв програмист е отговорен за правилността на своите действия.
Абстрактен тип данние математически модел плюс различни оператори, дефинирани в този модел. Възможно е да се проектира алгоритъм от гледна точка на абстрактни типове данни, но за да се приложи алгоритъмът на конкретен език за програмиране, трябва да се намери начин да се представи ADT по отношение на типовете данни и операторите, поддържани от този език за програмиране.
За представяне на ADT се използватструктури от данни,които са набор от променливи, евентуално от различни типове данни, комбинирани по определен начин.
Структурите от данни, използвани в алгоритмите, могат да бъдат изключително сложни. В резултат на това изборът на правилно представяне на данни често е ключът към успешното програмиране и може да има повече общо с производителността на програмата, отколкото детайлите на използвания алгоритъм.
Основният градивен елемент на структура от данни еклетка, която е проектирана да съдържа стойност от конкретен базов или съставен тип данни. Структурите от данни се създават чрез даване на имена на колекции (агрегати) от клетки като представители (т.е. указатели) на други клетки.