All plugins suddenly deactivated due to an error

The website in question is a WordPress installation on a typical shared hosting server. The website has been up for over a year now. All my plugins got suddenly deactivated, I discovered today. The Plugin page gave a list of error messages, one for each plugin that looked as follows:
“The plugin “so-and-so” has been deactivated dues to an error: The plugin does not have a valid header.”

When I entered individual plugins’ admin pages I got an “Internal Server Error” message.

I can provide screen shots for both types of error messages.

The web hosting company is looking into it but they’re telling me this is a WordPress issue, so while they’re looking I thought I’d ask around as well. Any ideas what may have happened?

Btw, the hosting company did something while they were with me on the phone. They asked me to try to log into the admin panel again, and when i did, the error messages were gone but so were the plugins. The message on the page says “You do not have any plugins available at this time.” But I cannot re-install those plugins. When I try, I get a “failed installation” message. Probably because the plugins are actually on the server and installed just deactivated and inaccessible.

The only type of activity that may have introduced change on my end was that I installed WP-Optimize plugin to help keep the database tables optimized. I installed it probably about a month ago. I don’t know when the issue with the plugins started. I discovered it accidentally—the backup plugin stopped emailing me backups and I went in today to see what happened.

Any suggestions as to how to proceed? I am not a programmer and I don;t feel comfortable messing around on my own unless someone offers specific instructions.

Thanks in advance.
Basia