Писани са от мен, Иван Димитров Георгиев (вече завършил) студент по информатика, електронната ми поща е ivandg@yahoo.com. Четени са през зимния семестър на учебната 2001/2002 година. Лектор беше доц. Стоян Бъчваров, семинарните упражнения водеше главен асистент Савка Костадинова. Включени са (повърхностно) само няколко семинарни занятия. Използвал съм единствено моите записки (и на мои колеги) от лекции и никаква допълнителна литература. Предупреждавам ви, че лекциите са писани от първокурсник и в тях има много неточности, така че може да пишете на мейла ми, ако не може да се обясните нещо. 3 октомври 1. Основни информационни дейности. Средства за автоматизация на смятането.
Основни информационни дейности – събиране, съхранение, преработване и разпространение на информация
събиране
съхранение
преработка
разпространиени
            
Средства за автоматизация на смятането – възникнали в следствие на противоречие в горната схема след появата на писмеността (във връзката между съхранение и преработка)
-
Инструмент + метод – пример: химикал и лист + начин на писане
-
Сметачни машини – извършват автоматично отделни операции – Блез Паскал (около 1640 г.)
-
Автоматични сметачни машини – Чарлз Бабедж (около 1840 г.); съставени от няколко блока: управляващо устройство, аритметично устройство, памет (където се съхраняват междинните резултати), вход и изход (външен носител); моделът се усъвършенства от Джон фон Нойман, който предлага и самата програма да се намира в паметта – автоматизация на целия изчислителен процес
Два вида сметачни машини (и автоматични) – аналогови и цифрови; разликата е в начина на представяне на числата; в аналоговите числата се представят чрез физически величини (напрежение, дължина, налягане), а в цифровите числата се представят в цифров вид; цифрата се изразява чрез състоянието на физически елемент, който може да се намира в краен брой различни състояния; цифри – 0 или 1 (двоични числа) има/няма напрежение; южен/северен полюс на магнит; правени са опити с три състояния
Компютър – цифрова автоматична сметачна машина; съвременните компютри са Нойманови компютри; развитието на компютрите засяга техническата реализация, а не принципите;
Нулево поколение – електромеханични компютри; основен елемент – реле;
Първо поколение – електронна лампа; предложена от Джон Атанасов;
Второ поколение – основен елемент – транзистори;
Трето поколение – основен елемент – интегрални схеми;
Четвърто поколение – основен елемент – големи интегрални схеми; по-компактни по размери (минитюаризация)
Пето поколение – търсят се други принципи, различни от ноймановите; свръхголеми интегрални схеми
2. Алгоритми. Определение и примери. Свойства. Начини на изразяване – словесно описание, блок-схема, алгоритмичен език.
Компютър (допълнение) – техническо средство за автоматично изпълнение на алгоритми
Алгоритъм – списък от краен брой правила за извършване на дадени действия в определен ред, чрез който се решават задачи от даден тип
Пример: Дадени са числата а1,а2,...,аk,…,an; да се намерят най-малкото () и най-голямото ()
Словесно описание:
-
Въвеждане на n и а1,а2,...,an; премини към 2
-
= a1; премини към 3
-
= a1; премини към 4
-
k = 2; премини към 5
-
Ако ak < премини към 6, иначе премини към 7
-
= ak; премини към 7
-
Ако ak > премини към 8, иначе премини към 9
-
= ak; премини към 9
-
k = k + 1; премини към 10
-
Ако k<=n премини към 5, иначе премини към 11
-
Изведи и ; премини към 12
-
Прекрати изпълнението на алгоритъма
Безусловни и условни действия – от условните може да се премине към повече от една стъпки; от безусловните само към една стъпка
Стъпка – изпълнение на едно правило; стъпките са съществено повече от правилата (стъпките зависят и от входните данни)
Основни свойства на алгоритмите –
-
определеност - описанието на алгоритъма е ясно и недвусмислено, определя еднозначно действията, които се извършват
-
масовост – прилага се не за една конкретна задача, а за клас от задачи; конкретната задача се определя с набора от входните данни
-
резултатност – всяко изпълнение на алгоритъма завършва за крайно време; трябва да са налице предпоставки – да има краен брой стъпки и всяка стъпка да се изпълнява за крайно време
-
цикличност – има възможност при описване на алгоритмите групи от правила да се изпълняват многократно
Блок – схеми
Начало
Не
Не
Не
Да
Да
Да
Край
Въвеждане на n и а1,а2,...,an
  
α = a1
β = a1
k = 2
k = k + 1
 
α = ak
β = ak
Изведи α и β
ak > β
k<=n
ak < α
      
С правоъгълните блокове се означават безусловните действия; с ромбовидните се означават условните (от тях има две разклонения - истина или лъжа); елипсовидните блокове указват началото и края на програмата; възможно е да се използват блокове с форма на успоредници за въвеждането и извеждането на данни; във всеки блок влиза поне една стъпка с изключение на началото и края
Възможно е да се прави прекъсване в блок – схемата по следния начин:
N
N
  
N е цяло число.
Компютърът изисква алгоритмите да са написани на машинен език; транслаторът е програма на машинен език; функцията му е да преобразува алгоритъма от словесно описание или блок – схема в машинен език; естествено транслаторите за словесно описание и за блок – схема са различни
Сподели с приятели: |
